搜索
查看
编辑修改
首页
UNITY
NODEJS
PYTHON
AI
GIT
PHP
GO
CEF3
JAVA
HTML
CSS
搜索
知新_RL
这个屌丝很懒,什么也没留下!
关注作者
热门标签
jquery
HTML
CSS
PHP
ASP
PYTHON
GO
AI
C
C++
C#
PHOTOSHOP
UNITY
iOS
android
vue
xml
爬虫
SEO
LINUX
WINDOWS
JAVA
MFC
CEF3
CAD
NODEJS
GIT
Pyppeteer
article
热门文章
1
IntelliJ IDEA配置git工作效率翻倍_idea 安装 git
2
Ubuntu下载jdk:cannot execute binary file
3
BioMed-CLIP 论文阅读笔记_biomedclip
4
动态模型管理:Mojo模型的自定义保存与加载控制
5
C语言在物联网(IoT)设备编程中的应用:传感器接口、无线通信与安全性(二)_c语言无线通信控制
6
Hugging Face 实战系列 总目录_hunggingface
7
python编程界面-编程入门10:Python图形界面
8
【渗透测试】垂直越权(1),面试宝典_垂直越权访问
9
Linux日志分析_linux提示登录失败,在哪里记录
10
linux查看服务器登录成功和登录失败的命令_怎么确定linux服务器有异常登录通过last
当前位置:
article
> 正文
动态规划算法:路径问题_动态规划 路径规划
作者:知新_RL | 2024-07-26 02:12:42
赞
踩
动态规划 路径规划
例题一
解法(动态规划):
算法思路:
1.
状态表⽰:
对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
i.
从 [i, j]
位置出发,巴拉巴拉;
ii.
从起始位置出发,到达 [i, j]
位置,巴拉巴拉。
这⾥选择第⼆种定义状态表⽰的⽅式:
dp[i][j]
表⽰:⾛到
[i, j]
位置处,⼀共有多少种⽅式。
2.
状态转移⽅程:
简单分析⼀下。如果
dp[i][j]
表⽰到达
[i, j]
位置的⽅法数,那么到达 [i, j] 位置之前的⼀⼩步,有两种情况:
i.
从 [i, j] 位置的上⽅( [i - 1, j] 的位置)向下⾛⼀步,转移到 [i, j] 位置;
ii.
从 [i, j] 位置的左⽅( [i, j - 1] 的位置)向右⾛⼀步,转移到 [i, j] 位置。
由于我们要求的是有多少种⽅法,因此状态转移⽅程就呼之欲出了:
dp[i][j] = dp[i - 1][j]+dp[i][j-1]。
3.
初始化:
可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
i.
辅助结点⾥⾯的值要「保证后续填表是正确的」;
ii.
「下标的映射关系」。
在本题中,「添加⼀⾏」,并且「添加⼀列」后,只需将
dp[0][1]
的位置初始化为
1
即可。
4.
填表顺序:
根据「状态转移⽅程」的推导来看,填表的顺序就是「从上往下」填每⼀⾏,在填写每⼀⾏的时候
「从左往右」。
5.
返回值:
根据「状态表⽰」,我们要返回
dp[m][n]
的值。
例题二
解法(动态规划):
算法思路:
本题为不同路径的变型,只不过有些地⽅有「障碍物」,只要在「状态转移」上稍加修改就可。
1.
状态表⽰:
对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
i.
从 [i, j]
位置出发,巴拉巴拉;
ii.
从起始位置出发,到达 [i, j]
位置,巴拉巴拉。
这⾥选择第⼆种定义状态表⽰的⽅式: dp[i][j] 表⽰:⾛到
[i, j]
位置处,⼀共有多少种⽅式。
2.
状态转移:
简单分析⼀下。如果
dp[i][j]
表⽰到达
[i, j]
位置的⽅法数,那么到达 [i, j] 位置之 前的⼀⼩步,有两种情况:
i.
从
[i, j]
位置的上⽅(
[i - 1, j]
的位置)向下⾛⼀步,转移到[i, j] 位置;
ii.
从
[i, j]
位置的左⽅(
[i, j - 1]
的位置)向右⾛⼀步,转移到
[i, j]
位置。
但是,
[i - 1, j]
与
[i, j - 1]
位置都是可能有障碍的,此时从上⾯或者左边是不可能到达 [i, j] 位置
的,也就是说,此时的⽅法数应该是 0。 由此我们可以得出⼀个结论,只要这个位置上「有障碍物」,那么我们就不需要计算这个位置上的值,直接让它等于 0
即可。
3.
初始化:
可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
i.
辅助结点⾥⾯的值要「保证后续填表是正确的」;
ii.
「下标的映射关系」。
在本题中,添加⼀⾏,并且添加⼀列后,只需将 dp[1][0]
的位置初始化为
1
即可。
4.
填表顺序:
根据「状态转移」的推导,填表的顺序就是「从上往下」填每⼀⾏,每⼀⾏「从左往右」。
5.
返回值:
根据「状态表⽰」,我们要返回的结果是
dp[m][n]
。
例题三
解法(动态规划):
算法思路:
1.
状态表⽰:
对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
i.
从 [i, j]
位置出发,巴拉巴拉;
ii.
从起始位置出发,到达 [i, j]
位置,巴拉巴拉。
这⾥选择第⼆种定义状态表⽰的⽅式: dp[i][j] 表⽰:⾛到
[i, j]
位置处,此时的最⼤价值。
2.
状态转移⽅程:
对于 dp[i][j] ,我们发现想要到达
[i, j]
位置,有两种⽅式:
i.
从 [i, j]
位置的上⽅
[i - 1, j]
位置,向下⾛⼀步,此时到达 [i, j] 位置能拿到的礼物价值为
dp[i - 1][j] + grid[i][j]
;
ii.
从 [i, j]
位置的左边
[i, j - 1]
位置,向右⾛⼀步,此时到达 [i, j] 位置能拿到的礼物价值为
dp[i][j - 1] + grid[i][j]
我们要的是最⼤值,因此状态转移⽅程为:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] 。
3.
初始化:
可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
i.
辅助结点⾥⾯的值要「保证后续填表是正确的」;
ii.
「下标的映射关系」。在本题中,「添加⼀⾏」,并且「添加⼀列」后,所有的值都为 0
即可。
4.
填表顺序:
根据「状态转移⽅程」,填表的顺序是「从上往下填写每⼀⾏」,「每⼀⾏从左往右」。
5.
返回值:
根据「状态表⽰」,我们应该返回
dp[m][n]
的值。
例题四
解法(动态规划):
算法思路:
关于这⼀类题,由于我们做过类似的,因此「状态表⽰」以及「状态转移」是⽐较容易分析出来的。 ⽐较难的地⽅可能就是对于「边界条件」的处理。
1.
状态表⽰:
对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
i.
从 [i, j]
位置出发,到达⽬标位置有多少种⽅式;
ii.
从起始位置出发,到达 [i, j]
位置,⼀共有多少种⽅式
这⾥选择第⼆种定义状态表⽰的⽅式:dp[i][j] 表⽰:到达
[i, j]
位置时,所有下降路径中的最⼩和。
2.
状态转移⽅程:
对于普遍位置
[i, j]
,根据题意得,到达
[i, j]
位置可能有三种情况:
i.
从正上⽅ [i - 1, j] 位置转移到
[i, j]
位置;
ii.
从左上⽅ [i - 1, j - 1] 位置转移到
[i, j]
位置;
iii.
从右上⽅
[i - 1, j + 1]
位置转移到
[i, j]
位置;
我们要的是三种情况下的「最⼩值」,然后再加上矩阵在
[i, j]
位置的值。
于是
dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i][j] 。
3.
初始化:
可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
i.
辅助结点⾥⾯的值要「保证后续填表是正确的」;
ii.
「下标的映射关系」。 在本题中,需要「加上⼀⾏」,并且「加上两列」。所有的位置都初始化为⽆穷⼤,然后将第⼀⾏初始化为 0 即可。
4.
填表顺序:
根据「状态表⽰」,填表的顺序是「从上往下」。
5.
返回值:
注意这⾥不是返回
dp[m][n]
的值!
题⽬要求「只要到达最后⼀⾏」就⾏了,因此这⾥应该返回「 dp 表中最后⼀⾏的最⼩值」。
例题五
解法(动态规划):
算法思路:
像这种表格形式的动态规划,是⾮常容易得到「状态表⽰」以及「状态转移⽅程」的,可以归结到
「不同路径」⼀类的题⾥⾯。
1.
状态表⽰:
对于这种路径类的问题,我们的状态表⽰⼀般有两种形式:
i.
从 [i, j]
位置出发,巴拉巴拉;
ii.
从起始位置出发,到达 [i, j]
位置,巴拉巴拉。
这⾥选择第⼆种定义状态表⽰的⽅式: dp[i][j] 表⽰:到达
[i, j]
位置处,最⼩路径和是多少。
2.
状态转移:
简单分析⼀下。如果
dp[i][j]
表⽰到达 到达
[i, j]
位置处的最⼩路径和,那么到达 [i, j] 位置之前的⼀⼩步,有两种情况:
i.
从 [i - 1, j] 向下⾛⼀步,转移到 [i, j] 位置;
ii.
从 [i, j - 1] 向右⾛⼀步,转移到 [i, j] 位置。
由于到
[i, j]
位置两种情况,并且我们要找的是最⼩路径,因此只需要这两种情况下的最⼩值,再加上 [i, j]
位置上本⾝的值即可。也就是: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
3.
初始化:可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
i.
辅助结点⾥⾯的值要「保证后续填表是正确的」;
ii.
「下标的映射关系」。 在本题中,「添加⼀⾏」,并且「添加⼀列」后,所有位置的值可以初始化为⽆穷⼤,然后让dp[0][1] = dp[1][0] = 1 即可。
4.
填表顺序:
根据「状态转移⽅程」的推导来看,填表的顺序就是「从上往下」填每⼀⾏,每⼀⾏「从左往后」。
5.
返回值:
根据「状态表⽰」,我们要返回的结果是
dp[m][n]
。
例题六
解法(动态规划):
算法思路:
1.
状态表⽰:
这道题如果我们定义成:从起点开始,到达
[i, j]
位置的时候,所需的最低初始健康点数。
那么我们分析状态转移的时候会有⼀个问题:那就是我们当前的健康点数还会受到后⾯的路径的影
响。也就是从上往下的状态转移不能很好地解决问题。
这个时候我们要换⼀种状态表⽰:从
[i, j]
位置出发,到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候,后续的最佳状态就已经知晓。
综上所述,定义状态表⽰为:dp[i][j] 表⽰:从[i, j]位置出发,到达终点时所需的最低初始健康点数。
2.
状态转移⽅程:
对于
dp[i][j]
,从 [i, j] 位置出发,下⼀步会有两种选择
(为了⽅便理解,设 dp[i][j] 的最终答案是
x
):
i.
⾛到右边,然后⾛向终点
那么我们在
[i, j]
位置的最低健康点数加上这⼀个位置的消耗,应该要⼤于等于右边位置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i][j + 1]
。通过移项可得: x >= dp[i][j + 1] - dungeon[i][j]
。因为我们要的是最⼩值,因此这种情况下的 x = dp[i][j + 1] - dungeon[i][j]
;
ii.
⾛到下边,然后⾛向终点
那么我们在
[i, j]
位置的最低健康点数加上这⼀个位置的消耗,应该要⼤于等于下边位置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i + 1][j]
。通过移项可得: x >= dp[i + 1][j] - dungeon[i][j]
。因为我们要的是最⼩值,因此这种情况下的 x = dp[i + 1][j] - dungeon[i][j]
;
综上所述,我们需要的是两种情况下的最⼩值,因此可得状态转移⽅程为:
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
但是,如果当前位置的
dungeon[i][j]
是⼀个⽐较⼤的正数的话,
dp[i][j]
的值可能变成 0
或者负数。也就是最低点数会⼩于
1
,那么骑⼠就会死亡。因此我们求出来的
dp[i][j]如果⼩于等于 0
的话,说明此时的最低初始值应该为
1
。处理这种情况仅需让
dp[i][j]与 1
取⼀个最⼤值即可:
dp[i][j] = max(1, dp[i][j])
3.
初始化:
可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
i.
辅助结点⾥⾯的值要「保证后续填表是正确的」;
ii.
「下标的映射关系」。在本题中,在 dp
表最后⾯添加⼀⾏,并且添加⼀列后,所有的值都先初始化为⽆穷⼤,然后让 dp[m][n - 1] = dp[m - 1][n] = 1 即可。
4.
填表顺序:
根据「状态转移⽅程」,我们需要「从下往上填每⼀⾏」,「每⼀⾏从右往左」。
5.
返回值:
根据「状态表⽰」,我们需要返回
dp[0][0]
的值。
本文内容由网友自发贡献,转载请注明出处:
【wpsshop博客】
推荐阅读
article
Elasticsearch
--
索引
别名
_
es
索引
别名
为什么
不能是已存在的
索引
...
索引
别名
在
Elasticsearch
所有的API中,对应的是一个或者多个
索引
。
Elasticsearch
可以对一个或者多...
赞
踩
article
从
Chrome
源码看
浏览器
如何
构建
DOM
树...
这几天下了
Chrome
的源码,安装了一个debug版的Chromium研究了一下,虽然很多地方都一知半解,但是还是有一点...
赞
踩
article
M2 运行
llamafile
_
llmafile
...
the cpu feature AVX was required at build time but isn’t ava...
赞
踩
article
我
把
我
的
声音
训练
成
了
AI
模型
,
并让它唱
了
一首歌...(附超全面
教程
,
你奶奶看
了
都会用)_
ai
训练
声音
...
天生五音不全
,
对于所有需要唱歌
的
场合
我
都是抗拒
的
,
因为只有一片笑声。
我
一直有一个梦想
,
就是用
我
的
声音
,
唱一首不跑调
的
歌。...
赞
踩
article
【跟着暴躁哥学
Python
】
http
.
server
:快速搭建你
的
本地
服务器
_
python
ser...
这样太简单了,我要自定义!” 没问题!来自定义一个:比如我们加上一个"/hello"路由。")else:super()....
赞
踩
article
记一次
git
lab代码
仓库
迁移_
git
clone
--
mirror
...
背景一个维护了将近三年的php项目,最近需要交给工程组的同事维护,需要把我们成都内网的
git
lab
仓库
的一些项目同步一份...
赞
踩
article
TSDF
算法
原理及
源码
解析...
先看效果参考
源码
: https://github.com/andyzeng/tsdf-fusion-python从图中可...
赞
踩
article
保证
数据
库
和ES的
数据
一致性
_
es
的
数据
一致性
怎么
保证
java
...
背景:在写毕设的全文检索功能时,要把题目的
数据
同步到
es
,考虑到一个问题,如何
保证
数据
库
和
es
的
一致性
呢?考虑方案如下:...
赞
踩
article
安卓
12(高版本9+以上)
安装
Charles
证书
到系统
证书
安装
目录_
安卓
手机
安装
charles
证书
...
(3) 下载并
安装
magisk的adguardcert模块。(1)
安卓
手机
开启root并
安装
Magisk。(2) 先安...
赞
踩
article
十大
排序
的
稳定性
和
时间
复杂度
...
十大
排序
算法的
稳定性
和
时间
复杂度
是数据结构和算法中的重要内容。十大
排序
的
稳定性
和
时间
复杂度
...
赞
踩
article
Jive
论坛与
Spring
框架...
Jive
论坛与
Spring
框架板桥里人 http://www.jdon.com 2004/07/01 没有一种新技术是...
赞
踩
article
生物
信息学
期刊
...
根据平时自己的收藏,整理一下自己的记录,
期刊
排名暂无顺序1. Bioinformatics该
期刊
是生物
信息学
领域的顶级期...
赞
踩
article
通过
Redis
+
自定义
注解
实现
接口
限流
策略_
自定义
注解
+
redis
实现
接口
限流
...
通过
Redis
+
自定义
注解
实现
接口
限流
策略_
自定义
注解
+
redis
实现
接口
限流
自定义
注解
+
redis
实现
接口
限流
...
赞
踩
article
2023
年
电赛
E
题
总结(op
e
nCV/
c++
)_
2023
电赛
e
题
...
findContours() 可以输出轮廓的所有点集,当然也包括任意形状,一般会用于(我接触到的)零件的边缘毛刺去除。如...
赞
踩
article
7-
Zip
安全漏洞
;
FASTJSON
2.0
发布
;
程序员
延寿指南…|叨资讯_
fastjson
2...
点击关注强哥,还有100多G的面试资料等你来拿哈喽,大家好,我是强哥。GitHub停用俄罗斯公司开发者账号;7-
Zip
...
赞
踩
article
我
用
AI
实现
了
我
的
插画
梦...
记忆中的青春,总在追逐一些美的事情。今天晚上泡在健身房里、明天又买
了
把吉他学起
了
民谣。那一年被《千与千寻》、《你的名字》...
赞
踩
article
iOS—
MVC
_
ios
mvc
...
2、 Controller在接收到View传过来的交互事件(View就是完成让人和程序的交互的呀,比如按B1按钮)之后,...
赞
踩
article
2020-12-
22
_
mohsen
guizani
ieee
...
对于边缘计算缓存的安全策略Security in Mobile Edge Caching with Reinforcem...
赞
踩
article
PHP
项目
|《
bbs
论坛含前台
后台
系统
》| 避错 注释 完整(
一
)|
无知
的
我复盘日记(图文排版无...
无知
的
我接触到了
PHP
,学习了
PHP
并尝试做了第
一
个比较合适
的
PHP
项目
。同时我正在不断优化自己写笔记
的
方法目
的
是 为了...
赞
踩
article
AI
在
创造
还是毁掉
音乐
?最近
AI
孙燕姿
的
个很火
,
我也
在
听...
然而
,
通过明确
AI
的
角色与定位、制定相关法规与政策、加强教育与培训以及促进跨学科研究与合作
,
我们可以更好地平衡技术发展与...
赞
踩
相关标签
elasticsearch
索引别名
git
xcode
数据结构与算法
llama
人工智能
AI作画
stable diffusion
AI绘图
模型
服务器
python
gitlab
全文检索
搜索引擎
java
android
adb
排序算法
算法
数据结构
设计模式
测试