动态规划之不同路径 II

简介: 动态规划之不同路径 II

1. 问题分析



题目链接选自力扣 : 不同路径 II

18f468aede8a9b7df166b633ba8b4117.png

对于路径问题, 我的上一篇文章 ( 不同路径问题 )刚刚讲解了这个问题的基础版. 同样的它也是只能向右或者向下不能进行回退. 不一样的是, 当遇到障碍物时, 那么就不能从这通过了.


例如题目的实例 1. 位置, 这个二维数组某个位置的值为 1 时, 表明它是一个障碍物, 此时无法从这儿通过. 在图解中则为红宝石的位置. 原本有四条不同的路因为障碍物变成了两条.

image.png


2. 状态表示



还是一样的. 以 dp[i][j] 表示从起点位置到 ( i, j ) 位置时一共有多少种不同的路径方法.


3. 状态转移方程



按照之前的经验, 以最近的一步进行问题分解. 想要到达 ( i, j ) 这个位置. 就只能从 ( i-1, j ) 的位置向下一步到达或者从 ( i, j-1 ) 的位置向右一步到达. ( 具体分析看我上一篇文章 不同路径 ). 因此 dp[i][j] 就有了两种情况.


  1. 从 ( i, j-1 ) 位置向前一步到达 ( i, j ) 位置


由于从 ( i, j-1 ) 位置到达 ( i, j ) 位置不管怎么走, 最终都会经过这两个点. 那么到达 ( i, j-1 ) 有多少种方法也就意味着此时到达 ( i, j ) 有多少种不同的路径方法. 正好符合我们的状态表示. 即 dp[i][j-1]


  1. 从 ( i-1, j ) 位置向下一步到达 ( i, j ) 位置


同样的, 到达 ( i-1, j ) 位置有多少种方法也就意味着此时从起点到 ( i, j ) 位置有多少种不同路径方法. 即 dp[i-1][j].


那么, 会有人问了. 如果从 ( i, j-1 ) 去 ( i,j ) 位置时, 这个 ( i, j-1 ) 位置是障碍物怎么办呢 ?


你可以想一想, 如果这个点是障碍物, 意味着要经过这个点的前提下到达 (i,j) 是一条路都行不通的, 因此这个时候 dp[i][j-1] 是为 0 的, 对于整个状态转移方程来说是没有影响的 !


因此最终的状态转移方程为 : dp[i][j] = dp[i-1][j] + dp[i][j-1]


4. 初始化



初始化是为了防止进行填写 dp 表示不越界. 根据状态转移方程, 当我们想要填写 ( i, j ) 位置时, 就需要先知道从起点到达 ( i-1, j ) 和 ( i, j-1 ) 的不同路径数.


因此我们需要初始化第一行和第一列. 对于第一行而言, 它没有上一个点. 此时根据状态转移去计算就会越界. 同理第一列也一样.

并且第一行和第一列上的每一个点路径数都为 1. 由第一行上的每个点都只能由起点向右走这一条路径到达这一点很容易想明白. 同理第一列上的每一个点也是 1.

这里还是采用之前一样的方式, 多开一行和一列进行初始化, 将繁杂的初始化行和列放在填表中一起写.

f73e02d8ddbaf24196b83d36e6baca16.png


5. 填表顺序



不难看出, 还是一样从上往下填写每一行, 而每一行又从左往右填写.


6. 返回值



题目要求返回 m,n 位置处的不同路径数. 而我们的 dp 表多开了一行一列为 dp[m+1][n+1], 因此此时 m, n 位置处不同的路径数的答案存放在 dp[m][n] 里


7. 代码演示



class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 1. 创建 dp 表
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m+1][n+1];
        // 2. 初始化
        // 只需要确保起始点为 1 就可以保证原本矩阵的第一行和第一列上的点都为 1
        dp[1][0] = 1; // 此处我选择起始点的前一个点为 1
        // dp[0][1] = 1; // 也可以选择起始点的上一个点为 1
        // 3. 填写 dp 表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                // 这里需要注意, 由于多开了一行一列. 对应到原本的矩阵中每一行每一列都需要 -1 才是原本矩阵的位置.
                // 当前这个点没有障碍物时
                if(obstacleGrid[i-1][j-1] != 1) {
                    // 根据状态方程填写
                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
                // 为障碍物时, dp[i][j] 为 0, 此处不写没关系
            }
        }
        // 4. 确认返回值
        return dp[m][n];
    }
}


相关文章
|
前端开发
如何初始化css样式?为什么要初始化css样式?
如何初始化css样式?为什么要初始化css样式?
120 0
|
存储
【牛客网】二叉树遍历(八)
【牛客网】二叉树遍历(八)
86 0
|
网络安全 开发工具 数据安全/隐私保护
上传成功但是在app管理中心找不到版本提交的解决方法
Appuploader常见错误及解决方法 问题解决秘籍 遇到问题,首先请登录苹果开发者官网检查账号是否有权限,是否被停用,是否过期,是否有协议需要同意,并且在右上角切换账号后检查所有关联的账号是否工作正常,特别留意邮箱地址,当有ipa上传,账号有发生变化,被停用,apple经常发送一些邮件通知,去检查邮件通知并根据邮件通知修改调整。只有账号正常没问题,功能才能正常使用。
|
存储 定位技术 Windows
《ArcGIS Engine+C#实例开发教程》第八讲 属性数据表的查询显示
原文:《ArcGIS Engine+C#实例开发教程》第八讲 属性数据表的查询显示 第一讲 桌面GIS应用程序框架的建立 第二讲 菜单的添加及其实现 第三讲 MapControl与PageLayoutControl同步 第四讲 状态栏信息的添加与实现 第五讲 鹰眼的实现 第六讲 右键菜单添加与实现 教程Bug及优化方案1 第七讲 图层符号选择器的实现1 第七讲 图层符号选择器的实现2 第八讲 属性数据表的查询显示 摘要:这一讲中,我们将实现图层属性数据表的查询显示。
1468 0
|
.NET C# 开发框架
如何:创建自定义 HTTP 模块
来源:MSDN 如何:创建自定义 HTTP 模块 本主题中描述的自定义 HTTP 模块阐释了 HTTP 模块的基本功能。
870 0
kde
|
15天前
|
JSON Linux 数据格式
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
9400 76
|
12天前
typora免费版,激活方法,Typora使用教程
Typora是一款简洁高效的Markdown编辑器,支持即时渲染。本教程涵盖安装方法、文件操作、视图控制、格式排版、字体样式及Markdown语法,助你快速上手使用Typora进行高效写作。
2394 6
|
5天前
|
云安全 人工智能 安全
|
18天前
|
人工智能 定位技术 API
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
2252 34
|
6天前
|
Ubuntu JavaScript Linux
Windows安装Claude Code
Claude Code 是 Anthropic 推出的代码助手,支持在 Windows 通过 WSL(Windows Subsystem for Linux)运行。本文介绍如何在 Windows 系统中启用 WSL、安装 Ubuntu 子系统、配置 Python 与 Node.js 环境,并最终安装和运行 Claude Code。内容涵盖 WSL 设置、开发工具安装、依赖配置及常见问题解决方法,助你顺利在本地环境中使用 Claude Code 提升编码效率。
599 1
Windows安装Claude Code
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问