JLUVicent

62不同路径&63不同路径II

 
  • 2023年 03月25日
  • 0 阅读

day39

62.不同路径

题目链接：62. 不同路径

解题思路：参考 视频

1.确定dp数组以及下标的含义：从(0,0)到第(i,j)位置的不同路径数

2.确定递推公式：$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

3.确定初始条件：从最上面或者最左边开始，初始只有一个路径

$dp[0][j]=1,dp[i][0]=1$

for( int i = 0; i < m; i++) dp[i][0] = 1;
for( int j = 0; j < n; j++) dp[0][j] = 1;

4.确定遍历顺序：从左往右，从上往下

5.打印dp数组

62.不同路径1

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0)); //dp初始化为0
        for( int i = 0; i < m; i++) dp[i][0] = 1;   //第一行初始化全为1
        for( int j = 0; j < n; j++) dp[0][j] = 1;   //第一列初始化为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

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

解题思路：参考 视频

总体思路和上面相同，唯一不同的就是在初始化和计算状态方程时候有变化。初始化时候碰到障碍物就终止赋值，计算状态方程时候必须保证没有障碍物。

1.确定dp[i]以及下标的含义：$dp[i][j]$表示从(0,0)到(i,j)的不同路径数

2.确定递推公式：$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

3.dp数组初始化：初始化为1，如果有障碍需要进行特殊处理

4.遍历顺序：从左到右，从上到下

5.打印数组

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {     
        // 时间：O(n*m)
        // 空间：O(n*m)   
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;   //边界条件，起点和终点有障碍
        vector<vector<int>> dp(m,vector<int>(n,0));
        for( int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;    //有障碍物时候初始化
        for( int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;    //有障碍物时候初始化
        for( int i = 1; i < m ; i++){
            for( int j = 1; j < n; j++){
                if( obstacleGrid[i][j] == 0){       //有障碍物时候的递推公式计算条件
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
};
搜索