【动态规划】1301. 最大得分的路径数目

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总

LeetCoce1301. 最大得分的路径数目

给你一个正方形字符数组 board ，你从数组最右下方的字符 ‘S’ 出发。
你的目标是到达数组最左上角的字符 ‘E’ ，数组剩余的部分为数字字符 1, 2, …, 9 或者障碍 ‘X’。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
一条路径的 「得分」 定义为：路径上所有数字的和。
请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。
如果没有任何路径可以到达终点，请返回 [0, 0] 。
示例 1：
输入：board = [“E23”,“2X2”,“12S”]
输出：[7,1]
示例 2：
输入：board = [“E12”,“1X1”,“21S”]
输出：[4,2]
示例 3：
输入：board = [“E11”,“XXX”,“11S”]
输出：[0,0]
提示：
2 <= board.length == board[i].length <= 100

动态规划

动态规划的状态表示

dp1[r][c] 表示到达的最大分数，dp2[r][c] 表示方案数,0表示状态不存在。d

动态规划的转移方程

已知dp1[r][c] dp2[r][c]。如果dp1[r][c]<0，忽略。
{ 更新 r − 1 , c − 1 r > 0 且 c > 0 更新 r − 1 , c r > 0 更新 r , c − 1 c > 0 \begin{cases} 更新r-1,c-1 & r>0且c>0 \\ 更新r-1,c & r>0 \\ 更新r,c-1 & c > 0 \\ \end{cases} ⎩ ⎨ ⎧​更新r−1,c−1更新r−1,c更新r,c−1​r>0且c>0r>0c>0​

更新状态：
如果目标状态是障碍，忽略。
{ 忽略 新分数小于旧分数 d p 2 + = d p [ r ] [ c ] 新旧分数相等 更新 d p 1 , d p 2 = d p [ r ] [ c ] 其它 \begin{cases} 忽略 & 新分数小于旧分数 \\ dp2 += dp[r][c] & 新旧分数相等\\ 更新dp1,dp2 = dp[r][c] & 其它 \end{cases} ⎩ ⎨ ⎧​忽略dp2+=dp[r][c]更新dp1,dp2=dp[r][c]​新分数小于旧分数新旧分数相等其它​

动态规划的初始状态

起点格为dp1为0,dp2为1。其它格-1,0.

动态规划的填表顺序

从最后一行到第一行，从最后一列到第一列。

动态规格的返回值

dp1[0][0] 如果为-1，返回{0,0}。
否则返回{dp1[0][0],dp2[0][0]}

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};


class Solution {
public:
	vector<int> pathsWithMaxScore(vector<string>& board) {
		const int n = board.size();
		vector<vector<int>> dp1(n, vector<int>(n, -1));
		vector<vector<C1097Int<>>> dp2(n, vector<C1097Int<>>(n));
		dp1.back().back() = 0;
		dp2.back().back() = 1;
		for (int r = n - 1; r >= 0; r--)
		{
			for (int c = n - 1; c >= 0; c--)
			{
				auto Update = [&](int r1, int c1)
				{
					if ((r1 < 0) || (c1 < 0))
					{
						return;
					}
					const char& ch = board[r1][c1];
					if ('X' == ch )
					{
						return ;
					}
					const int iNew = dp1[r][c] + (isdigit(ch) ? (ch - '0') : 0);
					if (iNew == dp1[r1][c1])
					{
						dp2[r1][c1] += dp2[r][c];
					}
					if (iNew > dp1[r1][c1])
					{
						dp1[r1][c1] = iNew;
						dp2[r1][c1] = dp2[r][c];
					}
				};
				if (dp1[r][c] < 0)
				{
					continue;
				}
				Update(r - 1, c - 1);
				Update(r    , c - 1);
				Update(r - 1, c    );
			}
		}
		if (dp1[0][0] < 0)
		{
			return { 0,0 };
		}
		return { dp1[0][0],dp2[0][0].ToInt() };
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<string> board;
	{
		Solution sln;
		board = { "E23", "2X2", "12S" };
		auto res = sln.pathsWithMaxScore(board);
		Assert(vector<int>{7, 1}, res);
	}

	{
		Solution sln;
		board = { "E12", "1X1", "21S" };
		auto res = sln.pathsWithMaxScore(board);
		Assert(vector<int>{4,2}, res);
	}
	{
		Solution sln;
		board = { "E11", "XXX", "11S" };
		auto res = sln.pathsWithMaxScore(board);
		Assert(vector<int>{0, 0}, res);
	}
}

2023年2月

class C1097Int
{
public:
C1097Int(int iData = 0) :m_iData(iData)
{

 }
 C1097Int  operator+(const C1097Int& o)const
 {
	 return C1097Int((m_iData + o.m_iData) % s_iMod);
 }
 C1097Int&  operator+=(const C1097Int& o)
 {
	 m_iData = (m_iData + o.m_iData) % s_iMod;
	 return *this;
 }
 C1097Int  operator*(const C1097Int& o)const
 {
	 return((long long)m_iData *o.m_iData) % s_iMod;
 }
 C1097Int&  operator*=(const C1097Int& o)
 {
	m_iData =((long long)m_iData *o.m_iData) % s_iMod;
	 return *this;
 }
 int ToInt()const
 {
	 return m_iData;
 }

private:
int m_iData = 0;;
static const int s_iMod = 1000000007;
};

int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}

int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}

