62. 不同路径

class Solution {

public:

/*

    dp的二维问题，由题可知当前位置只能来自于上或左

    dp[i][j]:从（0，0）到达i行j列的位置有多少种不同的路径

    dp[i][j]=dp[i-1][j]+dp[i][j-1];

*/

    int uniquePaths(int m, int n) {

        //初始化时应该把第一行和第一列都赋值为1；

        vector<vector<int>>dp(m,vector<int>(n,1));

       //for(int i=0;i<m;i++) dp[i][0]=1;

       //for(int j=1;j<n;j++) dp[0][j]=1;

        for(int i=1;i<m;i++){

            for(int j=1;j<n;j++){

                dp[i][j]=dp[i-1][j]+dp[i][j-1];

            }

        }

        return dp[m-1][n-1];

    }

};

63. 不同路径 II

class Solution {

public:

/*

    这题与62类似，当前路径只能来自于上或左,但是有障碍物的时候就应该将其置为0，

    代表没有路径可以到达有障碍物的位置，

    if(obstacleGrid[i][j]==0){

        dp[i][j]=dp[]

    }

    else dp[i][j]=0;

    初始化也是要也考虑第一行和第一列,

    如果第一行第一列有障碍物，障碍物之前置为1，代表有一条路径；

    障碍物之后包括障碍物之后后置为0，代表没有路径可以到达；

*/

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        int m=obstacleGrid.size();

        int n=obstacleGrid[0].size();

        vector<vector<int>>dp(m,vector<int>(n,0));//默认所有位置都为0

        for(int i=0;i<m&&obstacleGrid[i][0]==0;i++) dp[i][0]=1;

        for(int j=0;j<n&&obstacleGrid[0][j]==0;j++) dp[0][j]=1;

        for(int i=1;i<m;i++){

            for(int j=1;j<n;j++){

                if(obstacleGrid[i][j]==0){

                    dp[i][j]=dp[i][j-1]+dp[i-1][j];

                }

                else dp[i][j]=0;

            }

        }

        return dp[m-1][n-1];

    }

};