【学会动态规划】不同路径 II（6）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】不同路径 II（6）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：63. 不同路径 II - 力扣（Leetcode）

【学会动态规划】不同路径 II（6）,学会动态规划,动态规划,算法

这道题目也不难理解，相比之前的不同路径，

这道题添加了障碍物，题目给了我们一个二维的矩阵，

通过示例我们可以得知：

没有障碍物的位置就是初始化成0，有障碍物的位置就是1

而有障碍物的位置不能走，然后还是求路径数量。

2. 算法原理

1. 状态表示

dp[ i ][ j ] 就表示到[ i，j ]的时候，一共有多少种方法。

2. 状态转移方程

如果是没有障碍物的，我们就让：

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

如果有障碍，就让dp[ i ][ j ] = 0 表示这种路径不存在。

3. 初始化

我们多加一行和一列的虚拟节点，防止出现越界的情况，

把它们初始化成0，但是要保证第一个节点初始化成1.

4. 填表顺序

从左往右，从上往下。

5. 返回值

dp[ m ][ n ] ，终点作为返回值。

3. 代码编写

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        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) continue;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};