题解 | #不同路径的数目(二)#

这题是根据不同路径的数目（一）演变而来，使用动态规划解法。

不同路径的数目（一）的解法

题目描述：有一个m*n矩阵，人只能向右走或向下走。从起点start，到终点end，共有多少条路径？

动态解法

1. 确定dp数组及下标的含义

   dp[i][j] 表示走到矩阵下标[i][j]时，最多的路径。

2. 初始化

   dp[i][0] = 1 且 dp[0][j] = 1

3. 状态转移方程

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

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

for(int i = 0;i < m; i++) {
  for(int j = 0; j < n; j++) {
    if(i == 0 || j == 0) dp[i][j] =1;
    else dp[i][j] = dp[i-1][j] + dp[i][j-1];
  }
}
return dp[m-1][n-1];

不同路径的数目（二）的解法

增加一个条件判断就行

int size_row =obstacleGrid.size();//行数
int size_col = obstacleGrid[0].size();//列数
vector< vector<int> > dp(size_row+1,vector<int>(size_col+1,0));
//当矩阵[i][j]为0时，此时这条路径不通，也即为0，我们初始化时已经为dp置零。
for(int i = 0;i < m; i++) {
  for(int j = 0; j < n; j++) {
    if((i == 0 || j == 0) && obstacleGrid[i][j] ==1) dp[i][j] =1;
    else {
      if(obstacleGrid[i][j]==1) dp[i][j] = dp[i-1][j] + dp[i][j-1]
      }
  }
}
return dp[size_row-1][size_col-1];