《动态规划类算法》课件

动态规划类算法动态规划算法是一种解决优化问题的方法，它将问题分解成子问题，并利用子问题的解来构建最终解什么是动态规划核心思想优化策略将复杂问题分解成更小的子问题，并存储子问题的解，以通过记录已解决子问题的解，动态规划可以有效地避免重避免重复计算复计算，提高算法效率动态规划的基本思想将复杂问题分解为子问题存储子问题的解，避免重复计算自底向上，逐步构建最优解动态规划问题的特点最优子结构重叠子问题12问题的最优解可以由子问在求解过程中，会多次遇题的最优解组合而成到相同的子问题无后效性3子问题的解一旦确定，就不会再改变动态规划算法的基本步骤定义状态确定问题的子问题，并定义一个状态变量来表示子问题的结果例如，在计算斐波那契数列中，状态变量可以表示第n个斐波那契数确定初始状态确定一些最基本子问题的解，并将其作为初始状态值例如，在斐波那契数列中，f0=0,f1=1建立状态转移方程找出当前状态的值如何由之前的状态计算得出例如，在斐波那契数列中，fn=fn-1+fn-2计算最终结果根据状态转移方程递归地计算所有状态的值，最终得到问题的解如何建立动态规划的状态转移方程定义子问题寻找递推关系建立状态转移方程首先要确定问题的子问题，即状态找到当前子问题的解与之前子问题的将递推关系用数学公式表示出来，即解之间的关系状态转移方程动态规划算法的时间复杂度ON ON^2线性复杂度平方复杂度例如，斐波那契数列的动态规划例如，最长公共子序列的动态规实现划实现ON*M二维复杂度例如，01背包问题的动态规划实现动态规划的基本模型斐波那契数列凑零钱问题计算第n个斐波那契数，经给定不同面额的硬币和一个典的动态规划问题总金额，求最少硬币数量的组合最长公共子序列背包问题01找出两个字符串的最长公共给定容量为W的背包和n个子序列物品，每个物品有重量和价值，求背包所能装的最大价值斐波那契数列斐波那契数列是一个经典的动态规划问题它定义为F0=0，F1=1，Fn=Fn-1+Fn-2n=2动态规划的思路是利用之前计算过的结果来加速当前状态的计算，避免重复计算凑零钱问题假设你有一个装满了硬币的钱包，每种硬币都有无限个你想要找到用这些硬币凑成特定金额的最少硬币数量例如，如果你需要凑出11美元，并且你的钱包里有1美元、2美元、5美元和10美元的硬币，那么最少需要用3枚硬币来凑成11美元（一枚10美元硬币和一枚1美元硬币）最长公共子序列定义应用一个序列S的子序列是指从S中删除若干个字符后剩余的字符序列LCS问题广泛应用于生物信息学、文本编辑、软件工程等领域例，例如，ABCBDAB的子序列有ABAD,BCDA等，而ACBD不如，在DNA序列比对中，LCS可以用来识别两个DNA序列的相似是子序列给定两个字符串X和Y，求解X和Y的最长公共子序列性Longest CommonSubsequence,LCS，即长度最大的公共子序列背包问题01给定一个容量为W的背包，和N个物品每个物品有两个属性价值Vi和重量Wi问如何选择物品放入背包，使得背包中物品的总价值最大01背包问题要求对于每个物品，只有两种选择选或者不选，不能选择部分物品完全背包问题完全背包问题是动态规划中一个经典问题，它允许物品可以无限次地被放入背包中给定一个容量为W的背包和n个物品，每个物品都有重量wi和价值vi，求解如何选择物品放入背包中，使得背包中物品的总价值最大最长递增子序列最长递增子序列问题是指在一个序列中找到最长的递增子序列例如，序列{1,3,2,4,5}的最长递增子序列为{1,2,4,5}该问题可以采用动态规划的思想来解决，将最长递增子序列问题分解成子问题，然后使用子问题的解来解决原问题最短路径问题导航应用程序网络路由从起点到终点找到最佳路线在网络中找到数据包传输的最短路径编辑距离问题编辑距离，又称为莱文斯坦距离，用于衡量两个字符串之间的差异程度它指的是将一个字符串转换为另一个字符串所需的最少编辑操作次数，包括插入、删除和替换状态压缩动态规划将状态信息压缩成一个整数表示利用位运算进行状态压缩，提高，用于存储状态信息算法效率常用于解决一些与集合相关的动态规划问题树形动态规划树形结构状态转移树形动态规划适用于解决树形结构上的问题，通常需要对状态转移方程通常依赖于子节点的信息，通过自底向上或每个节点进行遍历和计算自顶向下的方式进行动态规划计算区间动态规划定义特点区间动态规划通常用于解决与区区间动态规划通常使用一个二维间相关的优化问题，例如求解最数组dp[i][j]来存储从i到j区间优区间划分、最长公共子序列等的最优解，其中i和j分别代表区问题这种方法通过将整个区间间的起点和终点状态转移方程划分为多个子区间，递归地求解通常是根据子区间的最优解递归子区间的最优解，最终合并得到定义的全局最优解应用区间动态规划广泛应用于各种领域，例如字符串处理、序列比对、图像处理等例如，最长公共子序列问题，可以通过区间动态规划方法高效地求解位运算优化动态规划状态压缩效率提升12将集合或状态表示成二进位运算比传统的循环枚举制数，用位运算进行状态更高效，可大幅减少代码的枚举和转移量，提高算法速度适用场景3适用于状态空间较小，且状态之间存在相互依赖关系的问题多重背包问题每个物品有多个，例如3个苹果需要考虑每个物品的数量限制，，2个梨并寻找最优的装包方案可以用动态规划解决，需要将物品数量作为状态的一维字符串动态规划子串匹配最长公共子串例如，判断字符串s是否包例如，求两个字符串的最长含字符串t公共子串编辑距离例如，求两个字符串之间的编辑距离数位动态规划数字范围限制状态定义与转移12适用于统计满足特定条件通常使用dp[i][j]表示从的数字个数，例如在给定高位到第i位，且当前位范围内，统计所有包含特数字为j的所有数字的个定数字的数字的个数数边界条件处理3需要根据具体问题设置边界条件，例如第一个数字是否可以为0，是否允许前导零等概率动态规划概率转移期望值应用场景概率动态规划基于概率转移，将问题通过计算每个子问题的期望值，最终概率动态规划广泛应用于金融、游戏分解为多个子问题，每个子问题都有得到整个问题的期望值、生物信息学等领域不同的概率股票买卖问题最佳买卖时机交易次数限制在给定的时间范围内，找到可能限制交易次数，例如只买入和卖出股票的最佳时机能进行一次交易或最多两次，以最大化利润交易冷冻期在卖出股票后，可能需要等待一定时间才能再次买入子集背包问题子集选择容量限制动态规划求解从所有物品中选择一个子集，使总价值最大子集的总重量不能超过背包的容量利用动态规划，枚举所有子集，找到最优解泰波那契数列泰波那契数列类似于斐波那契数列，但它以三个初始值开始，每个后续数字是前三个数字之和例如，泰波那契数列的前几个项是

