设dp[i][j]表示前i行和前j列最短路径数,状态方程如下:
- 当
i >= 2 && j >= 2
时,- 如果
obstacle[i-2][j-1] != 1
,dp[i][j] += dp[i-1][j]
- 如果
obstacle[i-1][j-2] != 1
,dp[i][j] += dp[i][j-1]
- 如果
- 基准1:
dp[1][k] = obstacle[0][k-1] != 1 && dp[1][k-1]!=0 ? 1 : 0
- 基准2:
dp[k][1] = obstacle[k-1][0] != 1 && dp[k-1][1]!=0 ? 1 : 0
解释如下:
- 如果矩阵的列数行数都大于等于2, 那么当前节点的最短路径数为
左侧非阻塞节点的最短路径数
+上侧非阻塞节点的最短路径数
- 基准1: 当行数为1时,当前节点的最短路径数为1或0,取决于左侧是否有阻隔
- 基准2: 当列数为1时,当前节点的最短路径数为1或0,取决于上侧是否有阻隔
代码如下:
// // Created by jt on 2020/8/30. // #include <vector> using namespace std; class Solution { public: /** * * @param obstacleGrid int整型vector<vector<>> * @return int整型 */ int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) { // write code here if (obstacleGrid.size() < 1 || obstacleGrid[0].size() < 1) return 0; vector<vector<int> > dp(obstacleGrid.size() + 1, vector<int>(obstacleGrid[0].size() + 1, 0)); if (obstacleGrid[0][0] == 0) dp[1][1] = 1; for (int i = 2; i <= obstacleGrid.size(); ++i) { dp[i][1] = dp[i-1][1]!=0 && obstacleGrid[i-1][0]!=1 ? 1 : 0; } for (int i = 2; i <= obstacleGrid[0].size(); ++i) { dp[1][i] = dp[1][i-1]!=0 && obstacleGrid[0][i-1]!=1 ? 1 : 0; } for (int i = 2; i <= obstacleGrid.size(); ++i) { for (int j = 2; j <= obstacleGrid[0].size(); ++j) { dp[i][j] += obstacleGrid[i-2][j-1] == 0 ? dp[i-1][j] : 0; dp[i][j] += obstacleGrid[i-1][j-2] == 0 ? dp[i][j-1] : 0; } } return dp[obstacleGrid.size()][obstacleGrid[0].size()]; } };