《算法设计与分析》课件 chp4动态规划

动态规划动态规划(DynamicProgramming)是由数学家理查德·贝尔曼于20世纪50年代提出的重要算法设计策略。它通过分解问题为子问题并利用其重复性质来求解最优解,是解决优化问题的强大工具。本章将通过详细案例分析,深入介绍动态规划的工作原理,帮助读者掌握如何利用这一技术设计高效算法。捡硬币问题:初识动态规划给定一排由n个硬币组成的序列,每个硬币的面值为正整数c₁,c₂,...,cₙ。目标是在不拾取相邻两枚硬币的前提下,尽可能多地拾取硬币,使得拾取的硬币总金额最大。例如:硬币序列为[2,7,9,3,1,5],最优解为拾取{2,9,5},总金额为16元。为什么需要动态规划?枚举法的局限枚举所有可能方案,时间复杂度为指数级Θ(2ⁿ),当n较大时计算效率极低分治法的挑战n个硬币分为左右两部分，每部分各包含n/2个硬币。对左/右半部分递归求解其最大金额。然而，在合并结果时，不能简单地将左右两部分的最大金额相加动态规划的优势通过识别最优子结构,避免重复计算,将指数级复杂度降至多项式级捡硬币问题:观察[2,7,9,3,1,5]当只有一枚硬币时，能拾取的最大价值显然为该硬币的面值，即2。考虑有两枚硬币的情况（2和7）。如果选择拾取第二枚硬币（面值为7），则第一枚硬币不能被拾取，此时总金额为7；如果不拾取第二枚硬币，则能拾取的最大金额为第一枚硬币的面值2。因此在只有前两枚硬币的情况下，拾取第二枚硬币可以得到最优解。捡硬币问题:寻找最优子结构对于第i枚硬币,我们面临两种互斥的选择:拾取第i枚硬币第i-1枚硬币不能被拾取,最大金额为第i枚硬币的面值加上前i-2枚硬币的最大金额不拾取第i枚硬币最大金额与前i-1枚硬币的最大金额一致通过比较这两种情况的最大值,我们可以得到前i枚硬币的最优解。这种递推关系为动态规划提供了基础。捡硬币问题:递推公式设最大拾取的金额为F(n),我们可以写出如下递推公式:边界条件:采用自底向上的方式逐步求解F(n):首先根据F(0)和F(1)求解出F(2),然后根据F(1)和F(2)求解出F(3),依此类推,直到计算出F(n)。捡硬币问题:算法实现算法:捡硬币问题的动态规划算法输入:一个数组coins,包含n个硬币的价值输出:可以拾取的最大硬币总金额F[0]←0F[1]←coins[1]fori←2tondoF[i]←max(F[i-1],F[i-2]+coins[i])returnF[n]算法的时间复杂度为Θ(n),空间复杂度为Θ(n)。捡硬币问题:求解示例对于硬币序列[2,7,9,3,1,5],计算过程如下:i硬币值F[i-2]+coins[i]F[i-1]F[i]0---012-02277273911711431011115112111265161216最大拾取金额为16元,拾取的硬币为{2,9,5}。动态规划的求解范式01找出最优解的性质识别最优子结构,即如何通过子问题的最优解构造原问题的最优解02递归定义最优值明确如何通过子问题的最优解递归地定义原问题的最优解,并写出递推公式03自底向上求解从最小规模的问题开始,逐步扩展到原问题的规模,避免重复计算04构造最优解通过回溯,根据递推公式中的选择情况,反向推导出最优解的路径兑零钱问题给定一个正整数数组coins,表示可用的硬币面值,以及一个目标金额n,假设每种硬币可以重复使用且数量无限,问如何用最少的硬币数凑出该金额n。例如:硬币面值为[1,2,5],兑11元最少需要3个硬币,即5+5+1。此问题的目标是找到凑出目标金额的最少硬币数,属于最优化问题,可以使用动态规划来求解。兑零钱问题:最优子结构对于兑n元硬币的情况,如果我们已经知道n-c(当前金额减去某个硬币面值c)的最少硬币数,那么兑n元的最少硬币数可以通过该结果加1得到。以n=11元为例,有三种选择:兑一枚5元硬币,剩余金额为6元兑一枚2元硬币,剩余金额为9元兑一枚1元硬币,剩余金额为10元因此,F(11)可以表示为:兑零钱问题:递推公式由此,我们可以得到F(n)的递推公式:边界条件:根据上述递推公式,可以从F(0)出发,逐步迭代计算出F(1),F(2),...,F(n)。兑零钱问题:求解示例对于coins={1,2,5},n=11的情况,求解过程如下:最优解为{1,5,5},共3枚硬币。兑零钱问题:算法实现时间复杂度Θ(kn)空间复杂度Θ(n)兑零钱问题:算法实现(2)背包问题在0-1背包问题中,给定n个物品,每个物品有一个重量wᵢ和一个价值vᵢ,同时给定一个背包的容量W。我们的目标是在以下约束条件下选择物品,使得背包内物品的总价值最大化:每个物品只能选择装入背包或者不装入背包,即0-1的选择背包内所有物品的总重量不能超过容量W这是一个经典的最优化问题,可以使用动态规划高效求解。背包问题:最优子结构分析观察

