从递归开始, 彻底搞懂动态规划前言。在以前打ACM比赛的那段日子里, 当我刚开始接触并学习动态规划这个知识点的时候, 我完全没法搞明白它到底是一个什么样的概念问题。我去网上搜索相关题目的解答, 发现绝大多数的情况是直接扔过来一道题目, 随后便毫无铺垫地直接列出一个状态转移方程, 紧接着就会立刻丢出一段能够通过验证的代码做法, 这让旁观的人感到非常困惑, 脑子里一片混沌, 晕头转向。尽管当时也动手做过不少相关的练习题了, 可是通常一旦遇到全新的题目类型就不知所措了彻底傻眼了。那时候只会做那些已经见过面的经典题目罢了, 比如像导弹拦截这种题型, 还有各种各样的背包问题之类的内容。今天我是借由算法课程的这项作业的机会, 非常仔细地、把动态规划这件事给好好剖析了一遍。我们是一步接着一歩地来进行说明的, 目的是要讲清楚, 到底是如何将一个普通的、属于指数级复杂度的递归算法, 一步步地给优化成那个属于多项式复杂度的动态规划算法的。关于题目的背景情况是把总共 $m$ 元钱拿出来, 拿去投资 $n$ 个项目, 那个效益函数叫做 $f_i(x) $, 具体的意思就是针对第 $i$ 个项目投资金额是 $x$ 元的时候, 所产生的收益数值是多少, 现在要解决的问题是去求出一种资金分配方式, 也就是给每个项目分别安排多少钱, 最终目标是让这个整体的总效益达到最大的状态, 这里需要用到递归算法, 并且需要对里面的那个递归式的推导过程进行详细说明。咱们来假设投资 i 个项目, 并且总共投资 x 元, 这种情况下, 收益情况的所有可能性都记为 g_i(x)。显然, 我们能够 地得出:存在一个分段定义的系统, 第一个表达式是g一x等于f一x一且x一小于等于x, 第二个表达式是g二x等于f一x一加f二x二且x一加x二小于等于x, 第三个表达式是g三x等于f一x一加f二x二加f三x三口且x一加x二加x三口小于等于x, 后面的模式依次类推, 第i个表达式是g i x等于从k等于一开始到i的f k的和, 且从k等于一开始到i的x k的和小于等于x。我们先把那个 $g_{i-1}(x-x_i)$ 给弄进来, 放到那个 $g_i(x)$ 里面去, 这么一操作之后, 我们就能够得出一个结果, 具体的情况是这样的。$$\begin{cases}g_1(x)f_1(x_1),\\g_2(x)g_1(x-x_2)f_2(x_2),\\g_3(x)g_2(x-x_3)f_3(x_3),\\\ \ ...\\\ \ ...\\\ \ ...\\g_i(x)g_{i-1}(x-x_i)f_i(x_i)\\\end{cases}$$整理可得递归式$$g_i(x)\begin{cases}f_1(x),\ \ i1 .\\g_{i-1}(x-x_i)f_i(x_i),\ \ i1, \sum_{k1}^ix_k \leq x\\\end{cases}$$我们的目的, 是把总收益给弄到最大, 因此需要去算一算。$$w_i(x)max\{g_i(x)\}$$这个式子就是递归定义出来的目标函数, 请注意, 在这个函数里面, $g_i(x)$ 指的是当前这一个项目投资所产生的收益与前面所有投资项目所产生收益排列、结合得在一起的那种组合情况。递归实现Java代码/*** Author xwh* Date 2020/4/13 13:05:53**/public class Investment {/* 投资收益函数 */public static int f[][] new int[5][10];/*** 投资i个工厂, 共x元的最大收益*/public static int g(int i, int x) {// 输出一下当前的计算层级, 方便下个步骤分析复杂度System.out.println(g i x);int max 0;if (i 1) {// 投资第一个工厂的最大收益就是对应函数值return f[i][x];} else {// DFS, 根据公式穷举所有收益情况, 并求其中最大值返回// 当前收益 第i个工厂投资j元收益 前i-1个工厂投资x-j元的最大收益for (int j 0; j x; j) {int temp f[i][j] g(i - 1, x - j);if (temp max) {max temp;}}}return max;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n 4, m 6;// 投资函数初始化, f[i][j]表示第i个工厂投资j元的收益for (int i 1; i n; i) {for (int j 0; j m; j) {f[i][j] scanner.nextInt();}}System.out.println(搜索树的DFS序列);int w g(4, 6);System.out.printf(向%d个工厂投资%d元的最大收益为%d元, n, m, w);}}测试数据是零, 然后是二十、五十、六十五、八十、八十五以及八十五。0 20 40 50 55 60 650 25 60 85 100 110 1150 25 40 50 60 65 70其中第$i$行第$j$列的数字, 表示的是第$i$个工厂进行投资时, 所投入的资金为$j$元的情况下, 所产生的收益数值。复杂度分析我们来对每一个 $g_i(x)$ 进行递归求解, 在求解的过程当中, 下一级别所涉及的内容都是一个组合数。因此, 该算法的时间复杂度应当是下面的这个数值:$$C_{mn-1}^m \frac {(mn-1)!} {(n-1)!m!} Ω((1\)^{mn-1})$$最后得出的结果呈现的是指数量级的增长态势。由于大家普遍知晓, 指数这种形式往往对应着爆炸式的增长现象。由此可以推断出, 如果算法的时间复杂度属于这种现象级别的话, 它在解决那些实际发生的问题时是不具备太大价值的。因此, 一定要采用某个特定的策略手段来把上述提到的这个复杂度的层级给降低下来。而这个被提及的策略手段的名称就被叫做动态规划。递归算法的问题分析要知道应当怎么做才能实现优化, 我们首先必须要清楚问题的根源到底在什么地方。接下来, 我们来对递归所产生的性能损失进行分析, 看一看它的具体消耗出现在哪个环节。当我们将相关的测试数据输入之后, 并且执行之前章节中的代码程序时, 最终得到下面所展示的结果情况:通过观察发现, 当4个工厂各投资6元的时候, 收益情况一共被枚举出了120种。接下来继续加以分析:我们发现, $g_2(j)$ 这种状况被计算了28次。但是在实际上, 这种状况应当只有6种才对, 分别是$ g_2(0), g_2(1) \cdots g_2(6)$。咱们不妨来探讨一下到底是为啥才会冒出这么个事儿呢。对于每一回进行的计算, 那个递归的程序, 它总是会去试着走一遍那更深更深处的一层递归里面所包含的所有的那些个排列和组合情况, 这样一来, 就会导致这性能变得非常低劣。就比如说是, 我们在拿来计算 g_4(6) 这个值的时候它, 会去算出那些从 g_3(0) 一直排到 g_3(6) 的所有结果然后, 对于这其中的任何一项来说, 它还得再去算出从 g_2(0) 一直到 g_2(6) 的那些个结果, 目的就是为了在这些个排列和组合当中, 把当前这个最好的解给找出来。很明显, 眼下这个递归算法出了毛病, 毛病有俩, 头一个就是相同的子问题在那儿重复计算, 第二个毛病就是把已经得出最优解的问题, 又去重新穷举次优解。优化动态规划那些能够借助动态规划方法来进行优化的题目, 通常都是需要严格符合下面所说的这三大基本条件的。它看着好像是很抽象的, 其实咱们已经把当下的这个问题的确是吻合那三个条件的证实完毕, 此刻就来开始进行讲明一番。在递归解决的方案之中它包含了众多的子问题, 而这些不同的子问题是极为稀少的, 以至于极少量子问题被重复处理的诸多次数。这是关于重叠子问题的定义说明, 看上去是不是很熟悉。就在上一节我们发现的递归算法的问题1就是这个意思, 意思是这个。就是说重复计算了很多一样的问题, 而这种计算事实上是通过记忆化搜索来处理的, 也就是通过时间来换空间这种方法得以避免掉这些重复计算的麻烦事情。所谓最优子结构, 其含义指的是一个最优化策略里面的子策略, 它总是具备最优的性质。也可以换一种方式来进行说明, 那就是任何一个确定的最优策略, 它都必须要包含子问题所形成的那些最优策略的存在。同样的情况是, 我们在前面的章节里头已经发现过了, 当我们在算当前这个最大收益 $g_i(x)$ 的时候, $ g_{i-1}(j) $ 肯定都是已经全部算完了的, 通过递归的方式去发现的话, $g_{i-2}(k)$ 也同样是处于这样一种已经被全部计算过的状态。所谓无后效性原则说的是这样一个性质, 那就是某阶段的状态一旦被确定下来之后, 此后过程中的一切演变情况将不再受到之前各个状态以及决策的影响。意思就是指, 对于每一个g_i(x), 它仅仅和g_{i-1}(j)有关系, 而g_{i1}(k)也仅仅和g_i(x)有关系, 同样地, 我们在计算的时候, 每次的排列组合仅仅和前i个工厂的总收益有关系。这个方案需要进行优化。此刻我们已验证完毕, 眼前的投资难题合乎动态规划的三条核心原则, 因此得以采用该方案去谋求优化, 而经过前述的漫长阐述之后, 问题在于具体来讲究竟何谓动态规划这一概念。我们现在返回去看之前所提到的那两个问题, 这第一个问题是说相同的子问题会产生重复计算的情况, 而这第二个问题是指那些本来就已经得出最优解的问题, 却还要重新去进行穷举次优解的操作。问题一涉及到的是子问题存在重叠情况, 问题二涉及到的是整体最优解包含局部最优选择的情况, 那么我们能否通过某种方式, 防止程序进行重复计算那些非最优的答案, 同时避免反复求解已经被确定过结果的最优答案既然我们得出了这样一个结论, 那就是: 当前的最佳结果, 其实仅仅跟前面算好的那个最佳结果有关系。基于这个情况, 我们完全可以在每一次算完以后, 把这个结果给存起来。然后等到下一次需要用到的时候, 我们就直接去之前存的地方拿过来用就行。这样做的话, 我们就不用再去进行那种深入的、一遍又一遍的递归计算了。如此一来, 是不是就能把那上面提到的两个问题都给解决掉呢换了一句话说, 我们如果仅仅只需要发现一个确定的公式, 然后依靠这个公式的结果, 通过当前状态里面已经求得的最优解的组合来不停地去穷举和探索下一个阶段状态里面的最优解决方案, 这样是不是就直接可以把递归这种操作方式给消除掉呢。状态转移方程利用最优子结构以及重叠子问题性质, 将之前的递归公式进行改写, 从而得到:当i等于1的时候, w_i(x)的值是f_1(x), 而当i大于1的时候, w_i(x的最大值集合等于f_i(k)加上w_{i-1} (x减去k)。我们实现成功, 这种成功的具体表现是将当前所找到的最优解与之前曾经计算过的那个最优解建立了关联, 这样一来, 我们在后续的操作当中, 就不需要再去进行那种毫无意义的穷举行为去查找次优解, 同时也避免了再次去重复计算那些已经算过的最优解。这也就是那个状态转移方程。Java代码public static void dp(int n, int m) {int i, j, k, temp;int w[][] new int[n 1][m 1];// 计算投资第一个项目的最大收益for (i 0; i m; i) {w[1][i] f[1][i];}// 投资前i个项目for (i 2; i n; i) {// 计算每一个g[i][x], 0xmfor (j 0; j m; j) {// 状态转移, 利用w[i-1][]计算w[i]// g[i][x] temp f[i][k] w[i-1][j-k]// k投资当前项目的钱数, 0kjfor (k 0; k j; k) {temp f[i][k] w[i - 1][j - k];if (temp w[i][j]) {// 更新当前的最优解, 给下一个最优解调用w[i][j] temp;}}}}System.out.printf(向%d个工厂投资%d元的最大收益为%d元\n, n, m, w[n][m]);}复杂度分析从表面情况来仔细分析一下, 不难清楚地看出来, 这个动态规划算法的大致复杂程度, 其实主要体现为三个部分的循环结构进行的嵌套操作关系, 其计算得到的复杂度数值被确定为是O(nm2)这种表达式形式, 与使用递归方式编写的原始版本程序进行直接的运行效率对比来看, 当前这一种处理性能提升或者改进的效果确实是非常显著而且大量的。总结我将动态规划看作是运用记忆化技术来处理重复子问题, 并且实施了对次优解的剪枝操作的一种穷举式计算算法, 该算法本质上是借助最优解的思路来实现对最终最优目标的全面搜索。至于当初那些学者为什么会决定把对应的英文词汇 $ \ $ 翻译成为“动态规划”这几个汉字, 这确实让人感到非常困惑, 因为这个直白的字面含义在实际概念理解层面的帮助并不大, 真的很难让人一下子弄明白。