leetcode 62. 不同路径

 只用一维数组：

/**
滚动数组：O(mn) time,O(n) space
**/

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(n==0||m==0) return 0;
        vector<int> dp(n,1);
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++)
                dp[j]=dp[j]+dp[j-1];
        }
        return dp[n-1];
    }
};

O(mn)time O(mn) space

从左上角更新，每次坐标i,j的最多路径为：dp[i][j]=dp[i][j+1]+dp[i+1][j]

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==0 || n==0) return 0;
        int dp[m][n];
        for(int j=0;j<n;j++){
            dp[m-1][j]=1;
        }
        for(int i=0;i<m;i++){
            dp[i][n-1]=1;
        }
        for(int i=m-2;i>=0;--i){
            for(int j=n-2;j>=0;--j){
                dp[i][j]=dp[i][j+1]+dp[i+1][j];
            }
        }
        return dp[0][0];
    }
};