例如:物品重量w=[2,2,2],价值v=[3,7,6],容量W=4。前2个物品的最优解包含物品1和2,但全局最优解却舍弃了物品1。如果已知背包容量为w−1时的最优解，是否可以构造出背包容量为w时的最优解？物品重量w=[2,2,3]，物品价值v=[4,5,7]，背包容量W=5。当背包容量为4时，最优的选择是物品1和物品2，总价值为9。然而，当背包容量为5时，最优的选择是物品2和物品3，总价值为12。显然，背包容量为5的最优解并不能通过背包容量为4的最优解直接构造出来。背包问题:最优子结构分析关键观察如果同时考虑背包容量w和物品数量i,可以通过较小的子问题推导出整体问题的最优解。最优子结构体现在两个方面:容量减少的影响(从w转化为w-wᵢ)物品数量的递减(从i转化为i-1)背包问题:递推公式用F(n,W)表示在有前n个物品、背包容量为W时的最大价值。考虑到第n个物品,我们有两个选择:不选第n个物品此时的最大价值是前n-1个物品在容量W下的最大价值,即F(n-1,W)选第n个物品此时的最大价值是前n-1个物品在容量W-wₙ下的最大价值,即F(n-1,W-wₙ)+vₙ递推公式为:背包问题:求解示例假设有4个物品,重量为[2,3,4,5],价值为[3,4,5,6],背包容量为8。动态规划求解过程如下:物品\容量012345678000000000010033333332003447777300345789940034578910F[4][8]=10,表示在背包容量为8时的最大价值为10。通过回溯可得最优解为{物品2,物品4}。背包问题:算法复杂度Θ(nW)时间复杂度Θ(nW)空间复杂度最大子数组问题最大子数组问题的目标是在给定整数数组中找到具有最大和的连续子数组。给定一个长度为n的数组A=[a₁,a₂,...,aₙ],我们需要找到子数组A[aᵢ...aⱼ],使得该子数组的元素之和最大。我们之前已使用分治法和枚举法设计了相应的算法。那么,是否可以利用动态规划来更高效地求解此问题呢?最大子数组:最优子结构动态规划的核心在于识别最优子结构。在最大子数组问题中,最优子结构表现为:以第i个元素结尾的最大子数组的最优解可以通过第i-1个元素结尾的最大子数组的最优解递归构造出来。具体地:如果以第i-1个元素结尾的子数组和为f(i-1),则可以选择:将当前元素aᵢ加入该子数组(延续前一个子数组)直接从当前元素aᵢ开始一个新的子数组对于每个位置i,只需选择这两种方案中的较大值即可。最大子数组:递推公式定义f(i)为以第i个元素结尾的最大子数组和,递推公式为:其中:f(i-1)+aᵢ表示将当前元素aᵢ加入前一个子数组aᵢ表示以当前元素aᵢ开始一个新的子数组初始条件为:f(1)=a₁最终目标是找到最大子数组的和:最大子数组:求解示例假设数组A=[12,5,-1,31,-61,59,26,-53,58,97,-93,-23,84,-15,6],计算过程如下:最大子数组和为187,对应的子数组为[59,26,-53,58,97]。最大子数组:算法优化时间复杂度Θ(n)-只需遍历数组一次空间优化通过使用变量curr_sum保存f(i),将空间复杂度从Θ(n)优化为Θ(1)与分治法对比分治法Θ(nlogn)带权区间调度问题带权区间调度问题是经典的调度问题之一。给定n个作业,每个作业具有开始时间sᵢ、结束时间fᵢ以及权重wᵢ>0。如果两个作业的时间区间不重叠,即作业i的结束时间fᵢ不超过作业j的开始时间sⱼ(fᵢ≤sⱼ),则称作业i和j是相容的。问题的目标是在所有相容的作业子集中,找到总权重最大的子集。带权区间调度:最优子结构假设前i个作业的最大权重为F(i),我们可以采用与捡硬币问题类似的思路:不选择第i个作业如果第i个作业不在最优解中,那么前i个作业的最大权重F(i)等于前i-1个作业的最大权重,即:F(i)=F(i-1)选择第i个作业如果第i个作业在最优解中,那么F(i)=wᵢ+F(p(i)),其中p(i)表示小于i的最大索引j,使得作业j与作业i兼容综合上述两种情况,可得到递推公式:带权区间调度:求解示例假设有4个作业,其权重分别为50、20、100、200。计算过程如下:i作业权重wᵢp(i)F[i-1]wᵢ+F[p(i)]F[i]00-0001500050502200502050310015015015042003150350350通过动态规划计算得到F[4]=350。通过回溯可确定最优解的具体作业组合为{作业4、作业3、作业1}。带权区间调度:算法复杂度1排序步骤对所有作业按照结束时间进行升序排序,时间复杂度为Θ(nlogn)2计算p(i)使用二分查找加速查找过程,时间复杂度为Θ(nlogn)3计算F(n)自底向上计算F(n),时间复杂度为Θ(n)最长公共子序列问题最长公共子序列(LongestCommonSubsequence,LCS)问题是动态规划的经典问题之一。给定两个序列X=x₁x₂...xₘ和Y=y₁y₂...yₙ,找到一个最长的子序列,使得该子序列同时出现在X和Y中。例如:对于字符串X=GGCACCACG和Y=ACGGCGGATACG,它们的最长公共子序列为:LCS(X,Y)=GGCAACG这里的"子序列"是指可以通过从原始序列中删除一些字符(可以不连续)得到的序列,但要求剩余字符的相对顺序保持不变。最长公共子序列:类比思考在开始解决这个问题之前,让我们回顾之前学过的动态规划问题:背包问题的启示通过考虑"选择当前物品"和"不选择当前物品"的方式来分解子问题兑零钱问题的启示是否可以定义一个状态来表示“两个序列的前缀的最长公共子序列长度”？带权区间调度的启示通过当前元素是否匹配来构造决策最长公共子序列:最优子结构考虑序列X=x₁x₂...xₘ和Y=y₁y₂...yₙ,如果我们知道它们前缀子序列的最长公共子序列F(i,j),那么如何构造F(i+1,j+1)呢?两种决策如果xᵢ=yⱼ,可以选择这两个匹配的字符加入LCS,此时LCS的长度增加1。如果xᵢ≠yⱼ,需要通过删除xᵢ或yⱼ来考察更小的子问题。递推关系如果xᵢ=yⱼ:如果xᵢ≠yⱼ:边界条件:当i=0或j=0时,其中一个序列为空,公共子序列长度为0。最长公共子序列:求解示例以字符串X=GGCACCACG和Y=ACGGCGGATACG为例,详细展示动态规划求解过程:通过填表计算,我们得到最长公共子序列的长度为7。通过回溯可确定最长公共子序列的具体内容为GGCAACG。如果xᵢ=yⱼ:如果xᵢ≠yⱼ:最长公共子序列:算法复杂度Θ(mn)时间复杂度-需要填充大小为(m+1)×(n+1)的二维数组,每个单元格的计算时间为常数Θ(mn)空间复杂度-需要存储二维数组F最长公共子序列问题在许多实际场景中有着广泛的应用,特别是在需要比较或匹配两个序列的相似性时,例如文本比较、版本控制、生物信息学等领域。编辑距离编辑距离(EditDistance)是衡量两个字符串相似度的一种常用方法。给定两个字符串X=x₁x₂...xₘ和Y=y₁y₂...yₙ,求这两个字符串之间的最小编辑距离。编辑距离定义为将一个字符串转化成另一个字符串所需要的最少操作次数。允许对X施加的操作包括:插入:在X中插入一个字符删除:在X中删除一个字符替换:将X中的一个字符替换为另一个字符例如:给定字符串X=abc和Y=ac,可以通过一次删除操作(删除X中的字符b)将X转换为Y,因此X和Y之间的最小编辑距离为1。编辑距离:最优子结构用D(i,j)表示将字符串X=x₁x₂...xᵢ转换为字符串Y=y₁y₂...yⱼ的最小编辑距离。类似于最长公共子序列问题,我们通过比较xᵢ和yⱼ的值来构造最优子结构:xᵢ=yⱼ不需要进行操作,即D(i,j)=D(i-1,j-1)删除操作删除字符串X中的xᵢ,编辑距离为D(i,j)=D(i-1,j)+1插入操作在字符串的末尾插入yⱼ,编辑距离为D(i,j)=D(i,j-1)+1替换操作将字符串X中的xᵢ替换为yⱼ,编辑距离为D(i,j)=D(i-1,j-1)+1编辑距离:递推公式综合上述分析,递推公式总结如下:边界条件:如果X为空,则需要j次插入操作将X转化为Y;如果Y为空,则需要i次删除操作将X转化为Y。编辑距离:求解示例以字符串X=XAUAT和Y=HXAUAXKT为例,展示详细的计算过程:i\j0HXAUAXKT0012345678X111234567A222123456U333212345A444321234T555432233X转换为Y的最小编辑距离为3。通过回溯可得,需要3次插入操作:在X[4]后面插入'K',在X[4]后面插入'X',在X[0]后面插入'H'。编辑距离:应用场景拼写纠错在文本编辑器和输入法中,利用最小编辑距离来识别并纠正用户的拼写错误,提供最接近的单词建议机器翻译在自然语言处理中,用于评估机器翻译的结果与参考译文之间的差异来优化翻译模型生物信息学在DNA、RNA和蛋白质序列的比对中,寻找两个生物序列的相似性,反映序列之间的进化关系最小编辑距离问题和最长公共子序列问题都是衡量两个字符串相似度的重要方法。最优二叉搜索树二叉搜索树(BinarySearchTree,BST)是一种高效的数据存储与检索结构,其核心特性如下:对于每个节点,其左子树的所有节点值小于该节点值其右子树的所有节点值大于该节点值问题定义:给定一组关键字K={k₁,k₂,...,kₙ},其访问概率分别为P={p₁,p₂,...,pₙ}。对于一棵二叉搜索树,假设关键字kᵢ在树中的深度为dᵢ(根节点的深度为1),则该树的搜索代价定义为:最优二叉搜索树问题的目标在于构建一棵二叉搜索树,使得上述搜索代价C达到最小。最优二叉搜索树:问题分析以包含三个节点的二叉搜索树为例,设关键字集合K={10,20,30},其对应的访问概率分别为P={0.5,0.2,0.3}。最优二叉搜索树:问题分析以包含三个节点的二叉搜索树为例,设关键字集合K={10,20,30},其对应的访问概率分别为P={0.5,0.2,0.3}。所有可能的5种二叉搜索树结构的搜索代价分别为:树结构计算公式搜索代价树11×0.5+2×0.2+3×0.31.8树21×0.5+3×0.2+2×0.31.7树32×0.5+1×0.2+2×0.31.8树43×0.5+2×0.2+1×0.32.2树52×0.5+3×0.2+1×0.31.9可见树2的查找代价最低。进一步分析可以发现,树2的根节点是查找概率最高的关键字10。最优二叉搜索树:枚举法的局限如果采用枚举法来解决最优二叉搜索树问题,我们需要遍历所有可能的二叉搜索树结构。那么,对于包含n个节点的集合,究竟有多少种不同的二叉搜索树呢?设T(n)表示由n个节点构成的二叉搜索树的总数,递推关系可以表示为:经过数学推导,可得到T(n)的封闭解:由于T(n)的增长速度约为指数级,枚举法在n较大时计算效率非常低,因此需要设计一种更高效的算法。最优二叉搜索树:最优子结构我们定义C[i][j]表示关键字集合{kᵢ,kᵢ₊₁,...,kⱼ}构成的最优二叉搜索树的最小查找代价。假设我们选择kᵣ(i≤r≤j)作为根节点,那么这棵树的查找代价包括以下三部分:01左子树的查找代价