template
void MinSelf(T* seft, const T& other)
{
*seft = min(*seft, other);
}

template
void MaxSelf(T* seft, const T& other)
{
*seft = max(*seft, other);
}

int GetNotRepeateNum(int len, int iHasSel)
{
if (0 == len)
{
return 1;
}
if ((0 == iHasSel) && (1 == len))
{
return 10;
}
int iRet = 1;
if (iHasSel > 0)
{
for (int tmp = 10 - iHasSel; (tmp >= 2)&& len ; tmp–,len–)
{
iRet *= tmp;
}
}
else
{
iRet *= 9;
len–;
for (int tmp=9; (tmp>=2)&&len; len–,tmp–)
{
iRet *= tmp;
}
}
return iRet;
}

class Solution {
public:
vector pathsWithMaxScore(vector& board) {
m_r = board.size();
m_c = board[0].size();
m_vScource.assign(m_r, vector(m_c, -1));
m_vNum.assign(m_r, vector(m_c));
m_vScource[m_r - 1][m_c - 1] = 0;
m_vNum[m_r - 1][m_c - 1] = 1;
for (int r = m_r - 1; r >= 0; r–)
{
for (int c = m_c - 1; c >= 0; c–)
{
const char& ch = board[r][c];
if (‘X’ == ch)
{
continue;
}
int iCurSource = ((‘S’ == ch) || (‘E’ == ch)) ? 0 : ch - ‘0’;
//从右边来
Test(r, c + 1, r, c, iCurSource);
//从下边来
Test(r+1, c , r, c, iCurSource);
//从右下来
Test(r+1, c + 1, r, c, iCurSource);
}
}
if (-1 == m_vScource[0][0])
{
return {0, 0};
}
return{ m_vScource[0][0], m_vNum[0][0].ToInt() };
}
void Test(int iPreRow, int iPreCol, int r, int c, int iCurSource)
{
if (iPreRow >= m_r)
{
return;
}
if (iPreCol >= m_c)
{
return;
}
if (-1 == m_vScource[iPreRow][iPreCol])
{
return;
}
const int iNewSource = m_vScource[iPreRow][iPreCol] + iCurSource;
if (iNewSource < m_vScource[r][c])
{
return;
}
if (iNewSource == m_vScource[r][c])
{
m_vNum[r][c] += m_vNum[iPreRow][iPreCol];
return;
}
m_vScource[r][c] = iNewSource;
m_vNum[r][c] = m_vNum[iPreRow][iPreCol];
}
int m_r = 0, m_c = 0;
vector<vector> m_vScource;
vector<vector> m_vNum;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/383302.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Tauri】（1）：使用Tauri1.5版本，进行桌面应用开发，在windows，linux进行桌面GUI应用程序开发，可以打包成功，使用 vite 最方便

【Tauri】（1）：使用Tauri1.5版本，进行桌面应用开发，在windows，linux进行桌面GUI应用程序开发，可以打包成功，使用 vite 最方便

1&#xff0c;视频地址&#xff1a; https://www.bilibili.com/video/BV1Pz421d7s4/ 【Tauri】&#xff08;1&#xff09;&#xff1a;使用Tauri1.5版本&#xff0c;进行桌面应用开发&#xff0c;在windows&#xff0c;linux进行桌面GUI应用程序开发&#xff0c;可以打包成功&…
阅读更多...
springboot177健身房管理系统

springboot177健身房管理系统

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…
阅读更多...
Java图形化界面编程——弹球游戏 笔记

Java图形化界面编程——弹球游戏 笔记

Java也可用于开发一些动画。所谓动画&#xff0c;就是间隔一定的时间(通常小于0 . 1秒 )重新绘制新的图像&#xff0c;两次绘制的图像之间差异较小&#xff0c;肉眼看起来就成了所谓的动画 。 ​ 为了实现间隔一定的时间就重新调用组件的 repaint()方法&#xff0c;可以借助于…
阅读更多...
正则可视化工具：学习和编写正则表达式的利器

正则可视化工具：学习和编写正则表达式的利器

引言 正则表达式是一种强大的文本匹配和处理工具&#xff0c;但对于初学者和非专业开发者来说&#xff0c;编写和理解正则表达式可能是一项具有挑战性的任务。为了帮助人们更好地学习和编写正则表达式&#xff0c;正则可视化工具应运而生。本文将探讨正则可视化工具的优点&…
阅读更多...
自动化AD域枚举和漏洞检测脚本

自动化AD域枚举和漏洞检测脚本

linWinPwn 是一个 bash 脚本&#xff0c;可自动执行许多 Active Directory 枚举和漏洞检查。该脚本基于很多现有工具实现其功能&#xff0c;其中包括&#xff1a;impacket、bloodhound、netexec、enum4linux-ng、ldapdomaindump、lsassy、smbmap、kerbrute、adidnsdump、certip…
阅读更多...
力扣49. 字母异位词分组

力扣49. 字母异位词分组

Problem: 49. 字母异位词分组 文章目录 题目描述思路复杂度Code 题目描述 思路 1.我们利用一个无序映射以排序后的字符作为键、字符数组作为值&#xff1b; 2.每次我们从原始数组中取出一个字符串并对其进行排序&#xff0c;并将其添加到对应键所存的数组中&#xff1b; 3.创建…
阅读更多...
OpenAI---提示词工程的6大原则

OpenAI---提示词工程的6大原则

OpenAI在官方的文档里上线了Prompt engineering&#xff0c;也就是提示词工程指南&#xff0c;其中OpenAI有提到写提示词的6条大的原则&#xff0c;它们分别是&#xff1a; &#xff08;1&#xff09;Write clear instructions&#xff08;写出清晰的指令&#xff09; &#xf…
阅读更多...
【漏洞复现】狮子鱼CMS文件上传漏洞(wxapp.php)

【漏洞复现】狮子鱼CMS文件上传漏洞(wxapp.php)

Nx01 产品简介 狮子鱼CMS&#xff08;Content Management System&#xff09;是一种网站管理系统&#xff0c;它旨在帮助用户更轻松地创建和管理网站。该系统拥有用户友好的界面和丰富的功能&#xff0c;包括页面管理、博客、新闻、产品展示等。通过简单直观的管理界面&#xf…
阅读更多...
Java的接口

Java的接口

目录 1.接口的概念 2.语法规则 3.接口的使用 4.接口的特性 总结&#xff1a; 5.实现多个接口 6.接口间的继承 1.接口的概念 接口就是公共的行为规范标准&#xff0c;大家在实现时&#xff0c;只要符合规范标准&#xff0c;就可以通用。 在Java中&#xff0c;接口可以看成…
阅读更多...
学习Android的第十天

学习Android的第十天

目录 Android CheckBox 复选框 获得选中的 CheckBox 的值 自定义点击效果 改变文字与选择框的相对位置 修改文字与选择框的距离 Android ToggleButton 开关按钮 改变 ToggleButton 的状态和文本 Android Switch 开关 改变 Switch 的状态和文本 Android CheckBox 复选框…
阅读更多...
Vue源码系列讲解——模板编译篇【一】(综述)

Vue源码系列讲解——模板编译篇【一】(综述)

目录 1. 前言 2. 什么是模板编译 3. 整体渲染流程 4. 模板编译内部流程 4.1 抽象语法树AST 4.2 具体流程 5. 总结 1. 前言 在前几篇文章中&#xff0c;我们介绍了Vue中的虚拟DOM以及虚拟DOM的patch(DOM-Diff)过程&#xff0c;而虚拟DOM存在的必要条件是得先有VNode&…
阅读更多...
ChatGPT高效提问—prompt常见用法（续篇五）

ChatGPT高效提问—prompt常见用法（续篇五）

ChatGPT高效提问—prompt常见用法&#xff08;续篇五&#xff09; 1.1 种子词 ​ 种子词&#xff08;seed word&#xff09;通常指的是在对话中使用的初始提示或关键词&#xff0c;用于引导ChatGPT生成相关回复。种子词可以是一个词、短语或句子&#xff0c;通常与对话的主题…
阅读更多...
VTK 三维场景的基本要素(相机) vtkCamera

VTK 三维场景的基本要素(相机) vtkCamera

观众的眼睛好比三维渲染场景中的相机&#xff0c;在VTK中用vtkCamera类来表示。vtkCamera负责把三维场景投影到二维平面&#xff0c;如屏幕&#xff0c;相机投影示意图如下图所示。 1.与相机投影相关的要素主要有如下几个&#xff1a; 1&#xff09;相机位置: 相机所处的位置…
阅读更多...
Vue3中Setup概述和使用(三)

Vue3中Setup概述和使用(三)

一、引入Setup 1、Person.Vue 与Vue3编写简单的App组件(二) 中的区别是&#xff1a;取消data、methods等方法,而是将数据和方法定义全部放进setup中。 <template><div class"person"><h1>姓名:{{name}}</h1><h1>年龄:{{age}}</h…
阅读更多...
Linux操作系统基础（九）：Linux用户与权限

Linux操作系统基础（九）：Linux用户与权限

文章目录 Linux用户与权限 一、文件权限概述 二、终端命令&#xff1a;组管理 三、终端命令&#xff1a;用户管理 1、创建用户 、 设置密码 、删除用户 2、查看用户信息 3、su切换用户 4、sudo 4.1、给指定用户授予权限 4.2、使用 用户 zhangsan登录, 操作管理员命令…
阅读更多...
【开源】SpringBoot框架开发天沐瑜伽馆管理系统

【开源】SpringBoot框架开发天沐瑜伽馆管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 瑜伽课程模块2.3 课程预约模块2.4 系统公告模块2.5 课程评价模块2.6 瑜伽器械模块 三、系统设计3.1 实体类设计3.1.1 瑜伽课程3.1.2 瑜伽课程预约3.1.3 系统公告3.1.4 瑜伽课程评价 3.2 数据库设计3.2.…
阅读更多...
字节跳动官方出品AI，白嫖使用GPT4！

字节跳动官方出品AI，白嫖使用GPT4！

关注我&#xff0c;紧跟本系列专栏文章&#xff0c;咱们下篇再续&#xff01; 作者简介&#xff1a;魔都技术专家兼架构&#xff0c;多家大厂后端一线研发经验&#xff0c;各大技术社区头部专家博主&#xff0c;编程严选网创始人。具有丰富的引领团队经验&#xff0c;深厚业务架…
阅读更多...
Matplotlib核心：掌握Figure与Axes

Matplotlib核心：掌握Figure与Axes

详细介绍Figure和Axes&#xff08;基于Matplotlib&#xff09; &#x1f335;文章目录&#x1f335; &#x1f333;引言&#x1f333;&#x1f333; 一、Figure&#xff08;图形&#xff09;&#x1f333;&#x1f341;1. 创建Figure&#x1f341;&#x1f341;2. 添加Axes&am…
阅读更多...
Linux笔记之xhost +和docker的关系以及GDK_SCALE和GDK_DPI_SCALE详解

Linux笔记之xhost +和docker的关系以及GDK_SCALE和GDK_DPI_SCALE详解

Linux笔记之xhost 和docker的关系以及GDK_SCALE和GDK_DPI_SCALE详解 ——2024-02-11 code review! 文章目录 Linux笔记之xhost 和docker的关系以及GDK_SCALE和GDK_DPI_SCALE详解xhost 的作用xhost 与 Docker 的关系 -e GDK_SCALE 和 -e GDK_DPI_SCALE详解GDK_SCALEGDK_DPI_SC…
阅读更多...
8种基本类型的包装类（与String的转换）

8种基本类型的包装类（与String的转换）

java针对8种基本数据类型&#xff0c;定义了相应的引用类型&#xff1a;包装类(封装类)&#xff0c;有了类的特点&#xff0c;就能调用类中的方法&#xff0c;java才是真正的面向对象。 基本数据类型 包装类byte Byteshort Shortint Integerlong Longfloat Floa…
阅读更多...
最新文章

Copyright @ 2022~2023