一文读懂动态规划---图文详解
一、动态规划
动态规划（Dynamic Programming, DP）作为运筹学的重要分支，在解决复杂系统中的最优决策序列方面发挥着关键作用。上世纪五十年代初期，在美国数学家理查德·贝尔曼（Richard Bellman）等人的深入研究下，“最优化原理定理”应运而生，并奠定了动态规划理论的基础。该方法不仅在工程技术领域具有广泛应用，在工程设计与管理方面也取得了显著成效——例如，在设备更新与维护策略制定中发挥重要作用，在生产调度与库存控制方面展现出独特优势，并在资源分配与项目管理中展现出巨大潜力。此外，在经济领域，“背包问题”的最优解法为资源有限条件下收益最大化提供了重要思路；而在工业生产管理方面，则通过建立需求预测模型实现科学化运营支持；同时，在军事领域，“旅行商问题”的解决方案为供应链网络优化提供了理论支撑；最后，在自动化控制系统设计中，“最长路径分析”方法被广泛应用于系统可靠性提升。
动态规划算法在本质上与分治法有相似之处，并都基于将复杂问题分解为简单子问题的原则。然而，在具体实施方式上存在显著差异。动态规划算法的核心思想在于将待解决的问题划分为若干个子问题，并分别求解每个子问题。与分治法不同之处在于，在于适合采用动态规划方法解决的问题往往存在大量相互重叠的子问题。如果直接应用分治法来解决这类问题，则会导致重复计算同一个子问题多次出现的现象。为了避免这种冗余计算带来的效率低下，在实际应用中我们通常会采用一种叫做记忆化存储的方法（memoryized storage），即在计算过程中记录下已经解决过的问题答案，并在后续计算中能够快速调用这些结果而不必重新进行重复计算。这种方法的核心优势在于通过存储已知的结果来减少重复计算的数量，在保证正确性的前提下显著提高了算法的时间效率
动态规划算法的核心在于消除重复计算的问题，在这种情况下成为解决复杂优化问题的重要方法。将复杂的问题拆分为多个相互独立的小规模子问题后进行求解，并记录每个子problem的解决方案以避免repeated calculations，在众多可行方案中选择最优solution。
二、两个动态规划的基本例子
最优解法：对于任何一个实例的最佳解决方案而言，在该实例下所有可能的解中都存在一个构成该方案的基础结构。
币值最大化问题 假设有排成一行的n枚硬币（n≥1），它们的面值分别为c₁, c₂, …, cₙ（其中每个c_i均为正整数），且其中某些可能相等。那么如何选择一组硬币使得这组所选硬币之间任意两个都不相邻的同时又能使总金额达到最大值？
首先，根据动态规划的定义，将该问题划分为两个子问题：
包含的最后一枚硬币为n时，则有：最后一位硬币为n的情况下（即第(n-1)位），前(n-1)位的最大总价值相当于整个前n位的最大总价值；
排除了最后一位硬币为n的情况后，则有：在排除了第(n)位的情况下（即仅考虑前(n-1)位），其最大总价值相当于整个前n位的最大总价值；
取决于第 (n-1) 枚硬币的状态, 我们可以将前 (n-1) 枚硬币的币值最大化问题划分为两个子问题; 类似地, 继续递归求解, 直到确定前0枚硬币的最大值为0
现在，假设有一排硬币 5, 1, 2, 10, 6, 2，求该组硬币的最大化：
用Ci表示第 i 枚硬币，F(n) 表示前 n 个硬币中最大值，规定 F(0) = 0 ;
- F(6) = max{F(5), F(4) + C6};
- F(5) = max{F(4), F(3) + C5};
- F(4) = max{F(3), F(2) + C4};
- F(3) = max{F(2), F(1) + C3};
- F(2) = max{F(1), F(0) + C2};
- F(1) = max{F(0), C1};
- F(0) = 0;
从以上式子可以看出，在没有进行任何记录操作的情况下，该式子呈现出与递归调用极为相似的特点。如果不进行任何记录操作的话，在这种情况下就会导致进行了大量的重复计算。
这种情况极大程度上增加了计算时间消耗。
所以，在应用动态规划时我们有必要设立一个额外的数据结构用于存储已经解决过的问题，并通过这种方法从而消除重复计算的问题。由此可见，在应用动态规划时我们实际上是在用额外的空间来换取更快捷的运算速度。
代码如下：
public class Main{
static int[] c = {5,1,2,10,6,2};
static int[] F = new int[c.length];
public static void main(String[] args){
Func(c.length-1);
System.out.println(Arrays.toString(c));
System.out.println(Arrays.toString(F));
}
/** * 递归三部曲：
* 1.确定参数与返回类型
* 2.确定终止条件
* 3.确定单体循环
* @author Ye
* @return
*/
public static int Func(int n)
{
if(n<0) return 0;
if(F[n]!=0) return F[n];
F[n] = Math.max(Func(n-1), Func(n-2)+c[n]);
return F[n];
}
}输出：硬币[5, 1, 2, 10, 6, 2]
最大值[5, 5, 7, 15, 15, 17]
例2、找零问题 ：需找零金额为 n ，最少要用多少枚硬币？硬币面值d1 < d2 < d3 < ··· < dm，规定d1 = 1；
n表示需要找零的具体金额；F(n)代表在找零金额为n的情况下所需的最小硬币数量；假设可用的硬币面值为1元、2元和5元，请计算当n=7时的F(n)值；
首先需要确定n是否能通过这些硬币中的某些组合来实现找零 即n的值必须至少等于这三种硬币中的一种或几种的总和 也就是说我们可以将这个问题分解为多个子问题：
最小零钱找零的数量包含第一种情况, 即计算公式为 F₇ = F₆ + 1, 其中第一个数字"1"表示所用面值, 第二个数字"1"则表示所用数量.
同样的,
最小零钱找零的数量包含另一种情况,
即计算公式为 F₇ = F₅ + 1,
其中第一个数字"2"表示所用面值,
第二个数字"1"则表示所用数量.
同样地,
最小零钱找零的数量也包含第三种情形,
即计算公式为 F₇ = F₂ + 1,
其中第一个数字"5"表示所用面值,
第二个数字"1"则表示所用数量.
所以，找零问题可拆分为若干个子问题：
- F(7) = min{F(7 - 1), F(7 - 2), F(7 - 5) } + 1 ；
- F(6) = min{F(6 - 1), F(6 - 2), F(6 - 5) } + 1 ；
- F(5) = min{F(5 - 1), F(5 - 2), F(5 - 5) } + 1 ；
- F(4) = min{F(4 - 1), F(4 - 2) } + 1 ；
- F(3) = min{F(3 - 1), F(3 - 2) } + 1 ；
- F(2) = min{F(2 - 1), F(2 - 2) } + 1 ；
- F(1) = min{F(1 - 1) } + 1 ；
- F(0) = 0 ；
同理
代码如下：
public class Main{
static int[] d = {1,2,5};
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] F = new int[n+1];
Func(n,F);
System.out.println(Arrays.toString(F));
System.out.println("找零问题："+n+" 需要硬币"+F[n]+"枚。");
}
/** * 递归三部曲：
* 1.确定参数与返回类型
* 2.确定终止条件
* 3.确定单体循环
* @param Ye
* @return
*/
public static int Func(int n,int[] F)
{
if(n==0) return 0;
if(F[n]!=0) return F[n];
if(n<2) F[n] = Func(n-d[0],F)+1;
else if(n<5) F[n] = Math.min(Func(n-d[0],F) , Func(n-d[1],F))+1;
else
{
F[n] = Math.min(Func(n-d[0],F) , Func(n-d[1],F));
F[n] = Math.min(F[n], Func(n-d[2],F))+1;
}
return F[n];
}
}7
[0, 1, 1, 2, 2, 1, 2, 2]
找零问题：7 需要硬币2枚。
总结：动态规划是一种通过占用更多内存来加速运算的技术手段，在解决问题时会将复杂的问题拆解为多个子问题，并且会将各个子问题的计算结果存储起来以便后续使用，在这种情况下就可以避免重复计算相同的子问题。