动态规划（DP）简介

Those who cannot remember the past are condemned to repeat it.

什么是动态规划算法

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.

Dynamic programming has evolvd into a major paradigm of algorithm design in computer science. The name was coined in 1957 by Richard Bellman to decribe a type of optimum control problem.

根据前述内容以及余老师 PPT 上的介绍，动态规划（DP）诞生初用于描述一类问题而非描述一种求解方式。不过随着时间演变，现在 DP 更常用来表示一类算法（尤其在 CS 领域）。

核心思想

解决小规模的子问题
将小规模问题的解（解集）储存起来
利用小规模问题解集状态转移至大规模问题的解集状态
最终解（最大规模的 final 解）即为我们所求的最终解

适用条件

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems.

最优子结构（Optimal structure）

A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal sulutions to its subprolems. Also is called Principle of Optimality by Bellman.

子问题重叠（Overlapping sub-problems）

子问题重叠并不是定义 DP 类型问题的必要条件，但是当子问题出现大规模重叠时，DP 算法更能体现效果，最简单直接的例子：分治思想和 DP 思想求解斐波那契额数列。

随便谈谈

与分治法（Divide and Conquer）对比

If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead.[1] This is why merge sort and quick sort are not classified as dynamic programming problems -- Introduction to Algorithms (2nd ed.), MIT Press.

子问题孤立，更适用于分治法，这点出了“Divide and Conquer”与“Dynamic Programming”，两种算法思想的本质不同。此外，求解过程中，分治法倾向于从顶向下递归分解问题然后再递归合成大规模问题的解，而动态规划算法则初始计算小问题的解，根据状态转移方程自底向上计算所求状态的解。

与贪心算法（Greedy）对比

贪心算法，对于尚未加入解集的元素按固定策略（最大或最小）选取状态转移，即总是遵循某种规则，做出局部最优的选择，以推导出全局最优解，所解决的问题也具有最优子结构性质。

以即将要讨论的 01 背包问题为例，贪心想法是在一次选择中选取未选择物体中价值/重量比最高的。这个局部选择是最优的，但不考虑整体背包选择方案是否最优。而动态优化则要求当前拾取物体从之前状态（减去该物体重量的最优态）转移过来，这样就保证了一定的全局性质。

前向性

No backwards: depending on the current state.

下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结，个人理解，这就是Dynamic的体现。

经典 DP 问题：背包问题

背包问题相信大家都不陌生，它是动态规划算法学习过程中不得不提的经典系列问题，而 01 背包问题又是该系列问题的基础。

在编程解决问题的过程中，我们常会使用空间优化与常数优化来加速程序的执行，在程序设计竞赛中，由于时间上的限制，我们的关注点常在程序的运行结果是否与标程的运行结果相一致，对于优化的影响却无暇关心。

优化问题，也是计算机科学家与专业编程人员常常关注的点，利用本节课的时间，我们会着重讨论求解 01 背包问题的优化方式以及其影响。

01 背包题目

有$N$件物品和一个容量为$V$的背包。放入第$i$件物品耗费的费用是$C_i$，得到的价值是$Value_i$。求解将哪些物品装入背包可使价值总和最大。

基本解题思路

因为每种物品只有一件，选择只有放（1）、不放（0）两种状态，所以称这类问题为 01 背包问题。

该问题对应的子问题为：取其中$i$件物品放入背包得到的最大价值。为了方便，我们给原物体一个序，则对应子问题为：取前$i$件物品放入背包得到的最大价值。根据该子问题，我们定义状态$F[i,v]$为前$i$件物品放入限制重量为$v$所能得到的最大价值，然后我们可以想出状态转移方程。

\[F[i,v] = max \{ F[i-1,v] , F[i-1,v-C_i] + Value_i \}\]

该状态转移方程的含义为：按序逐个拾取物体的过程中，拾取$i$号且背包限制为$v$重量状态（$F[i,v]$），其只由两种状态转移而来，不选择该物体（则状态取值同相同限重量拾取上个物体时的状态 $F[i-1,v]$），选择该物体（则状态取值由上次选择时，限重为当下限重减去此次拾取物体重量的状态转移而来$F[i-1,v-C_i]+Value_i$）。

