【二】【动态规划NEW】91. 解码方法,62. 不同路径,63. 不同路径 II

2024-06-16 06:04

本文主要是介绍【二】【动态规划NEW】91. 解码方法,62. 不同路径,63. 不同路径 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

‘A’ -> “1”
‘B’ -> “2”

‘Z’ -> “26”
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1:

输入:s = “12”
输出:2
解释:它可以解码为 “AB”(1 2)或者 “L”(12)。
示例 2:

输入:s = “226”
输出:3
解释:它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3:

输入:s = “06”
输出:0
解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。

提示:

1 <= s.length <= 100
s 只包含数字,并且可能包含前导零。

利用递归思想写动态规划,字符串s返回解码的方法数,f(i)表示0~i区间的解码方法数.
字符串s的长度是n,我们需要得到f(n).
f(i)函数求解0~i区间的解码方法数,
可以让i位置字符单独解码,也可以让i和i-1位置字符两个一起解码.

如果让i位置字符单独解码,此时产生的解码方法数是f(i-1).
如果让i和i-1位置共同解码,此时产生的解码方法数是f(i-2).

如果让i位置字符单独解码需要满足的条件是s[i]!=‘0’.
如果让i和i-1位置字符共同解码需要满足的条件是s[i-1]!=‘0’,并且i-1和i位置字符属于1~26.

根据递归思想直接写动态规划写法.
状态表示,定义dp[i]表示0~i区间的解码方法数.
状态转移方程,如果让i位置字符单独解码,此时产生的解码方法数是dp[i-1].
如果让i和i-1位置共同解码,此时产生的解码方法数是dp[i-2].
填表顺序,填写i位置状态需要用到i-1,i-2位置状态,i需要从小到大.
初始化,特判,最开始的可以直接得出答案的就手动填写,越界的用三目表达式解决.

#define debug // 定义 debug 宏
#ifdef debug // 如果定义了 debug
#define bug(code) do{cout<<"L"<<__LINE__<<":"<<endl;code;}while(0) // 定义 bug 宏,输出当前行号并执行代码块
#else
#define bug(code) do{}while(0) // 如果没有定义 debug,bug 宏为空操作
#endifclass Solution {
public:int ret; // 用于存储结果的整数string s; // 输入字符串vector<int>dp; // 动态规划数组void solve(){ // 解决问题的函数ret=0; // 初始化结果为 0dp.assign(s.size(),-1); // 将动态规划数组初始化为 -1,大小为输入字符串的长度dp[0]=1; // 初始条件,dp[0] 设为 1for(int i=1;i<dp.size();i++){ // 从第 1 个字符开始遍历字符串int ans=0; // 用于存储当前字符的解码方法数if(s[i]!='0') ans+=dp[i-1]; // 如果当前字符不是 '0',则可以单独解码,加上 dp[i-1]if(s[i-1]!='0'&&(s[i-1]-'0')*10+(s[i]-'0')<=26) ans+=(i-2>=0?dp[i-2]:1); // 如果前一个字符不是 '0',且当前和前一个字符组成的数字小于等于 26,则可以合并解码,加上 dp[i-2](如果 i-2 小于 0,则加 1)dp[i]=ans; // 更新 dp[i] 为当前的解码方法数}ret=dp[dp.size()-1]; // 最后的结果是 dp 数组的最后一个值bug( // 如果定义了 debug,输出 dp 数组for(int i=0;i<dp.size();i++){ // 遍历 dp 数组cout<<dp[i]<<" "; // 输出 dp 数组的每一个值}cout<<endl; // 换行);}int numDecodings(string _s) { // 主函数,接收输入字符串ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 加速输入输出s=_s; // 将输入字符串赋值给成员变量 sif(s[0]=='0') return 0; // 如果字符串以 '0' 开头,返回 0solve(); // 调用 solve 函数求解return ret; // 返回结果}
};

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:
在这里插入图片描述

输入:m = 3, n = 7
输出:28
示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下
    示例 3:

输入:m = 7, n = 3
输出:28
示例 4:

输入:m = 3, n = 3
输出:6

提示:

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

f(i,j)表示从(0,0)位置到达(i,j)位置的路径数,我们需要的返回值是f(row,col).
f(i,j)=f(i-1,j)+f(i,j-1).
递归出口,如果是(0,0)位置,返回1.
如果越界了返回0.

利用递归思想直接写动态规划,定义状态标识dp[i][j]表示(0,0)位置到达(i,j)位置的路径数,需要的返回值是dp[row][col].
状态转移方程,dp[i][j]=dp[i-1][j]+dp[i][j-1].
初始化,特判,越界情况用三目表达式解决.
填表顺序,i需要从小到大填写.

