Day33 动态规划part02

62.不同路径

class Solution {public int uniquePaths(int m, int n) {int dp[][] = new int[m][n];//初始化for(int i = 0; i < n ; i++){dp[0][i] = 1;}for(int j = 0; j < m ; j++){dp[j][0] = 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.确定dp[i][j]的含义：表示从（0 ，0）出发，到(i, j)有dp[i][j]条路径。

2.递归公式：dp[i][j]只能从左边即dp[ i-1 ] [ j ] ，或者从上边dp[ i ][ j-1 ]推出，而dp[ i-1 ] [ j ]表示到达(i-1 , j)的路径数。所以可以得到 dp[i][j] = dp[i-1][j] + dp[i][j-1];

3.初始化：由dp[i][j] = dp[i-1][j] + dp[i][j-1]知道，我们需要对dp[ 0 ] [ j ]和dp[ i ][ 0 ]进行初始化