最优子结构性质与无后向性是可证的，见下一节附加内容。

原文特别强调了上述转移方程的重要性，也做了相应的解释：

这个方程非常重要，基本上所有跟背包象关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前$i$件物品放入容量为$v$的背包中”这个子问题，若只考虑第$i$件物品的策略（放或不放），那么就可以转化为一个只和前$i-1$件物品相关的问题。如果不放第$i$件物品，那么问题就转化为“前$i-1$件物品放入容量为$v$的背包中”，价值为$F[i-1,v]$；如果放第$i$件物品，那么问题就转化为“前$i-1$件物品放入剩下的容量为$v-C_i$的背包中”，此时能获得的最大价值就是$F[i-1,v-C_i]$再加上通过放入第$i$件物品获得的价值$Value_i$。

伪代码描述：

F[0,0..V] ← 0
for i ← 1 to n
    for v ← w[i] to V
        F[i,v] ← max{F[i-1,v] , F[i-1,v-w[i]]+v[i]}

附加：最优子结构证明

学习自博客01 背包存在最优子结构的证明

表述：

$n$为背包重量限制，$w[i]$为$i$物体重量，$v[i]$为$i$物体价值，如果$(z_1,z_2 \cdots z_k)$是问题$f_k(n)$的最优解，那么

对于任意$1 \le j \le k$，有$z_j = 1$（确定$j$物体状态为取），则有$(z_1,z_2 \cdots z_{j_1} , z_{j+1} , z_{j+2} \cdots z_k)$是问题$f_{k-1}(n-w[j])+ v[j]$的最优解

对于任意$1 \le j \le k$，有$z_j = 0$（确定$j$物体状态为不取），则有$(z_1,z_2 \cdots z_{j_1} , z_{j+1} , z_{j+2} \cdots z_k)$是问题$f_{k-1}(n)$的最优解。

这里 $i$ 表示子问题的规模，表述为将 $i$ 个物品放入容量为$v$的背包中，

证明（反证法）：

假设子问题不是最优解，对于情况 1，假设存在$(z_1',z_2' \cdots z_{j-1}' , z_{j+1}' ,\cdots z_k')$ 是子问题的最优解，那么 $f_k(n)$的最优解将会是$(z_1',z_2' \cdots z_{j-1}' , z_j , z_{j+1}' \cdots z_k')$，与假设矛盾。情况 2 同理。

算法优化与代价

空间复杂度优化

由于要使用$dp[n][v]$状态空间，如果储存全部状态，根据伪代码思路，该动态优化算法的时间和空间复杂度均为$O(VN)$，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到$O(V)$。

我们观察状态转移方程

\[F[i,v] = max \{ F[i-1,v] , F[i-1,v-C_i] + Value_i \}\]

我们每轮计算前$i$个在不同限重背包的最优值时，利用的状态只有$i-1$时的状态，也即上一轮外层循环得到的值，据此我们可以使用一些优化方法。

滚动数组

每次都使用固定的几个存储空间，来达到压缩 or 节省存储空间的目的。主要应用在递推或动态规划中。

代码描述

for (i=1 ;i <= n; i++)
{
    for (v = w[i] ; v <= V ; v++)
    {
        dp[1][v] = max(dp[0][v],dp[0][v-w[i]]+v[i]);
    }
    // 一轮更新结束后统一翻转
    for (v = 0; v<=V ; v++){
        dp[0][v] = dp[1][v];
    }
}

当然我们还发现状态转移方程中，只会利用背包限重状态小于等于要更新状态的已知状态，所以我们按逆序（从大到小）遍历内层循环，就可以避免在同一轮外层循环中先更新的影响后更新的值，由此修改滚动数组代码。

for (i=1 ;i <= n; i++)
{
    for (v = V ; v >= w[i] ; v--)
    {
        dp[1][v] = max(dp[0][v],dp[0][v-w[i]]+v[i]);
        dp[0][v] = dp[1][v];
    }

}

压缩至一维数组

那既然逆序已经避免同一轮更新中先更新的影响后更新的值，实际上滚动数组也非必要了。我们使用一维数组便可实现状态转移，并且保证计算$dp[v]$时，$dp[v-w[i]]$保存的是对应二维$dp[i-1][v-w[i]]$的值。

