动态规划简单思路及例子（二）

简单动态规划以及举例二

• 前言
• 题目
• 代码实现

---

前言

这篇文章可以说是上篇文章的继续吧，因为这两类问题都是不同路径的问题，区别只是机器人路径中有没有进行障碍物，如果对这个还不太了解的话，可以看我的前一篇文章。

动态规划简单思路及例子（一）

题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。

商业转载请联系官方授权，非商业转载请注明出处。

代码实现

其他的就不多说了，因为题目都差不多，注释也比较齐全，直接上代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //1.确定dp数组
        //dp[i][j] 表示0,0到m-1,n-1有dp[i][j]条不同的路径
        int[][] dp = new int[m][n];
        //2.确定递推公式
        //dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //3.初始化dp数组
        //当原数组有值不为0时，说明是障碍物，不进行初始化 
        //当原数组有值为0时，说明可以进行初始化，初始化为1
        for(int i = 0;i < m && obstacleGrid[i][0] == 0;i++) {
            dp[i][0] = 1;
        }
        for(int i = 0; i < n && obstacleGrid[0][i] == 0;i++) {
            dp[0][i] = 1;
        }
        //4.确定递归顺序
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n ; j++){
                //当遇到障碍物时，跳过此次dp
                if(obstacleGrid[i][j] == 1){
                    continue;
                }else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}