0、

1、

1、

2、

4、

7、

13、

24、

44、81数塔问题描述思路一个数字金字塔，从塔顶开始，每次可以向下移动到下一层从塔底向上递推，每个位置的数字和等于其下面两个位置的的相邻位置，求从塔顶到塔底的路径的最大数字和最大数字和加上当前位置的值，最终得到塔顶位置的最大数字和最小生成树问题最小生成树MST问题是在一个带权无向图中寻找一棵包含所有顶点的生成树，且树的总权重最小常用的算法有Kruskal算法和Prim算法Kruskal算法基于贪心策略，每次选择权重最小的边，并加入到生成树中，直到所有顶点都被连接Prim算法从一个顶点开始，每次选择权重最小的边，并连接到生成树中，直到所有顶点都被连接单调队列优化动态规划单调队列优化时间复杂度在动态规划中，当状态转移通过维护一个单调队列，可方程需要用到之前若干个状以将状态转移方程的时间复态的值时，可以使用单调队杂度从On降至O1列来优化滑动窗口单调队列可以用于解决滑动窗口问题，例如求解一个窗口中最大值或最小值总结优势应用动态规划是一种强大的算法技巧，适用于解决各种优化问动态规划在计算机科学、工程、金融、生物学等领域都有题它通过分解问题，存储中间结果，并避免重复计算，广泛应用，例如最短路径、最优资源分配、投资策略等以高效地找到最佳解决方案。