【代码随想录|动态规划02】

62.不同路径

题目链接：62. 不同路径 - 力扣（LeetCode）

1.确定dp[i]含义  dp[i][j]是位于第i行第j列所能走的不同路径

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

3.dp数组的初始化（因为机器人只能往下往右走，所以你往下那条路就只能一直往下，往右那条路也只能一直往右所以路径都是1）
       每一行初始为1     dp[i][0]=1;
       每一列初始为1     dp[0][j]=1;

4.遍历顺序：从前向后，从上往下（没有上面和左边的数推不出来要求的数）

5.（打印dp数组）

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0));
        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.不同路径||

题目链接：63. 不同路径 II - 力扣（LeetCode）

1.确定dp[i]含义:到达i,j有多少种不同的路径。

2.递推公式：这里有障碍的地方就直接continue，让它等于0后面也方便计算，然后dp[i][j]=dp[i-1][j]+dp[i][j-1];

3.dp数组的初始化：这里有了障碍的话，就是如果有了障碍那一行或者那一列就全为0，因为绕不过去，然后
       每一行初始为1     dp[i][0]=1;
       每一列初始为1     dp[0][j]=1;

4.遍历顺序：从前向后，从上往下（没有上面和左边的数推不出来要求的数）

5.（打印dp数组）

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        if (obstacleGrid[0][0]==1||obstacleGrid[n-1][m-1]==1)return 0;
    //起点或者终点有障碍直接返回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]==1)continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};