学步园

这三题都是简单的动态规划题目，Unique Paths其实结果是C(m+n-2,n-1),因为m.n 的值比较大时，不方便用求阶乘的方式直接求，容易溢出，所以,使用动态规划类似二项式拆解的方式进行求解

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m<=1)return m;
        if(n<=1)return n;
        int map[m+1][n+1];
        memset(map,0,sizeof(map));
        for(int i=0;i<n;i++)map[0][i]=1;
        for(int i=0;i<m;i++)map[i][0]=1;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                map[i][j]=map[i-1][j]+map[i][j-1];
            }
        return map[m-1][n-1];
    }
};

Unique Paths II 在上一题的基础上加上了障碍，因此只要在上一题求解的基础上，对于障碍处通过绕开的计数方式即可

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

Minimum Path Sum 则通过min res[i][j]=min(res[i-1][j],res[i][j-1])+map[i][j],其中map 为记录原始的值的矩阵，不断向下向右可得

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int len1=grid.size();
        if(len1==0)return 0;
        int len2=grid[0].size();
        for(int i=1;i<len1;i++)grid[i][0]+=grid[i-1][0];
        for(int i=1;i<len2;i++)grid[0][i]+=grid[0][i-1];
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                if(grid[i-1][j]<grid[i][j-1])
                   grid[i][j]+=grid[i-1][j];
                 else
                    grid[i][j]+=grid[i][j-1];
            }
        }
        
    return grid[len1-1][len2-1];   
    }
};