有障碍的矩阵最短路径数

设dp[i][j]表示前i行和前j列最短路径数，状态方程如下：

1. 当i >= 2 && j >= 2时，
   1. 如果obstacle[i-2][j-1] != 1, dp[i][j] += dp[i-1][j]
   2. 如果obstacle[i-1][j-2] != 1, dp[i][j] += dp[i][j-1]
2. 基准1: dp[1][k] = obstacle[0][k-1] != 1 && dp[1][k-1]!=0 ? 1 : 0
3. 基准2: dp[k][1] = obstacle[k-1][0] != 1 && dp[k-1][1]!=0 ? 1 : 0

解释如下：

1. 如果矩阵的列数行数都大于等于2， 那么当前节点的最短路径数为左侧非阻塞节点的最短路径数+上侧非阻塞节点的最短路径数
2. 基准1: 当行数为1时，当前节点的最短路径数为1或0，取决于左侧是否有阻隔
3. 基准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()];
    }
};