银河下的哈纳雷湾 背景主题图源自美国夏威夷·哈纳雷

动态规划

动态规划这个概念十分有趣。举一个例子来说，在我本科学习“栈的应用”这部分内容的时候，提到了可以用栈实现“走迷宫”的问题。也就是在代码中，如果我们发现某一条路径进入死胡同的时候，要按原路回退。回退的前提是我们有一个数据结构——栈，用它来保存我们之前的行走路径。如果没有栈应用在迷宫问题，那不得不回退到起点再重新执行，这将很麻烦。所以，这里提到了一个重要的思想：保留之前运算的结果，不进行重复冗余的计算。

动态规划在我的理解而言，可以想象为：有某种问题看似很复杂，但是可以分解为较小的子问题进行求解。最小的子问题是方便求解的，同时存储中间子问题的计算结果。当然最重要的是，可以寻找到“该问题”和“分解的子问题”之间的递推关系表达式。

上面是我自己的理解，下面的内容摘录自书中规范化表述

和分治法一样，动态规划(dynamic programming)是通过组合子问题的解而解决整个问题的。(此处“programming”是指–种规划，而不是指写计算机代码)。分治法算法是指将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

钢条切割问题 Rod Cutting

自顶向下的分析

钢条切割的问题是，既然每一段不同长度的钢条价格不一，那么我们如何切割一段总长度为 n 的钢条，使总收益最大呢？假设使用 rnr_n 代表一个长度为 n 的钢条的最大收益，那么，可以得到：

rn=max⁡(pn,r1+rn−1,r2+rn−2,⋯ ,rn−1+r1)r_{n}=\max \left(p_{n}, r_{1}+r_{n-1}, r_{2}+r_{n-2}, \cdots, r_{n-1}+r_{1}\right)

第一个参数 pnp_n 代表着整段钢条都不参与切割，即查上表便可得到；第二个参数代表着把钢条切成长度为 1 和 n-1 两段钢条之后的总收益，等等。其实，在这个表达式中，已经把问题分解为若干个子问题，而这些子问题同时满足和原问题同样的情景，可以递归地进行下去，只是这种递归关系对我自己来说很难凭空想象，这样自顶向下的结构很抽象，所以下面接着分享学到的自底向上的分析方法。

对于上面的表达式我想再多说一点。为什么除第一个参数（整段钢条都保留）外，其他参数都是只切割一次，然后是计算切割一次的收益 pip_i 和剩余的钢条 rn−ir_{n-i} 的收益和？其实，这就是我们对子问题的分解罢了，至于剩余的钢条 rn−ir_{n-i} 到底被切割了没？又切割了几次？这是我们的子子问题，在递归的最后都会被计算的。就像我们想求斐波那契数列的 F(10)=F(9)+F(8)F\left(10\right) = F\left(9\right)+F\left(8\right) 一样，后两个数字不用着急啊，会递归到然后求得的。

总结一下：自顶向下的方法（分治法）往往是一个递归的过程，我们把问题不断地细颗粒度细化，最后不能再分解时得到每一个颗粒度的最优解递归返回，这一系列过程非常类似归并排序。

自底向上的分析

我们都知道，求斐波那契数列可以使用迭代的方法计算，这里自底向上的方法也是一个迭代的方法计算 rnr_n，相应的，上面的公式可以同样转化为：

rn=max⁡1⩽i⩽n(pi+rn−i)r_{n}=\max _{1 \leqslant i \leqslant n}\left(p_{i}+r_{n-i}\right)

那什么又是自底向上的方法呢？举例来说，r1r_1 不用切割，收益值就是 p1p_1；r2r_2 可以有 1+1 和 2+0 两种切割方式，前者的收益是 r1+r1r_1 + r_1，后者的收益是 p2p_2，最后取最大收益就是不切割（或者称在2的位置切割），r3r_3 可以有 1+2=r1+r2;2+1=r2+r2;3+0=p31+2=r_1+r_2;2+1=r_2+r_2;3+0=p_3 三种方式，其余的保持一样的计算方法。计算结果如下所示：

代码如下所示：

总结一下：自底向上的方法（动态规划）往往是一个迭代的过程，从最初的长度为 1 的钢条最有切割方案、再到长度为 2，再到长度为 3 等等，最关键是定义好无后效性的子问题，并准确写出状态转移方程。

矩阵链乘法问题

刚才的钢条问题，对于切割后左右的最优解是同等的（就是说，左边切出1和右边切出1都是一样的利润），所以我们只需要一维数组就能定位和存储子问题的最优解。矩阵链乘是二维的动态规划问题。

换句话表述，我们应当如何组合矩阵相乘的顺序，使最后的乘法规模最小？那么，我们问题的子问题就是 i<ji<j，使 Aij=AiAi+1…AjA_{ij} = A_{i}A_{i+1}\dots A_{j}，并且 m[i,j]m[i,j] 等于计算 AijA_{ij} 所需要的最小乘法次数。假设矩阵 AikA_{ik} 具有维度 pi−1∗pkp_{i-1}*p_{k}，那么我们计算 AikAk+1,jA_{i k} A_{k+1, j} 便进行了 pi−1∗pk∗pjp_{i-1}*p_{k}*p_j 次乘法计算。我们把从 i 到 j 的计算划分为 [i,k] 和 [k+1,j] 两次矩阵乘法计算，所以，我们可以得到：

m[i,j]=m[i,k]+m[k+1,j]+pi−1pkpjm[i,j]={0 if i=jmin⁡i≤k<j{m[i,k]+m[k+1,j]+pi−1pkpj} if i<jm[i, j]=m[i, k]+m[k+1, j]+p_{i-1} p_{k} p_{j}\\ m[i, j]=\left\{\begin{array}{ll} 0 & \text { if } i=j \\ \min _{i \leq k<j}\left\{m[i, k]+m[k+1, j]+p_{i-1} p_{k} p_{j}\right\} & \text { if } i<j \end{array}\right.