LeetCode-62 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        if(m==1 && n==1){
            return 1;
        }
        int[][] dp = new int[n+1][m+1];   //dp[i][j]表示机器人走到第i行第j列的可能路径
        dp[1][1] = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==1 && j==1) continue;
                dp[i][j] = dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[n][m];
    }
}

动态规划优化空间复杂度  O(n)

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
}