for (i=1 ;i <= n; i++)
{
    for (v = V ; v >= w[i] ; v--)
    {
        dp[v] = max(dp[v],dp[v-w[i]]+v[i]);
    }

}

时间复杂度常数优化

伪代码中

1 2	`for i ← 1 to n for v ← V to w[i]`

《背九》原作者给出可以优化为$V \quad to \quad max(V − \sum_i^N C_i, C_i)$。我个人认为可以严格到$V \quad to \quad max(V - \sum_{i+1}^N C_i,C_i)$。

1 2	`for i ← 1 to n for v ← V to max(w[i],V-(w[i+1]+...+w[n]))`

如何理解这个常数优化？，我们需要回过头来再看看状态转移方程。

\[F[i,v] = max \{ F[i-1,v] , F[i-1,v-C_i] + Value_i \}\]

我们固定某一限重状态随$i$递增的变化，不妨研究与最终答案相关的，$final(i)= F[i][V]$。我们发现在$i$递增一轮过程中。$final$只会变动一次，且只有两个可能的方向，不变（延续$i$上一轮递增后得到的结果），改变（受$F[i-1][V-w[i]]$影响）。

如果我们将，可以影响$final$的所有限重状态，随$i$减小（逆序），画出来，我们可以发现能够影响到答案（最终状态）的边界是逐渐减小的。

我们可以发现，能够影响$final$的重量状态是有限的，并且随$i$减小，可影响的状态逐渐扩张，最后一次只有$final=dp[n][V]$单一状态影响最终答案（因为它本身就是最终答案），每一轮可能影响到$final$的边界应是，$max(V - \sum_{i+1}^N Value_i,C_i)$，这里可以补充一下，原作者认为是求和下限应为$i$，带入最后$i=N$我们发现在最后一轮除了更新$dp[N]$还更新了其他与最终答案无关的状态，所以我觉得这个更严格的界限是正确的。

