不同路径|| -- dp

思路看到这道题和上一道题很相似但是需要用代码实现如何记录从左上角到右下角有几条路径。首先我们思考从左上角到右下角需要满足什么条件例如一个m 3,n 3的矩阵在 左上角走到右下角需要向右移动两步和向下移动两步。那么dp[i][j] 代表什么从左上角走到当前位置的路径数量。比如dp[1][2]就是走到12这个位置上有多少条路径。那么就开始写代码class Solution { public int uniquePaths(int m, int n) { int [][] dp new int[m][n]; dp[0][0] 1; for(int i 0;i m ;i ){ for(int j 0;j n;j ){ if(i 0 j 0){ dp[i][j] 1; }else if(i 0){ dp[i][j] 1; }else if(j 0){ dp[i][j] 1; }else{ dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }