(二) 动态规划算法

Word count: 6.3kReading time: 22 min

 2021/06/22   Share

一、术语介绍

先来说几个动态规划问题中的术语。

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

多阶段决策问题图示：

1.1 阶段

把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同。
描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用 k 表示。
此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。

在前面的图中，第一个阶段就是点A到点B，第二个阶段是点B到点C，而第三个阶段是点C到点D。

1.2 状态

状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。

前面的例子(图)中，初始状态即A，而第一个阶段有两个状态B1和B2，第二个阶段是三个状态C1，C2和C3，而第三个阶段是状态D1和D2。

过程的状态通常可以用一个或一组数来描述，称为状态变量，用x(k)表示。一般，状态是离散的，但有时为了方便也将状态取成连续的。

而且在每个阶段的状态维数可以不同。状态变量当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。

1.3 无后效性

我们要求状态具有下面的性质：如果某阶段的状态一旦确定，则在这一阶段以后过程的发展变化仅与此阶段的状态有关，不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。

换句话说，过程的每一次实现可以用一个状态序列表示。在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。

也就是说，未来与过去无关，当前的状态是此前历史（以往决策）的一个完整总结，过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。（简单点说：过去只能通过影响现在，进而影响未来）

1.4 决策

一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。
每一个阶段都有若干个决策可供选择。
在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。
描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

决策变量的范围称为允许决策集合。

1.5 多阶段决策问题与策略

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。

策略：由每个阶段的决策组成的一个决策序列称为策略。
- 每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取。
允许策略集合：对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。
最优策略：允许策略集合中达到最优效果的策略称为最优策略。
- 对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。

1.6 状态转移方程

给定k阶段状态变量 x(k) 的值后，如果这一阶段的决策变量一经确定，第 k+1 阶段的状态变量 x(k+1) 也就完全确定，即 x(k+1) 的值随 x(k) 和第 k 阶段的决策 u(k) 的值变化而变化。

那么可以把这一关系看成 (x(k),u(k)) 与 x(k+1) 确定的对应关系，用 x(k+1) = Tk(x(k),u(k)) 表示。这是从 k 阶段到 k+1 阶段状态转移方程的状态转移规律，称为状态转移方程。

1.7 最优化原理/最优子结构性质

最优性原理：要求问题的最优策略的子策略也是最优。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即一个问题的最优解只取决于其子问题的最优解，子问题的非最优解对问题的求解没有影响。
最优子结构性质：当一个问题的最优解包含着它的子问题的最优解时，就称此问题具有最优子结构性质。

一个问题 满足最优化原理也称其 拥有最优子结构性质。

动态规划引出：

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

二、基本思想

动态规划算法通常用于求解最优性问题：在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划(DP：Dynamic Programming)是一种重要的程序设计手段，是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

其基本思想是在对一个多阶段决策的问题，按照某一顺序，根据每一步所选决策的不同会引起状态的转移，最后会在变化的状态中获取到一个决策序列。

动态规划与分治法的异同：

相同点：都是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
不同点：分治法是将问题划分成相互独立的子问题，因此部分子问题会被重复计算；动态规划方法分解得到的子问题往往不互相独立，而是相互重叠的，从而避免了大量重复计算。

动态规划的实质是分治思想和解决冗余的结合：

将问题实例分解为更小的、相似的子问题
存储子问题的解，在需要时再找出已求得的答案，来避免计算重复的子问题，从而得到多项式时间算法。
- 用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解(即满足最优化原理)，则可以考虑用动态规划解决。

动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。

三、适用情况

一般具有以下3个特征：

满足最优化原理(或称：问题具有最优子结构的性质。是动态规划的基础)
- 怎么分析问题是否满足？反证法
- 先假设由问题的最优解导出的子问题的解不是最优的 → 然后证明在这个假设下可构造出比原问题最优解更好的解 → 从而导致矛盾，证明最优化原理
无后效性
有重叠子问题：递归地分解问题时，产生的子问题并不总是独立的（很多子问题重复），一个子问题在下一阶段中可能被多次使用到。该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势
- 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种 以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

四、基本步骤 — 书面版

1、分析最优解的性质，并刻画其结构特征。(确定满足最优化原理、划分阶段、确定状态)

