1.不同路径(类似于踩楼梯)

• $dp[i][j]=dp[i−1][j]+dp[i][j−1]$

• 2.19

  • dp【0】为 1

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];
    }
}

• 2.4
  • 初始化时初始化第一行和第一列为 1，然后从（1.1）开始 dp

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //类似于初始化dp[0]
        for(int i=0;i<m;i++) dp[i][0] = 1;
        for(int i=0;i<n;i++) dp[0][i] = 1;
        //dp从1开始,不然数组[i-1]会出界
        for(int i = 1;i<m;i++){
            for(int j =1;j<n;j++){
                dp[i][j] = dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
}