动态规划：05不同路径

动态规划：05不同路径

62. 不同路径

五部曲

1. 确定dp数组含义：到达第i，j位置的路径条数为d[i][j]

2. 确定递归公式：d[i][j]=d[i-1][j]+d[i][j-1]

   我们发现，想要到d[i][j]，只能从d[i-1][j]或者d[i][j-1]达到

3. dp数组初始化：dp[0][j] = 1,dp[i][0] = 1

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

   我们的初始值是在最上面和最左面

5. debug：打印dp数组

代码

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 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]; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结

本题还是使用动规五部曲，但这次我们就要考虑如何正确的初始化了，初始化和遍历顺序其实也很重要！