动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说求最长递增子序列呀,最小编辑距离呀等等。
既然是要求最值,核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值呗。
动态规划基本概念
动态规划(Dynamic Programming,简称DP)算法是一种解决复杂问题的算法设计和优化技术,常用于解决具有重叠子问题性质和最优子结构性质的问题。它的核心思想是将一个大问题分解成一系列相互重叠的子问题,然后将子问题的解存储起来,以避免重复计算,从而节省时间。
动态规划算法通常包括以下关键步骤:
- 定义子问题:将原问题分解成若干个子问题,并明确定义每个子问题的输入和输出。
- 构建状态转移方程:确定每个子问题与其他子问题之间的关系,即如何通过已解决的子问题来解决当前子问题。这通常通过递归或迭代方式建立状态转移方程。
- 初始化:初始化基本情况,通常是问题规模较小或无法再分时的边界情况。
- 自底向上求解或使用备忘录法:根据状态转移方程,从最小的子问题开始解决,逐步构建出更大规模的问题的解。可以使用自底向上的迭代方法或备忘录法来避免重复计算。
- 返回结果:根据状态转移方程求解出原问题的解。
动态规划广泛应用于各种领域,包括算法设计、优化问题、路径规划、序列比对、字符串处理、游戏策略等。经典的动态规划问题包括斐波那契数列、背包问题、最长公共子序列、最短路径问题。
动态规划的优点是可以显著减少重复计算,提高效率,但其缺点是需要合理定义子问题和状态转移方程,有时需要额外的内存空间来存储中间结果。因此,在解决问题时,需要仔细分析问题的性质,确定是否适合使用动态规划算法。
问题类型:一个模型三个特征
什么样的问题适合用动态规划来解决呢?换句话说,动态规划能解决的问题有什么规律可循呢?这部分理论可以总结为“一个模型三个特征”。
一个模型
首先,我们来看,什么是“一个模型”?它指的是动态规划适合解决的问题的模型。我把这个模型定义为多阶段决策最优解模型,我们一般是用动态规划来解决最优问题。
解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值。
三个特征
什么是“三个特征”?它们分别是最优子结构、无后效性和重复子问题
1 最优子结构
最优子结构指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。如果我们把最优子结构,对应到我们前面定义的动态规划问题模型上,那我们也可以理解为,后面阶段的状态可以通过前面阶段的状态推导出来。最优子结构,就是目前的最优解可以由以前的最优解推导出来,也就是存在状态转移公式
2 无后效性
无后效性有两层含义,第一层含义是,在推导后面阶段的状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步一步推导出来的。第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型,其实基本上都会满足无后效性。无后效性 其实就是当前状态与路径无关、当前的决定不受后面的影响,子问题的最优决策只与子问题自己相关,与原始问题无关,解决子问题时候不用考虑原始问题,就和递归只要考虑当前层状态和处理一样
3 重复子问题
不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态
动态规划解题框架
虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事:
- 需要熟练掌握递归思维,只有列出正确的「状态转移方程」,才能正确地穷举。
- 需要判断算法问题是否具备「最优子结构」,是否能够通过子问题的最值得到原问题的最值。
- 动态规划问题存在「重叠子问题」,如果暴力穷举的话效率会很低,所以需要使用「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算
以上最难的是写出状态转移方程,给出一个思维框架
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义,按上面的套路走,最后的解法代码就会是如下的框架
# 自顶向下递归的动态规划 def dp(状态1, 状态2, ...): for 选择 in 所有可能的选择: # 此时的状态已经因为做了选择而改变 result = 求最值(result, dp(状态1, 状态2, ...)) return result # 自底向上迭代的动态规划 # 初始化 base case dp[0][0][...] = base case # 进行状态转移 for 状态1 in 状态1的所有取值: for 状态2 in 状态2的所有取值: for ... dp[状态1][状态2][...] = 求最值(选择1,选择2...)
示例:暴力递归
首先看一个斐波那契数列的暴力递归方法:
int fib(int N) { if (N == 1 || N == 2) return 1; return fib(N - 1) + fib(N - 2); }
这个递归树怎么理解?就是说想要计算原问题 f(20),我就得先计算出子问题 f(19) 和 f(18),然后要计算 f(19),我就要先算出子问题 f(18) 和 f(17),以此类推。最后遇到 f(1) 或者 f(2) 的时候,结果已知,就能直接返回结果,递归树不再向下生长了
递归算法的时间复杂度怎么计算?就是用子问题个数乘以解决一个子问题需要的时间
首先计算子问题个数,即递归树中节点的总数。显然二叉树节点总数为指数级别,所以子问题个数为 O(2^n)。然后计算解决一个子问题的时间,在本算法中,没有循环,只有 f(n - 1) + f(n - 2) 一个加法操作,时间为 O(1)。
所以,这个算法的时间复杂度为二者相乘,即 O(2^n)
,指数级别,爆炸,观察递归树,很明显发现了算法低效的原因:存在大量重复计算,比如 f(18) 被计算了两次,而且你可以看到,以 f(18) 为根的这个递归树体量巨大,多算一遍,会耗费巨大的时间。更何况,还不止 f(18) 这一个节点被重复计算,所以这个算法及其低效。
这就是动态规划问题的第一个性质:重叠子问题
自顶向下:递归+备忘录
即然耗时的原因是重复计算,那么我们可以造一个「备忘录」,每次算出某个子问题的答案后别急着返回,先记到「备忘录」里再返回;每次遇到一个子问题先去「备忘录」里查一查,如果发现之前已经解决过这个问题了,直接把答案拿出来用,不要再耗时去计算了。
一般使用一个数组充当这个「备忘录」,当然你也可以使用哈希表(字典),思想都是一样的
int fib(int N) { // 备忘录全初始化为 0 int[] memo = new int[N + 1]; // 进行带备忘录的递归 return dp(memo, N); } // 带着备忘录进行递归 int dp(int[] memo, int n) { // base case if (n == 0 || n == 1) return n; // 已经计算过,不用再计算了 if (memo[n] != 0) return memo[n]; memo[n] = dp(memo, n - 1) + dp(memo, n - 2); return memo[n]; }
实际上,带「备忘录」的递归算法,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数
子问题个数,即图中节点的总数,由于本算法不存在冗余计算,子问题就是 f(1), f(2), f(3) … f(20),数量和输入规模 n = 20 成正比,所以子问题个数为 O(n)。解决一个子问题的时间,同上,没有什么循环,时间为 O(1),所以,本算法的时间复杂度是 O(n),比起暴力算法,是降维打击
自底向上:状态转移表法(DP Table)
带备忘录的递归和常见的动态规划解法已经差不多了,只不过这种解法是「自顶向下」进行「递归」求解,我们更常见的动态规划代码是「自底向上」进行「递推」求解
注意我们刚才画的递归树(或者说图),是从上向下延伸,都是从一个规模较大的原问题比如说 f(20),向下逐渐分解规模,直到 f(1) 和 f(2) 这两个 base case,然后逐层返回答案,这就叫「自顶向下」。
啥叫「自底向上」?反过来,我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)(base case)开始往上推,直到推到我们想要的答案 f(20)。这就是「递推」的思路,这也是动态规划一般都脱离了递归,而是由循环迭代完成计算的原因
有了上一步「备忘录」的启发,我们可以把这个「备忘录」独立出来成为一张表,通常叫做 DP table,在这张表上完成「自底向上」的推算
int fib(int N) { if (N == 0) return 0; int[] dp = new int[N + 1]; // base case dp[0] = 0; dp[1] = 1; // 状态转移 for (int i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[N]; }
实际上,带备忘录的递归解法中的那个「备忘录」memo 数组,最终完成后就是这个解法中的 dp 数组
什么是状态转移方程?把参数 n 想做一个状态,这个状态 n 是由状态 n - 1 和状态 n - 2 转移(相加)而来,这就叫状态转移,仅此而已。 你会发现,上面的几种解法中的所有操作,例如 return f(n - 1) + f(n - 2),dp[i] = dp[i - 1] + dp[i - 2],以及对备忘录或 DP table 的初始化操作,都是围绕这个方程式的不同表现形式
根据斐波那契数列的状态转移方程,当前状态 n 只和之前的 n-1, n-2 两个状态有关,其实并不需要那么长的一个 DP table 来存储所有的状态,只要想办法存储之前的两个状态就行了
int fib(int n) { if (n == 0 || n == 1) { // base case return n; } // 分别代表 dp[i - 1] 和 dp[i - 2] int dp_i_1 = 1, dp_i_2 = 0; for (int i = 2; i <= n; i++) { // dp[i] = dp[i - 1] + dp[i - 2]; int dp_i = dp_i_1 + dp_i_2; // 滚动更新 dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i_1; }
所以,可以进一步优化,把空间复杂度降为 O(1)
动态规划解题基本步骤及应用领域
动态规划(Dynamic Programming,简称DP)是一种解决复杂问题的算法设计技术,常用于优化问题和组合问题的求解。它通过将原问题分解成子问题,并保存子问题的解,以避免重复计算,从而提高算法的效率。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。
动态规划的基本思想可以总结为以下几个步骤:
- 定义问题的状态:首先要明确定义问题的状态,这些状态可以用来描述问题的各种情况。
- 找到状态转移方程:状态转移方程描述了问题之间的联系,即如何从一个状态转移到另一个状态。这通常涉及到问题的递归关系,通过这个关系可以从较小规模的子问题得到更大规模的问题的解。
- 初始化状态:确定初始状态的值,这通常是问题规模最小的情况下的解。
- 自底向上或自顶向下求解:动态规划可以采用自底向上(Bottom-Up)或自顶向下(Top-Down)的方式求解问题。自底向上是从最小的状态开始逐步计算,直到得到最终问题的解;自顶向下是从最终问题开始,递归地计算子问题的解,直到达到最小状态。
- 根据问题的要求,从状态中找到最终解。
动态规划常见的应用领域包括:
- 最长公共子序列问题:在两个序列中找到一个最长的共同子序列,用于比较字符串相似性。
- 背包问题:在给定一定容量的背包和一组物品的情况下,选择一些物品放入背包,使得物品的总价值最大或总重量不超过背包容量。
- 最短路径问题:求解图中两点之间的最短路径,如Dijkstra算法和Floyd-Warshall算法。
- 硬币找零问题:给定一组硬币面额和一个目标金额,找到使用最少数量的硬币组合成目标金额。
- 斐波那契数列问题:求解斐波那契数列的第n个数,通过动态规划可以避免重复计算。
动态规划是一种强大的问题求解方法,但它并不适用于所有类型的问题。在使用动态规划时,需要仔细分析问题的性质,确保问题具有重叠子问题和最优子结构性质,以确保动态规划算法能够有效地解决问题。
贪心算法、动态规划、回溯算法
这三个算法解决问题的模型,都可以抽象成多阶段决策最优解模型,
- 回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题,我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况,然后对比得到最优解。不过,回溯算法的时间复杂度非常高,是指数级别的,只能用来解决小规模数据的问题。对于大规模数据的问题,用回溯算法解决的执行效率就很低了。解决最多的问题,性能最差
- 尽管动态规划比回溯算法高效,但是,并不是所有问题,都可以用动态规划来解决。能用动态规划解决的问题,需要满足三个特征,最优子结构、无后效性和重复子问题。在重复子问题这一点上,动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相反,动态规划之所以高效,就是因为回溯算法实现中存在大量的重复子问题。解决较多的问题,性能较好
- 贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效,代码实现也更加简洁。不过,它可以解决的问题也更加有限。它能解决的问题需要满足三个条件,最优子结构、无后效性和贪心选择性(这里我们不怎么强调重复子问题)。其中,最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是,通过局部最优的选择,能产生全局的最优选择。每一个阶段,我们都选择当前看起来最优的决策,所有阶段的决策完成之后,最终由这些局部最优解构成全局最优解,解决最少的问题,性能最好
动态规划、递归、分治的区别
下面是动态规划、递归和分治这三种算法的相同点和不同点的表格展示:
特点 | 动态规划 | 递归 | 分治 |
求解方式 | 自底向上 | 自顶向下 | 分而治之 |
重复计算处理 | 避免重复计算,通过存储子问题的解来提高效率 | 可能重复计算相同的子问题 | 分解问题并独立处理子问题 |
时间复杂度 | 通常具有较低的时间复杂度 | 可能具有较高的时间复杂度 | 通常具有中等的时间复杂度 |
适用性 | 适用于具有重叠子问题性质和最优子结构性质的问题 | 适用于结构天然呈递归性质的问题 | 适用于问题可以分解为独立的子问题 |
经典问题举例 | 背包问题、最短路径问题、斐波那契数列等 | 树形结构的问题、图遍历等 | 快速排序、归并排序等 |
记忆化/缓存 | 通过存储中间结果,具有记忆化的特点 | 可以使用记忆化技巧来减少重复计算 | 分治通常不涉及记忆化 |
稳定性 | 具有稳定性,不受输入数据顺序影响 | 可能受输入数据顺序影响 | 通常具有稳定性,不受输入数据顺序影响 |
这个表格概括了动态规划、递归和分治算法之间的一些主要相同点和不同点。需要注意的是,这些算法的选择取决于具体问题的性质和要求,有时候也可以根据问题的特点将它们结合使用,以获得更好的性能和效果。
动态规划、递归、分治处理的题目分类
适用于这些算法思想的题目
动态规划处理的高频算法题
动态规划是一个非常强大的算法技巧,适用于解决各种高频的算法问题。以下是一些使用动态规划解决的常见高频算法题目:
- 斐波那契数列问题:计算斐波那契数列的第n个数,可以使用动态规划来避免指数级的重复计算。
- 背包问题:如 0-1 背包问题、完全背包问题、多重背包问题等,动态规划可用于优化资源分配问题。
- 最长公共子序列问题:寻找两个字符串的最长公共子序列,动态规划可用于解决字符串匹配和相似性比较问题。
- 最长递增子序列问题:寻找一个数组中最长的递增子序列,常用于优化问题和排序问题。
- 最短路径问题:如 Dijkstra 算法、Floyd-Warshall 算法,用于在图中找到最短路径或最短距离。
6. 编辑距离问题:计算两个字符串之间的最小编辑操作数,如插入、删除和替换操作。
7. 股票买卖问题:寻找股票价格数组中的最佳买卖时机,以获得最大的利润。
- 子集和问题:确定给定集合中是否存在一个子集,其元素之和等于特定目标值。
- 矩阵链乘法问题:在给定一组矩阵的情况下,确定它们相乘的最佳顺序以最小化乘法运算的次数。
- 字符串匹配问题:如正则表达式匹配、通配符匹配等,用于模式匹配和文本搜索。
这些问题只是动态规划可以解决的众多示例之一。动态规划的思想可以应用于各种优化和最优化问题,它的关键是将问题分解成子问题并找到适当的状态转移规则。因此,当你面对一个复杂的问题时,考虑是否可以使用动态规划来提高问题求解的效率和准确性。
分治算法处理的高频算法题
分治算法是一种重要的算法技巧,适用于解决各种高频的算法问题,特别是分而治之的思想。以下是一些使用分治算法解决的常见高频算法题目:
- 归并排序:分治算法的经典示例之一,用于将一个大数组分割成较小的子数组,排序子数组,然后将它们合并以得到有序数组。
- 快速排序:另一种基于分治思想的排序算法,通过选择一个基准元素,将数组划分成两个子数组,然后递归地对子数组进行排序。
- 连续子数组的最大和:给定一个整数数组,查找具有最大和的连续子数组。分治算法可以用于高效解决这个问题。
- 求解最近点对问题:给定一个包含多个点的平面,找到最接近的一对点。该问题可以通过分治算法以较低的时间复杂度解决。
- 矩阵乘法:分治算法可以用于将矩阵分割成子矩阵,然后递归地进行矩阵乘法操作,以减少计算次数。
- 大整数乘法:用于计算两个大整数的乘积,分治算法可以用于将大整数分解为较小的整数,并递归地计算它们的乘积。
- 众数问题:查找数组中出现次数超过一半的元素,分治算法可以在线性时间内解决这个问题。
- 合并K个有序链表:将K个有序链表合并为一个有序链表,分治算法可以用于高效解决这个问题。
- 寻找第K大/小的元素:在一个未排序的数组中找到第K大或第K小的元素,分治算法可以用于解决这个问题。
- 求解凸多边形的最小包围矩形:给定一个凸多边形,找到包围它的最小矩形。分治算法可用于高效计算最小包围矩形。
这些问题只是分治算法可以解决的众多示例之一。分治算法的关键思想是将问题分解为相互独立的子问题,然后将子问题的解合并以得到原问题的解。当你面对一个需要分而治之的问题时,考虑是否可以使用分治算法来提高问题求解的效率和准确性。
递归算法处理的高频算法题
递归算法是一种常见且强大的算法技巧,适用于解决各种高频的算法问题。以下是一些使用递归算法解决的常见高频算法题目:
- 二叉树遍历:包括前序遍历、中序遍历、后序遍历等,用于访问和处理二叉树的节点。
- 分解问题:许多问题可以通过将它们分解为更小的相似子问题来解决,例如斐波那契数列、汉诺塔问题等。
- 递归的数据结构:如链表、树、图等数据结构的处理通常使用递归来实现。
- 组合和排列问题:生成所有可能的组合或排列,如子集生成、排列生成等。
- 回溯算法:解决一些组合优化问题,如八皇后问题、数独问题等。
- 图的遍历:深度优先搜索(DFS)和广度优先搜索(BFS)是递归的常见应用,用于解决图相关的问题。
- 递归的搜索和查找:二分查找、树的搜索、图的最短路径等问题可以使用递归算法解决。
- 分治算法:分治算法的核心思想就是递归,如归并排序、快速排序等。
- 递归背包问题:解决背包问题的变种,如动态规划中的背包问题。
- 字符串处理:字符串匹配、编辑距离、正则表达式匹配等问题通常可以使用递归来解决。
这些问题只是递归算法可以解决的众多示例之一。递归算法的关键思想是将问题分解为更小的相似问题,并通过递归调用自身来解决这些子问题。当你面对一个需要不断分解问题的情况时,考虑是否可以使用递归来解决,但需要小心避免无限递归,确保有适当的终止条件。