#define debug // 定义 debug 宏
#ifdef debug // 如果定义了 debug
#define bug(code) do{cout<<"L"<<__LINE__<<":"<<endl;code;}while(0) // 定义 bug 宏,输出当前行号并执行代码块
#else
#define bug(code) do{}while(0) // 如果没有定义 debug,bug 宏为空操作
#endif  
class Solution {
public:int row, col; // 定义行数和列数int ret; // 用于存储结果的整数vector<vector<int>> dp; // 动态规划数组void solve() { // 解决问题的函数ret = 0; // 初始化结果为 0dp.assign(row + 1, vector<int>(col + 1, -1)); // 初始化 dp 数组为 -1,大小为 (row+1) x (col+1)for (int i = 1; i <= row; i++) { // 遍历每一行for (int j = 1; j <= col; j++) { // 遍历每一列if (i == 1 && j == 1) { // 如果是起点位置 (1, 1)dp[i][j] = 1; // 起点位置的路径数为 1continue; // 跳过后续计算}dp[i][j] = (i - 1 >= 1 ? dp[i - 1][j] : 0) + (j - 1 >= 1 ? dp[i][j - 1] : 0); // 计算当前位置的路径数}}ret = dp[row][col]; // 最后的结果是 dp 数组的右下角值bug( // 如果定义了 debug,输出 dp 数组for (int i = 1; i <= row; i++) { // 遍历 dp 数组的每一行for (int j = 1; j <= col; j++) { // 遍历 dp 数组的每一列cout << dp[i][j] << " "; // 输出 dp 数组的每一个值}cout << endl; // 换行}cout << endl; // 换行);}int uniquePaths(int _m, int _n) { // 主函数,接收输入的行数和列数ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出col = _n, row = _m; // 将输入的行数和列数赋值给成员变量solve(); // 调用 solve 函数求解return ret; // 返回结果}
};

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:
在这里插入图片描述

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右
    示例 2:
    在这里插入图片描述

输入:obstacleGrid = [[0,1],[0,0]]
输出:1

提示:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

网格里面有障碍物,填表的时候,障碍物的位置是不需要填写的,并且为了不影响其他位置的填写,如果是障碍物dp值设置为0即可,如果不设置为0,在状态转移方程哪里就需要多判断一下.
用三目运算符解决越界的情况.

#define debug // 定义 debug 宏
#ifdef debug // 如果定义了 debug
#define bug(code) do{cout<<"L"<<__LINE__<<":"<<endl;code;}while(0) // 定义 bug 宏,输出当前行号并执行代码块
#else
#define bug(code) do{}while(0) // 如果没有定义 debug,bug 宏为空操作
#endif
class Solution {
public:vector<vector<int>> arr; // 存储输入的障碍物网格int ret; // 用于存储结果的整数vector<vector<int>> dp; // 动态规划数组void solve() { // 解决问题的函数dp.assign(arr.size(), vector<int>(arr[0].size(), -1)); // 初始化 dp 数组为 -1,大小与输入网格相同for (int i = 0; i < arr.size(); i++) { // 遍历每一行for (int j = 0; j < arr[0].size(); j++) { // 遍历每一列if (arr[i][j] == 1) dp[i][j] = 0; // 如果当前位置是障碍物,路径数为 0if (arr[i][j] == 1) continue; // 如果当前位置是障碍物,跳过后续计算if (i == 0 && j == 0) { dp[i][j] = 1; continue; } // 起点位置的路径数为 1dp[i][j] = (i - 1 >= 0 ? dp[i - 1][j] : 0) + (j - 1 >= 0 ? dp[i][j - 1] : 0); // 计算当前位置的路径数}}ret = dp[arr.size() - 1][arr[0].size() - 1]; // 最后的结果是 dp 数组的右下角值}int uniquePathsWithObstacles(vector<vector<int>>& _obstacleGrid) { // 主函数,接收输入的障碍物网格ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出arr = _obstacleGrid; // 将输入的障碍物网格赋值给成员变量solve(); // 调用 solve 函数求解return ret; // 返回结果}
};

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。
同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。
谢谢您的支持,期待与您在下一篇文章中再次相遇!

这篇关于【二】【动态规划NEW】91. 解码方法,62. 不同路径,63. 不同路径 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1065643

相关文章

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

如何将Python彻底卸载的三种方法

《如何将Python彻底卸载的三种方法》通常我们在一些软件的使用上有碰壁,第一反应就是卸载重装,所以有小伙伴就问我Python怎么卸载才能彻底卸载干净,今天这篇文章,小编就来教大家如何彻底卸载Pyth... 目录软件卸载①方法:②方法:③方法:清理相关文件夹软件卸载①方法:首先,在安装python时,下