题解 | #求路径#

方法一：递归

 public int uniquePaths (int m, int n) {
        // write code here
        int sum = 0;
        sum = search(1,1,m,n);
        return sum;
    }
    public int search(int row,int col,int m,int n){
        if (row == m && col == n)
            return 1;
        if (row == m)
            return search(row,col+1,m,n);
        if (col == n)
            return search(row+1,col,m,n);
        return search(row+1,col,m,n) + search(row,col+1,m,n);
    }

可惜超时了。。。

方法二：动态规划

public int uniquePaths (int m, int n) {
        // write code here
       int[][] dp = new int[m+1][n+1];    //题意下标从1开始
        for (int i = 1; i <= m; i++){
            dp[i][1] = 1;    //初始化边界
        }
        for (int i = 1; i <= n; i++){
            dp[1][i] = 1;    //初始化边界 
        }
        for (int i = 2; i <= m; i++){
            for (int j = 2; j <= n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];    //当前位置到达的方式等于左一格的到达方式加上上一格的到达方式
            }
        }
        return dp[m][n];    //dp存的是当前位置的所有路径
    }