动态规划(Dynamic Programming):简称 DP,是一种求解多阶段决策过程最优化问题的方法。在动态规划中,通过把原问题分解为相对简单的子问题,先求解子问题,再由子问题的解而得到原问题的解。
动态规划最早由理查德 · 贝尔曼于 1957 年在其著作「动态规划(Dynamic Programming)」一书中提出。这里的 Programming 并不是编程的意思,而是指一种「表格处理方法」,即将每一步计算的结果存储在表格中,供随后的计算查询使用。
动态规划的核心思想:
把「原问题」分解为「若干个重叠的子问题」,每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后,动态规划方法才会执行下一个阶段的计算。
在求解子问题的过程中,按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」,把结果存储在表格中,当需要再次求解此子问题时,直接从表格中查询该子问题的解,从而避免了大量的重复计算。
这看起来很像是分治算法,但动态规划与分治算法的不同点在于:
适用于动态规划求解的问题,在分解之后得到的子问题往往是相互联系的,会出现若干个重叠子问题。
使用动态规划方法会将这些重叠子问题的解保存到表格里,供随后的计算查询使用,从而避免大量的重复计算。
下面我们先来通过一个简单的例子来介绍一下什么是动态规划算法,然后再来讲解动态规划中的各种术语。
斐波那契数列:数列由 $f(0) = 1,f(1) = 2$ 开始,后面的每一项数字都是前面两项数字的和。也就是:
$f(n) = \begin{cases} 0 & n = 0 \cr 1 & n = 1 \cr f(n - 2) + f(n - 1) & n > 1 \end{cases}$
通过公式 $f(n) = f(n - 2) + f(n - 1)$,我们可以将原问题 $f(n)$ 递归地划分为 $f(n - 2)$ 和 $f(n - 1)$ 这两个子问题。其对应的递归过程如下图所示:
从图中可以看出:如果使用传统递归算法计算 $f(5)$,需要先计算 $f(3)$ 和 $f(4)$,而在计算 $f(4)$ 时还需要计算 $f(3)$,这样 $f(3)$ 就进行了多次计算。同理 $f(0)$、$f(1)$、$f(2)$ 都进行了多次计算,从而导致了重复计算问题。
为了避免重复计算,我们可以使用动态规划中的「表格处理方法」来处理。
这里我们使用「自底向上的递推方法」求解出子问题 $f(n - 2)$ 和 $f(n - 1)$ 的解,然后把结果存储在表格中,供随后的计算查询使用。具体过程如下:
定义一个数组 $dp$,用于记录斐波那契数列中的值。
初始化 $dp[0] = 0,dp[1] = 1$。
根据斐波那契数列的递推公式 $f(n) = f(n - 1) + f(n - 2)$,从 $dp(2)$ 开始递推计算斐波那契数列的每个数,直到计算出 $dp(n)$。
最后返回 $dp(n)$ 即可得到第 $n$ 项斐波那契数。
具体代码如下:
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
dp = [0 for _ in range(n + 1)]
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 2] + dp[i - 1]
return dp[n]
这种使用缓存(哈希表、集合或数组)保存计算结果,从而避免子问题重复计算的方法,就是「动态规划算法」。
究竟什么样的问题才可以使用动态规划算法解决呢?
首先,能够使用动态规划方法解决的问题必须满足以下三个特征:
最优子结构性质
重叠子问题性质
无后效性
最优子结构:指的是一个问题的最优解包含其子问题的最优解。
举个例子,如下图所示,原问题 $S = \lbrace a_1, a_2, a_3, a_4 \rbrace$,在 $a_1$ 步我们选出一个当前最优解之后,问题就转换为求解子问题 $S{子问题} = \lbrace a_2, a_3, a_4 \rbrace$。如果原问题 $S$ 的最优解可以由「第 $a_1$ 步得到的局部最优解」和「 $S{子问题}$ 的最优解」构成,则说明该问题满足最优子结构性质。
也就是说,如果原问题的最优解包含子问题的最优解,则说明该问题满足最优子结构性质。
重叠子问题性质:指的是在求解子问题的过程中,有大量的子问题是重复的,一个子问题在下一阶段的决策中可能会被多次用到。如果有大量重复的子问题,那么只需要对其求解一次,然后用表格将结果存储下来,以后使用时可以直接查询,不需要再次求解。
之前我们提到的「斐波那契数列」例子中,$f(0)$、$f(1)$、$f(2)$、$f(3)$ 都进行了多次重复计算。动态规划算法利用了子问题重叠的性质,在第一次计算 $f(0)$、$f(1)$、$f(2)$、$f(3)$ 时就将其结果存入表格,当再次使用时可以直接查询,无需再次求解,从而提升效率。
无后效性:指的是子问题的解(状态值)只与之前阶段有关,而与后面阶段无关。当前阶段的若干状态值一旦确定,就不再改变,不会再受到后续阶段决策的影响。
也就是说,一旦某一个子问题的求解结果确定以后,就不会再被修改。
举个例子,下图是一个有向无环带权图,我们在求解从 $A$ 点到 $F$ 点的最短路径问题时,假设当前已知从 $A$ 点到 $D$ 点的最短路径($2 + 7 = 11$)。那么无论之后的路径如何选择,都不会影响之前从 $A$ 点到 $D$ 点的最短路径长度。这就是「无后效性」。
而如果一个问题具有「后效性」,则可能需要先将其转化或者逆向求解来消除后效性,然后才可以使用动态规划算法。
如下图所示,我们在使用动态规划方法解决某些最优化问题时,可以将解决问题的过程按照一定顺序(时间顺序、空间顺序或其他顺序)分解为若干个相互联系的「阶段」。然后按照顺序对每一个阶段做出「决策」,这个决策既决定了本阶段的效益,也决定了下一阶段的初始状态。依次做完每个阶段的决策之后,就得到了一个整个问题的决策序列。
这样就将一个原问题分解为了一系列的子问题,再通过逐步求解从而获得最终结果。
这种前后关联、具有链状结构的多阶段进行决策的问题也叫做「多阶段决策问题」。
通常我们使用动态规划方法来解决问题的基本思路如下:
划分阶段:将原问题按顺序(时间顺序、空间顺序或其他顺序)分解为若干个相互联系的「阶段」。划分后的阶段⼀定是有序或可排序的,否则问题⽆法求解。
这里的「阶段」指的是⼦问题的求解过程。每个⼦问题的求解过程都构成⼀个「阶段」,在完成前⼀阶段的求解后才会进⾏后⼀阶段的求解。
定义状态:将和子问题相关的某些变量(位置、数量、体积、空间等等)作为一个「状态」表示出来。状态的选择要满⾜⽆后效性。
一个「状态」对应一个或多个子问题,所谓某个「状态」下的值,指的就是这个「状态」所对应的子问题的解。
状态转移:根据「上一阶段的状态」和「该状态下所能做出的决策」,推导出「下一阶段的状态」。或者说根据相邻两个阶段各个状态之间的关系,确定决策,然后推导出状态间的相互转移方式(即「状态转移方程」)。
初始条件和边界条件:根据问题描述、状态定义和状态转移方程,确定初始条件和边界条件。
最终结果:确定问题的求解目标,然后按照一定顺序求解每一个阶段的问题。最后根据状态转移方程的递推结果,确定最终结果。
动态规划相关的问题往往灵活多变,思维难度大,没有特别明显的套路,并且经常会在各类算法竞赛和面试中出现。
动态规划问题的关键点在于「如何状态设计」和「推导状态转移条件」,还有各种各样的「优化方法」。这类问题一定要多练习、多总结,只有接触的题型多了,才能熟练掌握动态规划思想。
下面来介绍几道关于动态规划的基础题目。
4.1.1 题目链接
4.1.2 题目大意
描述:给定一个整数 $n$。
要求:计算第 $n$ 个斐波那契数。
说明:
斐波那契数列的定义如下:
$f(0) = 0, f(1) = 1$。
$f(n) = f(n - 1) + f(n - 2)$,其中 $n > 1$。
$0 \le n \le 30$。
示例:
示例 1:
输入:n = 2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入:n = 3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2
4.1.3 解题思路
1. 划分阶段
我们可以按照整数顺序进行阶段划分,将其划分为整数 $0 \sim n$。
2. 定义状态
定义状态 $dp[i]$ 为:第 $i$ 个斐波那契数。
3. 状态转移方程
根据题目中所给的斐波那契数列的定义 $f(n) = f(n - 1) + f(n - 2)$,则直接得出状态转移方程为 $dp[i] = dp[i - 1] + dp[i - 2]$。
4. 初始条件
根据题目中所给的初始条件 $f(0) = 0, f(1) = 1$ 确定动态规划的初始条件,即 $dp[0] = 0, dp[1] = 1$。
5. 最终结果
根据状态定义,最终结果为 $dp[n]$,即第 $n$ 个斐波那契数为 $dp[n]$。
4.1.4 代码
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
dp = [0 for _ in range(n + 1)]
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 2] + dp[i - 1]
return dp[n]
4.1.5 复杂度分析
时间复杂度:$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。
4.2.1 题目链接
4.2.2 题目大意
描述:假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。每次你可以爬 $1$ 或 $2$ 个台阶。现在给定一个整数 $n$。
要求:计算出有多少种不同的方法可以爬到楼顶。
说明:
$1 \le n \le 45$。
示例:
示例 1:
输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2:
输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
4.2.3 解题思路
1. 划分阶段
我们按照台阶的阶层划分阶段,将其划分为 $0 \sim n$ 阶。
2. 定义状态
定义状态 $dp[i]$ 为:爬到第 $i$ 阶台阶的方案数。
3. 状态转移方程
根据题目大意,每次只能爬 $1$ 或 $2$ 个台阶。则第 $i$ 阶楼梯只能从第 $i - 1$ 阶向上爬 $1$ 阶上来,或者从第 $i - 2$ 阶向上爬 $2$ 阶上来。所以可以推出状态转移方程为 $dp[i] = dp[i - 1] + dp[i - 2]$。
4. 初始条件
第 $0$ 层台阶方案数:可以看做 $1$ 种方法(从 $0$ 阶向上爬 $0$ 阶),即 $dp[1] = 1$。
第 $1$ 层台阶方案数:$1$ 种方法(从 $0$ 阶向上爬 $1$ 阶),即 $dp[1] = 1$。
第 $2$ 层台阶方案数:$2$ 中方法(从 $0$ 阶向上爬 $2$ 阶,或者从 $1$ 阶向上爬 $1$ 阶)。
5. 最终结果
根据状态定义,最终结果为 $dp[n]$,即爬到第 $n$ 阶台阶(即楼顶)的方案数为 $dp[n]$。
虽然这道题跟上一道题的状态转移方程都是 $dp[i] = dp[i - 1] + dp[i - 2]$,但是两道题的考察方式并不相同,一定程度上也可以看出来动态规划相关题目的灵活多变。
4.2.4 代码
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
4.2.5 复杂度分析
时间复杂度:$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。因为 $dp[i]$ 的状态只依赖于 $dp[i - 1]$ 和 $dp[i - 2]$,所以可以使用 $3$ 个变量来分别表示 $dp[i]$、$dp[i - 1]$、$dp[i - 2]$,从而将空间复杂度优化到 $O(1)$。
4.3.1 题目链接
4.3.2 题目大意
描述:给定两个整数 $m$ 和 $n$,代表大小为 $m \times n$ 的棋盘, 一个机器人位于棋盘左上角的位置,机器人每次只能向右、或者向下移动一步。
要求:计算出机器人从棋盘左上角到达棋盘右下角一共有多少条不同的路径。
说明:
$1 \le m, n \le 100$。
题目数据保证答案小于等于 $2 * 10^9$。
示例:
示例 1:
输入:m = 3, n = 7 输出:28
示例 2:
输入:m = 3, n = 2 输出:3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
4.3.3 解题思路
1. 划分阶段
按照路径的结尾位置(行位置、列位置组成的二维坐标)进行阶段划分。
2. 定义状态
定义状态 $dpi$ 为:从左上角到达 $(i, j)$ 位置的路径数量。
3. 状态转移方程
因为我们每次只能向右、或者向下移动一步,因此想要走到 $(i, j)$,只能从 $(i - 1, j)$ 向下走一步走过来;或者从 $(i, j - 1)$ 向右走一步走过来。所以可以写出状态转移方程为:$dpi = dpi - 1 + dpi$,此时 $i > 0,j > 0$。
4. 初始条件
从左上角走到 $(0, 0)$ 只有一种方法,即 $dp0 = 1$。
第一行元素只有一条路径(即只能通过前一个元素向右走得到),所以 $dp0 = 1$。
同理,第一列元素只有一条路径(即只能通过前一个元素向下走得到),所以 $dpi = 1$。
5. 最终结果
根据状态定义,最终结果为 $dpm - 1$,即从左上角到达右下角 $(m - 1, n - 1)$ 位置的路径数量为 $dpm - 1$。
4.3.4 代码
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for _ in range(n)] for _ in range(m)]
for j in range(n):
dp[0][j] = 1
for i in range(m):
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
4.3.5 复杂度分析
文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下:http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态:[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态
文章浏览阅读1.3w次,点赞45次,收藏99次。我个人用的是anaconda3的一个python集成环境,自带jupyter notebook,但在我打开jupyter notebook界面后,却找不到对应的虚拟环境,原来是jupyter notebook只是通用于下载anaconda时自带的环境,其他环境要想使用必须手动下载一些库:1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境
文章浏览阅读5.2k次,点赞19次,收藏28次。选择scoop纯属意外,也是无奈,因为电脑用户被锁了管理员权限,所有exe安装程序都无法安装,只可以用绿色软件,最后被我发现scoop,省去了到处下载XXX绿色版的烦恼,当然scoop里需要管理员权限的软件也跟我无缘了(譬如everything)。推荐添加dorado这个bucket镜像,里面很多中文软件,但是部分国外的软件下载地址在github,可能无法下载。以上两个是官方bucket的国内镜像,所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn
文章浏览阅读4.5k次,点赞2次,收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了,例如:这里的:sty..._vue el-color-picker
文章浏览阅读640次。基于芯片日益增长的问题,所以内核开发者们引入了新的方法,就是在内核中只保留函数,而数据则不包含,由用户(应用程序员)自己把数据按照规定的格式编写,并放在约定的地方,为了不占用过多的内存,还要求数据以根精简的方式编写。boot启动时,传参给内核,告诉内核设备树文件和kernel的位置,内核启动时根据地址去找到设备树文件,再利用专用的编译器去反编译dtb文件,将dtb还原成数据结构,以供驱动的函数去调用。firmware是三星的一个固件的设备信息,因为找不到固件,所以内核启动不成功。_exynos 4412 刷机
文章浏览阅读2w次,点赞24次,收藏42次。Linux系统配置jdkLinux学习教程,Linux入门教程(超详细)_linux配置jdk
文章浏览阅读3.3k次,点赞5次,收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图:_matlab微米怎么输入
文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件,可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中,对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数,而关闭则使用fclose函数。在C语言中,可以使用fread和fwrite函数进行二进制读写。 Biaoge 于2024-03-09 23:51发布 阅读量:7 ️文章类型:【 C语言程序设计 】在C语言中,用于打开文件的函数是____,用于关闭文件的函数是____。
文章浏览阅读3.4k次,点赞2次,收藏13次。跟随鼠标移动的粒子以grid(SOP)为partical(SOP)的资源模板,调整后连接【Geo组合+point spirit(MAT)】,在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in(CHOP)鼠标位置到metaball的坐标,实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动
文章浏览阅读178次。项目运行环境配置:Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX(Webstorm也行)+ Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。项目技术:Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成,B/S模式 + Maven管理等等。环境需要1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计
文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多,会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析,后面会慢慢更新。另外,博客只作为自己学习记录的一种方式,对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析 时序图
文章浏览阅读2.4k次,点赞41次,收藏13次。java 数据结构与算法 ——快速排序法_快速排序法