02右子树的查找代价关键字集合{kᵣ₊₁,kᵣ₊₂,...,kⱼ}构成的右子树的最小查找代价为C[r+1][j]03根节点和子树深度增加的影响根节点kᵣ位于第一层,其查找代价为pᵣ。当左、右子树挂在根节点下时,所有节点的深度都增加了1最优二叉搜索树:递推公式综合上述分析,当选择kᵣ作为根节点时,这棵树的总查找代价为:基于这一性质,我们可以选择所有可能的节点kᵣ作为根节点,选择使C[i][j]最小的那个。递推公式如下:这一性质是动态规划算法的基础:如果一颗二叉搜索树是最优的,那么它的左子树和右子树也必然是最优组织的。最优二叉搜索树:求解示例继续以关键字集合K={10,20,30},访问概率P={0.5,0.2,0.3}为例。我们的目标是求C[1][3]。在计算动态规划表C[i][j]时,需要按照对角线方向来填表:i\j12310.50.91.720.20.730.3通过动态规划计算得到C[1][3]=1.7。通过回溯可确定最优二叉搜索树的根节点为k₁=10,其右子树的根节点为k₃=30,k₂=20作为k₃的左子树。最优二叉搜索树:算法伪代码最优二叉搜索树:算法复杂度Θ(n³)基本算法时间复杂度需要填充n×n的二维数组,每个单元格需要枚举O(n)个根节点Θ(n²)空间复杂度需要额外空间存储二维数组C,其大小为n×n需要注意的是,最优二叉搜索树的应用前提是关键字的集合和每个关键字的访问概率必须已知或可以通过统计方法预估。在动态系统中,红黑树、B树等支持动态操作且性能稳定,是更常用的检索数据结构。矩阵链乘法问题