2、递归地定义最优解。(确定状态转移方程(递推方程))

3、以自底向上或自顶向下(备忘录)的方式计算出最优值

4、根据计算最优值时得到的信息，从子问题的最优解逐步构造出整个问题的最优解

步骤1-3是动态规划算法的基本步骤。在只需求出最优值的情形下，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多，以便构造最优解。

【问题描述】：给定两个字符串A[m]、B[n]，求它们的最长公共子序列C。

1、刻画最优解的结构特征

1 2	如果temp=A[m]=B[n]，C=temp+max_common_len(A[1,...,m-1],B[1,...,n-1])；如果A[m]!=B[n]，则C=maxLen(max_common_len(A[1,...,m],B[1,...,n-1])，max_common_len(A[1,...,m-1],B[1,...n]))。

2、递归的定义最优解的值

设C[i,j]表示两个串A[i]与B[j]的最长公共子序列的长度，则
if i=j=0, C[i,j]=0;
if i,j>0 and A[i]==B[j], C[i,j]=1+C[i-1,j-1];
if i,j>0 and A[i]!=B[j], C[i,j]=max(C[i-1,j],C[i,j-1]).

3、计算最优解

五、基本步骤【个人心得】

5.1 步骤

第一步：将原问题分解为子问题 — 划分阶段

把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决。
子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。
按照问题的时间或空间特征，把问题分为若干个子问题。划分时，需要注意划分后的子问题一定要是有序的或者是可排序的，否则问题就无法求解。(多阶段决策问题)

第二步：确定状态 — 确定状态、状态空间

“状态”是什么？

在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。
- 个人解读：
  - 引用词语释义：在学术领域，状态是指对象涉及的过程，由一组物理量来表征。例如：
    - 质点的机械运动状态由质点的位置和动量来确定；
    - 由一定质量的气体组成的系统的热学状态可由系统的温度、压强和体积来描述。
  - 状态是一组变量。一组变量定义了一个子问题。即一个状态对应一个子问题。
一个“状态”对应于一个或多个子问题。
- 个人解读：
  - 一系列(1…N个)的决策，组成一个策略，每个策略都对应产生了一个状态(/子问题)。
  - 当策略可能包含多个子策略时，此策略对应的状态，是由多个子问题递推出来的，即所谓的一个状态可能对应多个子问题。（换个说法就是：求解某个状态的值，可能需要先求解某些子问题。）
所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。
- 个人解读：
  - 子问题的解 = dp(一个状态) = dp({变量1，变量2,…变量n});
当然，状态的选择要满足无后效性。
所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。
- 状态空间也就是子问题空间，决定了动态规划表的设计（是几维的）。

第三步：确定一些初始状态的值

初始状态，也会被称为边界状态、叶节点状态(对应一个子问题)

第四步：确定状态转移方程

定义出什么是状态、在该状态下的值后，就要找出不同的状态之间如何迁移 —— 怎么从本阶段状态(“值”已知)递推到下一阶段的未解状态，直到最终状态。(递推型)
状态的迁移可以用递推公式表示，此递推公式也可被称作状态转移方程。

第五步：开始计算

以 自底向上 或 自顶向下的记忆化方式(备忘录法) 计算出最优值，根据计算最优值时得到的信息，构造问题的最优解。

5.2 个人总结

相比动态规划，分治法与贪心法就简单许多。(首先后两者都不用记录前面状态(子问题)的值)
分治法：先一分为二…然后合二为一…
贪心法：也算是多阶段决策问题。找出子问题分解思路、确定状态空间、初始状态值。确定状态转移方程这一步有差异，贪心法是自顶向下一层一层分解，遵守贪心选择原则，得出一系列子问题的局部最优解，直到最小子问题，即可组合出原问题的解。

5.3 备忘录算法

备忘录方法是动态规划算法的变形，它通过分治思想对原问题进行分解，以存储子问题的解的方式解决冗余计算，并采用自顶向下的递归方式获取问题的最终解。

备忘录算法与动态规划算法

相同之处：都会对子问题的计算结果进行存储，解决冗余计算
不同之处：动态规划算法是自底向上递推求解，而备忘录方法是自顶向下递归求解。

