【二】【动态规划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 条路径可以到达右下角。

向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下
示例 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 条不同的路径：

向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
示例 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; // 返回结果}
};