矩阵链乘法:递推公式定义M[i][j]为矩阵链乘法问题中,将矩阵链Aᵢ到Aⱼ的最小乘法次数。根据矩阵链乘法的特点,最优的划分是通过选择一个分割点k来分割区间[i,j]。递推公式如下:这一递推公式与最优二叉搜索树问题的递推公式非常相似。在计算M[1][n]的过程中,我们需要填充二维数组M的n(n-1)/2个元素,每个元素的计算都需要枚举区间[i,j-1]中所有可能的k值。因此,算法的时间复杂度为Θ(n³)。矩阵链乘法:求解示例以上述三个矩阵为例,求解过程如下:i\j12310600018000202400030通过动态规划计算,我们得到M[1][3]=18000,表示将三个矩阵相乘的最小乘法次数为18000次。动态规划的优化策略动态规划是一种强大的算法设计方法,能够有效地解决许多最优化问题。然而,直接应用动态规划方法可能会导致较高的时间和空间复杂度,限制了其在大规模问题上的实用性。时间优化降低动态规划算法的时间复杂度,使其能够在合理的时间内解决更大的问题空间优化减少空间消耗,尤其是在处理规模较大的问题时,空间的消耗可能成为限制算法可行性的瓶颈时间优化:备忘录法我们从捡硬币问题出发展开分析。如果使用从顶到下的递归法来求解,会存在同一子问题的重复求解。递归树的形状接近二叉树,树的深度为n,导致总的递归调用数接近于2ⁿ。因此,递归法的时间复杂度T(n)∈O(2ⁿ),远远慢于动态规划的线性时间复杂度。为了优化递归法的时间复杂度,我们可以通过备忘录化技术避免重复计算子问题。备忘录化是一种自顶向下的动态规划实现方法,其基本思想是将已经计算过的子问题结果保存下来,以便后续需要时直接返回,从而避免多次计算同一个子问题。备忘录法:实现方式具体来说,我们可以使用一个数组或哈希表来存储每个子问题的