题解 | #不同路径的数目(一)#

这题最重要的是思路，当走到最后一行的时候，只能向右，只有一条路，当走到最后一列时，只能向下，只有一条路，其他时候可以向下或向右

• 递归的结束就是m==1或n==1,向下和向右当下只能选其一，所以要么是m-1,要么是n-1，加起来就可以。
• 动态规划的意思我理解是不走重复的路，那就把计算过的地方存下来即可。

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
//         递归
//         if(m==1 || n==1)return 1;
//         return uniquePaths(m-1,n)+uniquePaths(m,n-1);
        
//         动态规划
        int[][] arr = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(i==1){
                    arr[i][j]=1;
                    continue;
                }
                if(j==1){
                    arr[i][j]=1;
                    continue;
                }
                arr[i][j]= arr[i-1][j]+arr[i][j-1];    
            }
        }    
        return arr[m][n];
    }
}