反过来想也可以，在计算$dp[v]$时，若某一限重状态最终能够影响$final$，必然要经过几轮$i$递增（理想状态是，$dp[v+w[i+1]$每次都能受到影响），这也提醒我们，某一状态影响最终结果是需要一定时间限制的，在$i$逐渐靠近$n$时，即便我们遇到重量很小但是价值很大的一颗“金子”，我们也不一定需要从它的重量开始更新状态。

举例来讲比如最后三个物体是

// n = 10   V = 50
// 当前dp[50]=150
w[n-2]=2  v[n-2]=100 //金子
w[n-1]=5  v[n-1]=40
w[n]=3    v[n]=50

此时$w[i] = 2$,$V-sum=42$（按照底为$i+1$的求和）。如果只是为了获得正确的$dp[50]$，我们需要从$v=50$更新到$v=42$就够了呢？还是说要更新到$v=2$，显然，我们更新到$v=42$就够了，即便后面两个物体在最优解中都要取，$dp[42]$会影响下一轮的$dp[47]$，进而影响最终的$dp[50]$。

优化的代价

优化不是无代价的

承上面例子，显然根据常数优化算法，我们最终可以得到正确的$dp[50]$，但我们在想，有没有少些什么？

很明显啊，在倒数第三轮外层循环我们没有计算新的$dp[2]$（而大概率碰到金子，2 格背包我们应该捡起来啊！），那么不更新的代价是什么呢？

针对题目，影响最终答案么？

不影响。

不针对题目，影响答案么？

影响，因为改变了状态空间解集。

朴素二维动态规划得到的解集

$dp[n][V]$储存了（在该遍历序下）任意小于序长度前缀，任意小于最大限制容量的解集。也即在不增删修改物品条件下，后续满足上述条件的任意询问$Q_1$，都可以在$O(1)$的时间给出答案。

一维压缩空间优化得到的解集

$dp[V]$储存了长度等于序长，任意小于最大限制容量的解集。同样，不改变物体，对该序询问容量小于限制的背包问题$Q_2$，都可以在$O(1)$的时间给出答案，但是如果想询问前缀问题（而非序长），则不能获得，因为在外层循环迭代中，没有保留这部分结果。

空间优化+常数优化的解集

只能保证$dp[i],i=V$单个值是正确的，而其他值均无意义。

根据上述这些“发现”，我们能学到什么？

对于正在讨论的问题，如果关注单解，那么空间+常数优化自然是很好的选择，但是如果数据固定而频繁询问，不考虑更新算法的话，那么朴素的二维 dp 或许是最好的。优化不应该是盲目的，有些优化需要我们理解背后更深的意义及影响，才能更好的应用在我们的程序中。

其他 DP 优化算法

空间复杂度常与实现方式有关，这里我们考虑通用的时间复杂度优化，影响动态规划时间复杂度的因素：

时间复杂度=所需计算状态总数*每个状态转移的状态数*每次状态转移的时间

通常，我们考虑对动态优化算法进行优化时，要从上述三个因素着手。

需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 ——《动态规划算法的优化技巧》毛子青

回顾 01 背包问题时间复杂度常数优化，我们是优化了所需计算状态总数（对应二维数组容易理解）。本节后面内容，将结合其他经典的动态规划问题，介绍另外的优化方法。

矩阵优化递推

常用于线性递推式，能以对数优化线性计算。通用模型：

\[f(n-1) = a f(n-1) + b f(n-2) + c\]

矩阵递推式代替原有递推式，将所求转换为矩阵连乘形式。

$$ =

这样做有什么好处呢？将系数矩阵设为$base$

\[ base = \left[ \begin{matrix} a & b & c \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{matrix} \right] \]

\[ \left[ \begin{matrix} f(n) \\ f(n-1) \\ 1 \end{matrix} \right] ={base}^{n-2} \left[ \begin{matrix} f(2) \\ f(1) \\ 1\\ \end{matrix} \right] \]

${base}^{n-2}$可用快速幂算法加速运算。

举例题目：【洛谷-P1962 斐波那契数列】【CSU-1895 Apache is late again】

这里以后者题目为例。

利用（矩阵）快速幂算法进行运算。

利用决策单调性进行优化

学习自毛子青的《动态规划算法的优化技巧》，该优化方法针对每个状态转移数的优化。

石子合并问题也是经典的DP问题，描述如下：在一个操场上摆放着一排n（n≤20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。

核心：状态转移方程

\[m[i,j] = \min_{i<k≤j} \{m[i, k-1]+m[k,j] + \sum_{l=i}^jd[l] \} \quad i＜j \]

四边形不等式

当函数$w[i,j]$满足$w[i,j]+w[i',j'] \le w[i',j] + w[i,j'] , \quad i \le i' \le j \le j'$。

当函数$w[i,j]$满足$w[i',j]≤w[i,j'] \quad i \le i' \le j \le j'$时称$w$关于区间包含关系单调。

在石子归并问题中，我们可以依次证明$\sum_{l=i}^j𝑑[l]$、$𝑚[𝑖,𝑗]$、$𝑠[𝑖,𝑗]$满足四边形不等式。所以优化状态转移数，状态转移方程为：

\[m[i,j] = \min_{s[i,j-1]<k≤s[i+1,j]} \{m[i, k-1]+m[k,j] + \sum_{l=i}^jd[l] \} \quad i＜j \]

Computer Science 算法与数据结构

算法与数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

密码技术学习——Keccak原像破解赛题前置知识点总结上一篇

算法与数据结构学习——01背包问题常数优化算法对问题解集的影响下一篇

算法与数据结构学习——DP背包问题备课提纲

动态规划（DP）简介

什么是动态规划算法

核心思想

适用条件

最优子结构（Optimal structure）

子问题重叠（Overlapping sub-problems）

随便谈谈

与分治法（Divide and Conquer）对比

与贪心算法（Greedy）对比

前向性

经典 DP 问题：背包问题

01 背包题目

基本解题思路

附加：最优子结构证明

算法优化与代价

空间复杂度优化

滚动数组

压缩至一维数组

时间复杂度常数优化

优化的代价

朴素二维动态规划得到的解集

一维压缩空间优化得到的解集

空间优化+常数优化的解集

其他 DP 优化算法

矩阵优化递推

利用决策单调性进行优化

四边形不等式