选择：

当子问题空间中的大量子问题无需求解时，使用备忘录方法较省时。
但当无需计算的子问题只有少部分或全部都要计算时，使用动态规划算法，节省递归带来的额外消耗。

比如：求LCS(最长公共子序列)问题中：

动态规划算法求算，就是自底向上，将所有会出现的子问题都计算并记录下来，而其实有一些子问题在后续的计算中，并不会被用到。
而备忘录算法求解，就是自顶向下递归，只计算使用到的子问题并记录，

备忘录算法与直接递归（备忘录方法 = 递归 + 记录表）

备忘录方法的控制结构与直接递归方法的控制相同(递归也是分解子问题，自顶向下求解)，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解
备忘录：初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。

六、程序设计【实操】

6.1 三要素

动态规划的主要难点在于理论上的设计，也就是上面几个步骤的确定，一旦设计完成，实现部分就会非常简单。

使用动态规划求解问题，最重要的就是确定动态规划三要素：

问题的阶段(子问题划分)
每个阶段的状态
从前一个阶段转化到后一个阶段之间的递推关系

递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

6.2 确定状态转移方程

仍以该图为例

阶段：描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。
- 第一个阶段就是点A到点B，第二个阶段是点B到点C，而第三个阶段是点C到点D。
状态：状态通常可以用一个或一组数来描述，称为状态变量，记为x(k)。
- 初始状态为A，而第一个阶段有两个状态B1和B2，第二个阶段是三个状态C1，C2和C3，而第三个阶段是状态D1和D2。
决策：每一个阶段都有若干个决策可供选择，描述决策的变量称决策变量。记为u(k)。
每个阶段状态的值：为演变到该状态的前一阶段的状态的值F(k) + 决策对应的值。如果发现更优解，覆盖之前的(最优常指耗费最小/路径最短，或是收益最大)。

以凑零钱问题为例，如何列出正确的状态转移方程？(动态规划详解 — labuladong)

确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。

就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

更简单一些的：最长公共子序列问题，dp中没有自变量。

更复杂一些的：如投资问题

已知：f_k(x) 为投资项目k x元钱，所得到的收益
F_k(x)：x元钱投给前k个项目最大效益
x_k：投给项目k的钱数

6.3 最优决策表

确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

1	f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

6.4 一般的算法设计模式如下

for(j=1; j<=m; j=j+1) // 第一个阶段
   xn[j] = 初始值;

 for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
   for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
     xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};

t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案

print(x1[j1]);

for(i=2; i<=n-1; i=i+1）
{  
     t = t-xi-1[ji];

     for(j=1; j>=f(i); j=j+1)
        if(t=xi[ji])
             break;
}

七、经典运用

矩阵连乘
走金字塔
最长公共子序列(LCS)
最长递增子序列(LIS)
凸多边形最优三角剖分
背包问题
双调欧几里得旅行商问题
求全路径最短路径的Floyd算法
…

7.1 0-1背包问题

【问题描述】
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-11背包问题。

【数据】
物品个数n=5，物品重量 w[n] = {0,2,2,6,5,4}，物品价值 V[n] = {0,6,3,5,4,6}（第0位，置为0，不参与计算，只是便于与后面的下标进行统一，无特别用处，也可不这么处理）。总重量 c = 10。背包的最大容量为10，那么在设置数组m大小时，可以设行列值为6和11，那么，对于 m(i, j) 就表示可选物品为 i…n 背包容量为j(总重量)时背包中所放物品的最大价值。

八、参考链接

看了好多，教你彻底学会动态规划——入门篇尤为通俗易懂
如果要看备忘录算法、动态规划算法之间的差异，可以看算法-动态规划 Dynamic Programming–从菜鸟到老鸟，并做一下求LCS这道题，搜一下它的两种解法
动态规划 — 百度百科

Author：Tenloy

原文链接：https://tenloy.github.io/2021/06/22/dynamic-programming.html

发表日期：2021.06.22 , 2:40 PM

更新日期：2024.04.07 , 8:02 PM

Next Post

(三) 贪心算法
Previous Post

(一) 分治算法及减治、变治算法

