【动态规划】不信看完你还不懂动态规划
1.什么是动态规划？
百科全书：动态规划（Dynamic programming, 简称DP）是一种常用的方法, 通过将整个问题分解为较小且相互独立的部分来解决复杂系统的有效策略。
使用场景： 动态规划的方法常见于解决那些具有重叠的子问题和最优子结构性质的复杂问题。
动态规划的方法通常用于将一个复杂的问题分解为多个较简单的、相互关联的子问题集合。
简而言之，在处理一个复杂的问题时，在确保各个分解出来的部分都能得到直接求解的基础上将整个大问题是动态规划所要解决的核心思想。具体而言，在面对一个问题时我们将它分解为多个小规模的问题并逐一解决这些小规模的问题之后将每个小规模的问题的答案记录下来从而避免重复计算最终通过反向利用各小规模的解答结果来构造出原始大问题是解决问题的关键方法
动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
通常这些高度相似的子问题是可以通过建立函数关系式来逐步求解的。
动态规划致力于以有序的方式解决每一个子问题，并且能够避免重复计算相同的子问题结果。
例如斐波那契数列就是典型的用于教学目的的动态规划案例。
2.动态规划3个核心点
- 界定边界的要点在于明确退出条件
- 识别最优子结构的过程包括分解成更小的子问题
- 构建状态转移方程的关键在于理解子问题与原问题之间的关联，并整合各子问题的结果以求得最终解决方案
对于这个3点，后面会做一一解释，请看我道来。
3.从「钱」讲起
在一个算法星系中，央行发行了一种特别的货币单位（奇葩币），其面值分别为一元、五元和十一元，请问如何用最少数量的货币凑出恰好十五元？
本质上来说,这个问题等同于'给定一系列可用的货币面额,计算能够组成金额n所需的最小硬币数量'
我们需要凑出一个n值。当且仅当n不等于零时，在一系列硬币中必然存在最后一个特定面值的硬币，其数值正好等于所需的目标值。例如使用集合{...}中的元素进行组合，我们可以构造出所需的数值。具体来说，在构造数值N的过程中，我们会先取出前四个元素{a,b,c,d,e}等量叠加后得到N - x的形式，并最终取出了一个{x}来达成目标数值N。
如果用 {5,5,5} 来凑15,最后一个硬币就是5,我们按照这个思路捋一捋,：
- 如果我们假设最后一个使用的硬币是11分，则余下4分。此时问题则转化为需要用现有的其他面值凑出n-11分的总值最少需要多少个硬币。当n=4时，则只能使用四个面值为1分的硬币来完成。
- 如果我们假设最后一个使用的硬币是5分，则余下的是n-5分数值的问题。而问题则转化为需要用现有的其他面值凑出这个剩余分数最少需要多少个硬币。
说明
将「复杂的大问题拆分为较小规模的相似子问题」这正是最优子结构的本质特征。我们可以通过自顶向下的方法递归地求解这些子问题，并通过这些小范围内的最优化结果来构建更大范围内的最优化结果。
这个时候我们分别假设 1、5、11 三种面值的币分别为最后一个硬币的情况：
其最后一枚硬币的价值定为 11：其最小值计算式等于 f(4) 加上一。
其最后一枚硬币的价值定为 5：其最小值计算式等于 f(9) 加上一。
其最后一枚硬币的价值定为 2：其最小值计算式等于 f(8) 加上一。
此时是否已经发现了问题的关键？在计算最少找零时（min），我们关注的是与以下三个函数解相关的参数：f(4)，f(10)，以及f(14)，其中涉及到了这三个函数解中的最小那个数值。这一数值对于确定找零方式至关重要，在于它直接关联到后续统一操作的一致性。因为后面的操作都是一样的。
假设凑的硬币总额为 n，那么 f(4) = f(n-11)、f(10) = f(n-5)、f(14) = f(n-1)，我们得出以下公式:
f(n) = min{f(n-1), f(n-5), f(n-11)} + 1我们深入探讨上面的公式中f(n-1)，计算其最少需要多少枚硬币来凑齐其最小硬币数量是否转换为如下的表达式？
f(n-1) = min{f(n-1-1), f(n-1-5), f(n-1-11)} + 1以此类推...
这确实以前学过呢,说起来就是递归啊。我们可以用递归来计算出最优找零方案。
4.递归解法
public static int coinChange(int n) {
if (n <= 0) return 0;
int min = Integer.MAX_VALUE;
if (n >= 1) {
min = Math.min(coinChange(n - 1) + 1, min);
}
if (n >= 5) {
min = Math.min(coinChange(n - 5) + 1, min);
}
if (n >= 11) {
min = Math.min(coinChange(n - 11) + 1, min);
}
return min;
}- 在n等于0的情况下直接返回0 能够显著提升程序的健壮性
- 我们将最小找零min初始化为正无穷 这一设定有助于后续使用Math.min函数求取最小值
- 假设最后一个使用的硬币面值是1分时 计算得到的当前最优解与现有最优解进行比较 并更新最小值
- 假设最后一个使用的硬币面值是5分时 计算得到的当前最优解与现有最优解进行比较 并更新最小值
- 假设最后一个使用的硬币面值是1分时 计算得到的当前最优解与现有最优解进行比较 并更新最小值
递归的弊端
我们看似已经实现了问题解决,但无需急躁,建议持续进行测试.随着n值不断增大,程序运行时间将呈现指数级增长,这将导致栈溢出情况的发生.因此,为何会产生如此冗长的运行时间?根本原因在于递归算法本身的效率低下.
在处理f(70)的计算时, 我们需要逐一分析最后一枚硬币取值为1元、5元和11元的不同情形, 而这些子问题进一步分为三个部分, 逐层展开讨论。这样的算法其时间复杂度呈指数增长（O(3ⁿ)）, 显然是一种低效的方法。
我们再仔细看图:
以红色标注的形式呈现的是同一类别的特定函数实例，在具体案例中包含了如f(64)、f(58)以及f(54)等实例均为重复运算的结果；这些仅占整个计算系统的一个小部分；然而目前系统中存在大量冗余的计算任务难以直观呈现
可见我们重复计算了非常多的无效函数，浪费了算力。
我们不妨再举一个简单的例子，比如我们要计算 「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」的和。
我们开始数数...,直到我们数出上面计算的和为 8，那么，我们再在上述 「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」 后面 「+ 1」，那么和是多少？
这个时候你肯定数都不会数，脱口而出「9」。
为什么我们在后面的计算这么快？是因为我们已经在大脑中记住了之前的结果 「8」，我们只需要计算「8 + 1」即可，这避免了我们重复去计算前面的已经计算过的内容。
我们用的递归像什么？像继续数「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」来计算出「9」，这是非常耗时的。
我们考虑使用m种不同面值的硬币来凑成金额n所需的最少硬币数量，在回溯法求解该问题时其时间复杂度达到了令人担忧的O(nᵐ)，这在所有算法中属于较为糟糕的时间复杂度情况之一。经过深入分析我们已经识别出问题的核心即大量的重复计算严重降低了算法的时间效率因此亟需采取相应的优化措施以提升算法性能
5.备忘录与递归
已知存在显著的冗余计算问题，在算法设计中可以通过维护一个备忘录记录将计算结果存储于特定的数据结构中。当需要答案时访问该备忘录以查找所需结果，并将其存储信息作为快速检索的基础从而消除重复计算带来的效率损失
有了思路后,其实在代码实现上非常简单,我们只需建立一个缓存备忘录,并在函数内部检查是否存在结果,如果存在则返回。
public class Cions {
public static void main(String[] args) {
int a = coinChange(70);
System.out.println(a);
}
private static HashMap<Integer,Integer> cache = new HashMap<>();
public static int coinChange(int amount) {
return makeChange(amount);
}
public static int makeChange(int amount) {
if (amount <= 0) return 0;
// 校验是否已经在备忘录中存在结果,如果存在返回即可
if(cache.get(amount) != null) return cache.get(amount);
int min = Integer.MAX_VALUE;
if (amount >= 1) {
min = Math.min(makeChange(amount-1) + 1, min);
}
if (amount >= 5) {
min = Math.min(makeChange(amount-5) + 1, min);
}
if (amount >= 11) {
min = Math.min(makeChange(amount-11) + 1, min);
}
cache.put(amount, min);
return min;
}
}实际上利用备忘录来解决递归重复计算的问题叫做「记忆化搜索」。
这个方法的核心目标与回溯法中的「剪枝」功能具有相同的目的性；其主要作用在于将图中所有的重复节点逐一去除，并仅保留每个节点的一个副本；然而在当前展示能力下无法完整呈现所有节点信息；经过去重处理后，则会呈现出一种线性化的结构特征：
带有记忆功能的递归方法仅达到O(n)水平的时间复杂度，并已达到了与动态规划时间复杂度相当的程度。
那这样就足够了嘛？难道非得用动态规划不可？还记得我们在上文中提到了递归的一个关键挑战吗？这个挑战由公式O(n^2)所表示。
出现栈溢出问题！由于编程语言本身的限制，在使用剪枝优化手段时，在处理超过五位数的数据时仍会出现栈溢出问题。这使得针对大规模数据集的递归运算变得不可行。
由递归计算的形式决定，在我们的这种设计中采用了「自顶向下」的方法。这种方法的具体实施是从f(70)、f(69)一直到f(1)依次分解。这种思路在其他算法中也很常见，并被分治法所采用。
由递归计算的形式决定，在我们的这种设计中采用了「自顶向下」的方法。这种方法的具体实施是从f(70)、f(69)一直到f(1)依次分解。这种思路在其他算法中也很常见，并被分治法所采用。
这种思路在此并不完全适用；因此我们应采用「自顶向下」的方法来解决这个问题；也就是说；f(1)至f(70)，以及f(69)，需通过逐步解决小规模的问题进而推进至大范围的问题；动态规划方法通常采用迭代法替代递归法来进行问题求解
除了递归结合备忘录策略之外,还存在另一个主要问题,即无法进一步优化算法性能。由此可见，在极端情况下,递归的最大深度达到n值,这与算法本身的特性直接相关。因此,为了实现高效的运行效果,系统需要使用O(n)的空间来实现递归调用。然而,这一内存需求在转换为非递归方法后将大幅减少,通过采用迭代方法，则无需如此庞大的内存需求。
6.动态规划算法
还记得上面我们如何利用备忘录缓存记录各个节点的状态信息吗？这种「备忘录」被用作一张表格来记录每个节点的状态信息，在此之后就被称为 DP table 了：DP
请注意：在图中，f[n] 表示计算凑齐n所需最小币数的函数；方框中的数值则代表了相应结果。
我们不妨在上图中找找规律?
我们观察f[1]: f[1] = min(f[0], f[-5], f[-11]) + 1
由于f[-5] 这种负数是不存在的,我们都设为正无穷大,那么f[1] = 1。
让我们详细考察一下f[5]：它等于min(f[4], f[0], f[-6]) + 1。具体来说，在计算min(f[4]=4, f[0]=0, f[-6]=∞)时会发现最小数值为0；将其结果加上1后得到最终值为1；因此可知f[5]=1。
状态转移方程
发现了吗？每一个节点都可以从前一阶段的节点进行计算得出结果，并不需要重复计算前一阶段的结果；这个相关的方程是:
f[n] = min(f[n-1], f[n-5], f[n-11]) + 1是否还记得我们在讨论动态规划时提到过存在较大的优化潜力？回溯法+记忆化搜索虽然因为回溯法本身就会导致较大的栈深度,但其所需存储空间仅为 O(n)，相比之下,迭代型动态规划的空间复杂度则为常数级别。
查看下图后可知，在计算f\left(\text{70}\right)时只需关注前三个数值f\left(\text{59}\right)、f\left(\text{69}\right)和f\left(\text{65}\right)通过应用特定公式即可得到结果；而f\left(\text{0}\right)f\left(\text{1}\right)\dotsbf\left(\text{58}\right)等值完全没有意义因此无需存储这些值以节省内存空间；从而为我们提供了优化算法的空间
上文所述的方程式就是状态转移方程式，在解决动态规划问题时，这一状态转移方程式发挥着关键作用。
显然地,即使你推导出动态转移方程,也不足以保证能够解决所有动态规划问题。然而,尽管存在许多推导出转移方程的人。这背后的原因在于未正确处理边界条件。
边界问题
一部分的问题其实我们在上文已经给出了解决方案。针对这个找零的情况我们需要考虑下面列举的一些边界条件。
处理f[n]中n为负数的问题：
规定当n为负数时,f[n]被定义为其值趋于正无穷。
由于通常不会存在数组下标为负数的情况,n取负值时f[n]实际上并不存在。
由于要求最少找零的原因,我们需要排除这些不可能存在的n取负值的情况，并简化计算过程。
我们直接将其定义为正无穷大，并以此为基础方便地实现动态规划转移方程。
处理f[n]中n为0的问题
n=0的情况被视为动态转移方程的基础状态设定。
这些特殊情形通常表现为无从下手的状态，在这种情况下就需要设定初始条件。
如果缺少这一项基础设定的话，那么我们的递归公式就会变成f[0]=\min(f[-1],f[-5],f[-11])+1。
尽管如此，在某些极端情况下（比如所有可能值都未被初始化时），数值会默认取到一个极大值（如正无穷），这使得这类问题难以直接求解。因此，在编程实现时必须人为地补充这些基础状态。
处理好边界问题我们就可以得到完整的动态转移方程了:
f[0] = 0 (n=0) f[n] = min(f[n-1], f[n-5], f[n-11]) + 1 (n>0)那么让我们重新考虑一下这个找零问题，在本次假设中我们将给出不同面额的硬币coins以及一个具体的总金额amount。我们的目标是设计一个算法来求解能够达到目标金额所需的最少硬币数量。如果经过计算仍然无法找到有效的组合则返回-1
比如输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 复制代码
实际上，在之前我们处理过的找零问题中存在一种普遍性。我们的币种已经固定下来了，具体包括1元、5元和11元等。然而这一次改变了规则，在新的系统中采用了一个名为coins的一组新的面额组合。
我们重新理一下思路：
- 涉及最优子结构: 其核心在于原问题的解可由各子问题的最优解组合而成。基于假设我们需要至少k个硬币来凑出总面额n，则目标函数f(n)等于各选项中最小值。
- 解决边界条件: 这部分较为直接，在数学上我们规定当n为负值时返回正无穷大，在实际应用中则认为无法用零枚硬币凑出零元。
- 构建动态规划转移方程: 初始状态设定为f[0]=0（表示凑出零元所需硬币数量），递推关系式则定义为对于所有正整数n有f[n]=min{f[n−c_i]}+1（表示最少需要多少枚硬币）。
我们根据上面的推导,得出以下代码:
public int coinChange(int[] coins, int amount) {
// 初始化备忘录,用amount+1填满备忘录,amount+1 表示该值不可以用硬币凑出来
int[] dp = new int[amount + 1];
Arrays.fill(dp,amount+1);
// 设置初始条件为 0
dp[0]=0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
// 根据动态转移方程求出最小值
if(coin <= i) {
dp[i]=Math.min(dp[i],dp[i-coin]+1);
}
}
}
// 如果 `dp[amount] === amount+1`说明没有最优解返回-1,否则返回最优解
return dp[amount] == amount+1 ? -1 : dp[amount];
}7.小结
我们总结一下学习历程：
- 经过深入研究后发现采用递归方式能够攻克最少找零问题。
- 但经过算法复杂度分析和实际测试后发现采用递归方法效率低下，并且亟需寻找其他解决方案。
- 通过结合备忘录技术和优化后的递归策略，在一定程度上降低了时间复杂度。
然而自顶向下的思路导致了程序崩溃风险因此转而采用自底向上的方法。 - 运用动态规划中的转移方程 并采用迭代算法逐步推导出最优解。
动态规划本质上是经过反复优化的传统暴力方法。
运用动态规划方法可以消除大量重复计算的子问题。
在接下来讨论的所有与动态规划相关的题目中,其解题思路均可以从传统暴力方法逐步演进至动态规划策略。
可能你会问面试题这么多,到底哪一道应该用动态规划?如何判断?
一种有效的方法就是对题目中所提出的问题进行分析与研究；具体来说,就是要探索该问题是否能够被分解为若干个子问题,并进一步考察这些子问题是如何关联以及能否通过解决这些子问題进而推导出原题的答案.
不过先前介绍的那种方法具有较高的准确性，并且要求我们具备一定的经验和基础储备。或者采用另一种更为简便的方式——即尽管这种思路略显不够严谨但仍能快速解决问题——来判断一个问题是否属于动态规划范畴
- 求最大值，最小值
- 判断方案是否可行
- 统计方案个数
参考文档：