《动态规划类算法》课件

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