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 宏为空操作
#endif
class Solution {
public:
int ret; // 用于存储结果的整数
string s; // 输入字符串
vector<int>dp; // 动态规划数组
void solve(){ // 解决问题的函数
ret=0; // 初始化结果为 0
dp.assign(s.size(),-1); // 将动态规划数组初始化为 -1，大小为输入字符串的长度
dp[0]=1; // 初始条件，dp[0] 设为 1
for(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; // 将输入字符串赋值给成员变量 s
if(s[0]=='0') return 0; // 如果字符串以 '0' 开头，返回 0
solve(); // 调用 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; // 初始化结果为 0
dp.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; // 起点位置的路径数为 1
continue; // 跳过后续计算
}
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; // 如果当前位置是障碍物，路径数为 0
if (arr[i][j] == 1) continue; // 如果当前位置是障碍物，跳过后续计算
if (i == 0 && j == 0) { dp[i][j] = 1; continue; } // 起点位置的路径数为 1
dp[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; // 返回结果
}
};
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
