114. 不同的路径、115. 不同的路径 II（动态规划）_不同路径ii

解题思路

这是一道典型的动态规划问题，使用一个二维数组path记忆到达每一点可行的走法总数。首先将左边界点和上边界点初始化为1，因为机器人起始与（0，0），左边界点和上边界点的走法只有1种。接下来的每一点（i,j），可以由（i-1,j）向右走

或是（i，j-1）向下走来到达，因此在（i,j）这一点可到达的方法有path[i-1][j]+path[i][j-1]种，到达终点的方法则是path最后一个点的数据。有种递归的意思，不过这个是从终点向起点递归

代码：

class Solution {
public:
    /*
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    int uniquePaths(int m, int n) {
        // write your code here
         if(m==0||n==0)
         return 0;
         vector<vector<int>>path(m,vector<int>(n,0));//定义一个m*n的二维数组，并初始化为0
         for(int i=0;i<m;i++)
         path[i][0]=1;
         for(int j=0;j<n;j++)
         path[0][j]=1;
         for(int i=1;i<m;i++)
           for(int j=1;j<n;j++)
           path[i][j]=path[i-1][j]+path[i][j-1];
         return path[m-1][n-1];
    }
};

"不同的路径" 的跟进问题：

现在考虑网格中有障碍物，那样将会有多少条不同的路径？

网格中的障碍和空位置分别用 1 和 0 来表示。

样例

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

class Solution {
public:
    /*
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
        // write your code here
        int m= obstacleGrid.size();//求二维数组的行元素数
        int n= obstacleGrid[0].size();//求二维数组的列元素数
        if(m==0||n==0)
        return 0;
        vector<vector<int>> path(m,vector<int>(n,0));
        if(obstacleGrid[0][0]==1)
        return 0;
        path[0][0]=1;
        //解决边界障碍物
         for(int i=1;i<m;i++)
          {
              if (obstacleGrid[i][0]==1)
               path[i][0]==0; 
              else path[i][0]=path[i-1][0];
           }
          for(int j=1;j<n;j++)
          {
              if (obstacleGrid[0][j]==1)
               path[0][j]==0; 
              else path[0][j]=path[0][j-1];
          }
          //计算路径总数
           for(int i=1;i<m;i++)
            {
                for(int j=1;j<n;j++)
                {
                  if(obstacleGrid[i][j]==1)//解决内部障碍物
                   path[i][j]=0; 
                  else 
                   path[i][j]=path[i-1][j]+path[i][j-1];
                 }
            }
       
             return path[m-1][n-1];
    }
};