动态规划6：63. 不同路径 II

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题解：63. 不同路径 II - 力扣（LeetCode）

题解：

1.状态表示：dp[i]表示到达[i,j]位置有几种方法

2.状态转移方程：if(无障碍物) dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.初始化：本题如果障碍物在边缘位置，不方便初始化。通过多开一行一列空间，将初始化操作与填表操作合并

4.填表顺序：遍历二维数组，依次填表

5.返回值：dp[m][n]   m为网格行数，n为网格列数

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        size_t m=obstacleGrid.size();
        size_t n=obstacleGrid[0].size();
        //创建dp表
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //多开位置填值
        dp[0][1]=1;
        //填表
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(obstacleGrid[i-1][j-1]==1) dp[i][j]=0;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};