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

看起来不错的运行效率

62题：

动态规划递推公式: 站在当前方块上可选择的路径数量　＝　我正下方那个方块可选择的路径数量　＋　我右侧那个方块可选择的路径数量；
边界情况：　棋盘上最右边那列只能选择往下走，所以dp[i][n-1]=1;
棋盘最下面那一行只能选择往右面走，所以dp[m-1][j] = 1;
进一步优化：重复利用一行数组代替m*n的dp数组，节省空间。

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];
    }
};

63题:

与62题的不同：凡是放了障碍物的地方dp[i][j]设置成零。如果最右侧一列上任意一个位置有障碍物，那么它以及它正上方的所有方块可选路径为０，也就是dp[i][n-1] = 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];
    }
};