代码随想录算法训练营第三十九天 |● 62.不同路径 ● 63. 不同路径 II

题目链接：62.不同路径

代码随想录

视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径_哔哩哔哩_bilibili

因为只能向右或则向下走，所以到第i，j位置有dp[i][j]的方法数等于 dp[i - 1] 的方法数加上 dp[i][j - 1]方法数；

我们要知道动态规划的五部曲；

1，确定dp数组的含义，下标的含义；

2，确定递推公式；

3，确定dp数组如何初始化；

4，确定遍历顺序；

5，打印dp数组（用来debug）

1，到第i，j位置有dp[i][j]的方法

2，dp[i][j] = dp[i - 1] + dp[i][j - 1];

3，dp数组初始化dp[0][j] = 1,dp[i][0] = 1;

4，从上向下，从左向右遍历；

5，打印dp数组，可以用来debug

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++) dp[i][0] = 1;
        for(int i = 0; i < n; i++) dp[0][i] = 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 

代码随想录

视频讲解：动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II_哔哩哔哩_bilibili

看完代码随想录之后的想法：

我们要知道动态规划的五部曲；

1，确定dp数组的含义，下标的含义；

2，确定递推公式；

3，确定dp数组如何初始化；

4，确定遍历顺序；

5，打印dp数组（用来debug）

这道题和上一个几乎一样，当我们遇到障碍的时候我们的dp[i][j] = 0;

然后在初始化的时候我们遇到障碍之后我们障碍之后需要设置为0；

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for(int i = 0; i < n && obstacleGrid[0][i] == 0; i++) dp[0][i] = 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 - 1][j] + dp[i][j - 1];
                else
                    dp[i][j] = 0;
            }
        }
        return dp[m - 1][n - 1];
    }
}

总结：

昨天晚上没有做什么，今天做了两道动态规划的题，上午背了一下单词，下午去买了一辆自行车；

呜呜呜没钱了；