目录

题目链接：62.不同路径

思路

代码

题目链接：63. 不同路径 II

思路  

代码

总结

---

题目链接：62.不同路径

思路

        ①dp[i][j]表示从(0,0)到(i,j)有dp[i][j]条路径

        ②递推公式：dp[i][j] = dp[i][j-1] + dp[i-1][j]，只可能从两个路径过来，左或者上

        ③dp数组初始化，dp[0][0] = 0，dp[i][0] = 1，dp[0][j] = 1

        ④遍历顺序，从左到右一层一层遍历

        ⑤推到dp数组

代码

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0)); // 定义dp数组// dp数组初始化for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int j = 0; j < n; j++) {dp[0][j] = 1;}// 从左到右一层一层遍历for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {// 递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};

题目链接：63. 不同路径 II

思路  

        ①dp[i][j]表示从(0,0)到(i,j)有dp[i][j]条路径

        ②递推公式：dp[i][j] = dp[i][j-1] + dp[i-1][j]，只可能从两个路径过来，左或者上

        ③dp数组初始化，dp[0][0] = 0，dp[i][0] = 1，dp[0][j] = 1

        ④遍历顺序，从左到右一层一层遍历

        ⑤推到dp数组

        处理障碍物：如果遇到障碍物dp数组对应位置保持初始状态0。

代码

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {// 获取行列数int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m, vector<int>(n, 0)); // 定义dp数组// dp数组初始化for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1)break; // 障碍物之后无法到达，默认为0dp[i][0] = 1;}for (int j = 0; j < n; j++) {if (obstacleGrid[0][j] == 1)break; // 障碍物之后无法到达，默认为0dp[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1)continue; // 遇到障碍物时，跳过当前位置的处理dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};

总结

        ①路径问题，与台阶问题相似，每次前进都有两种方向，由此推出递推公式

        ②加入障碍物后，在原有代码上添加对障碍物的考虑即可，遇到障碍物跳过

        ③动态规划五部曲很好用