动态规划真的可以为所欲为的(Leetcode 62/63)

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

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(),n;
        if(m>0) n = obstacleGrid[0].size();
        else return 0;
        
        int* dp = new int[n];
        memset(dp,0,sizeof(int)*n);
        
        for(int i=m-1;i>=0;i--)
        {
            if(obstacleGrid[i][n-1]==1||i+1<m&&dp[n-1]==0) dp[n-1] = 0;
            else dp[n-1] = 1;
            for(int j=n-2;j>=0;j--)
            {
                if(obstacleGrid[i][j]==1) dp[j] = 0;
                else  dp[j] = dp[j]+dp[j+1];
            }
        }
        return dp[0];
    }
};