文江博客开发文档演算法笔记文章详情

文章来源于网络收集而来，版权归原创者所有，如有侵权请及时联系！

Dynamic Programming

发布于 2025-01-31 22:20:36 字数 18979 浏览 0 评论 0 收藏 0

长江后浪催前浪，一替新人趱旧人。《张协状元》

资之深，则取之左右逢其原。《孟子》

Dynamic Programming

先透过一个简单的例子，感受一下动态规划吧！

范例：阶乘（Factorial）

1 × 2 × 3 × ⋯ × N。整数 1 到 N 的连乘积。N 阶乘。N!。

N!源自(N-1)!，如此就递迴分割问题了。

阵列的每一格对应每一个问题。设定第一格的答案，再以迴圈依序计算其馀答案。

Dynamic Programming: recurrence

Dynamic Programming
= Divide and Conquer + Memoization

动态规划是分治法的延伸。当递迴分割出来的问题，一而再、再而三出现，就运用记忆法储存这些问题的答案，避免重複求解，以空间换取时间。

动态规划的过程，就是反覆地读取数据、计算数据、储存数据。

1. 把原问题递迴分割成许多更小的问题。（recurrence）
   1-1. 子问题与原问题的求解方式皆类似。（optimal sub-structure）
   1-2. 子问题会一而再、再而三的出现。（overlapping sub-problems）
2. 设计计算过程：
   2-1. 确认每个问题需要哪些子问题来计算答案。（recurrence）
   2-2. 确认总共有哪些问题。（state space）
   2-3. 把问题一一对应到表格。（lookup table）
   2-4. 决定问题的计算顺序。（computational sequence）
   2-5. 确认初始值、计算范围。（initial states / boundary）
3. 实作，主要有两种方式：
   3-1. Top-down
   3-2. Bottom-up

1. recurrence

递迴分割问题时，当子问题与原问题完全相同，只有数值范围不同，我们称此现象为 recurrence，再度出现、一再出现之意。

【注：recursion 和 recurrence，中文都翻译为“递迴”，然而两者意义大不相同，读者切莫混淆。】

此处以爬楼梯问题当作范例。先前于递归法章节，已经谈过如何求踏法，而此处要谈如何求踏法数目。

踏上第五阶，只能从第四阶或从第三阶踏过去。因此“爬到五阶”源自两个子问题：“爬到四阶”与“爬到三阶”。

“爬到五阶”的踏法数目，就是总合“爬到四阶”与“爬到三阶”的踏法数目。写成数学式子是“f(5) = f(4) + f(3)”，其中“f(‧)”表示“爬到某阶之踏法数目”。

依样画葫芦，得到“f(4) = f(3) + f(2)”、“f(3) = f(2) + f(1)”。

“爬到两阶”与“爬到一阶”无法再分割、没有子问题，直接得到“f(2) = 2”、“f(1) = 1”。

整理成一道简明扼要的递迴公式：

f(n) =
 { 1                , if n = 1
 { 2                , if n = 2
 { f(n-1) + f(n-2)  , if n >= 3 and n <= 5="" <="" pre="">

爬到任何一阶的踏法数目，都可以藉由这道递迴公式求得。n 代入实际数值，递迴计算即可。

为什麽分割问题之后，就容易计算答案呢？因为分割问题时，同时也分类了这个问题的所有可能答案。分类使得答案的规律变得单纯，于是更容易求得答案。

2-1. recurrence

f(n) =
 { 1                , if n = 1
 { 2                , if n = 2
 { f(n-1) + f(n-2)  , if n >= 3

2-2. state space

想要计算第五阶的踏法数目。

全部的问题是“爬到一阶”、“爬到二阶”、“爬到三阶”、“爬到四阶”、“爬到五阶”。

至于“爬到零阶”、“爬到负一阶”、“爬到负二阶”以及“爬到六阶”、“爬到七阶”没有必要计算。

2-3. lookup table

建立六格的阵列，储存五个问题的答案。

表格的第零格不使用，第一格是“爬到一阶”的答案，第二格是“爬到二阶”的答案，以此类推。

如果只计算“爬完五阶”，也可以建立三个变数交替使用。

2-4. computational sequence

因为每个问题都依赖“阶数少一阶”、“阶数少二阶”这两个问题，所以必须由阶数小的问题开始计算。

计算顺序是“爬到一阶”、“爬到二阶”、……、“爬到五阶”。

2-5. initial states / boundary

最先计算的问题是“爬到一阶”与“爬到二阶”，必须预先将答案填入表格、写入程式码，才能继续计算其他问题。心算求得“爬到一阶”的答案是 1，“爬到二阶”的答案是 2。

最后计算的问题是原问题“爬到五阶”。

为了让表格更顺畅、为了让程式码更漂亮，可以加入“爬到零阶”的答案，对应到表格的第零格。“爬到零阶”的答案，可以运用“爬到一阶”的答案与“爬到两阶”的答案，刻意逆推而得。

最后可以把初始值、尚待计算的部份、不需计算的部分，统整成一道递迴公式：

f(n) =
 { 0                , if n < 0               [Exterior]
 { 1                , if n = 0               [Initial]
 { 1                , if n = 1               [Initial]
 { f(n-1) + f(n-2)  , if n >= 2 and n <= 0="" 5="" [compute]="" {="" ,="" if="" n=""> 5               [Exterior]

UVa 11069

3. 实作

直接用递迴实作，而不使用记忆体储存各个问题的答案，是最直接的方式，也是最慢的方式。时间複杂度是 O(f(n))。问题一而再、再而三的出现，不断呼叫同样的函式求解，效率不彰。刚接触 DP 的新手常犯这种错误。

正确的 DP，是一边计算，一边将计算出来的数值存入表格，以后便不必重算。这裡整理了两种实作方式，各有优缺点：

1. Top-down
2. Bottom-up

3-1. Top-down

Dynamic Programming: counting / optimization

范例：楼梯路线（Staircase Walk），计数问题

一个方格棋盘，从左上角走到右下角，每次只能往右走一格或者往下走一格。请问有几种走法？

对于任何一个方格来说，只可能“从左走来”或者“从上走来”，答案是两者相加。

“从左走来”是一个规模更小的问题，“从上走来”是一个规模更小的问题，答案是两者相加。

二维阵列的每一格对应每一个问题。设定第零行、第零列的答案，再以迴圈依序计算其馀答案。

时间複杂度分析：令 X 和 Y 分别是棋盘的长和宽。计算一个问题需要 O(1) 时间（两个子问题答案相加的时间）。总共 X*Y 个问题，所以计算所有问题需要 O(XY) 时间。

空间複杂度分析：总共 X*Y 个问题，所以需要 O(XY) 空间，简单来说就是二维阵列啦！如果不需要储存所有问题的答案，只想要得到其中一个特定问题的答案，那只需要一维阵列就够了，也就是 O(min(X, Y)) 空间。

节省记忆体是动态规划当中重要的课题！

如果只打算求出一个问题，那麽只需要储存最近算出来的问题答案，让计算过程可以顺利进行就可以了。

两条阵列轮替使用，就足够储存最近算出来的问题答案、避免 c[i-1][j]超出阵列范围。

Dynamic Programming: state / DAG（Under Construction!）

State / DAG

以 State 和 DAG 的观点，重新看待动态规划。

动态规划得类比成“ 状态 State ”：“问题”变“状态”，“全部问题”变“状态空间”，“递迴关係”变“状态转移函式”。

动态规划得类比成“ 有向无环图 DAG ”：既然递迴关係不能循环，显然就是 DAG。“问题”变“点”，“递迴关係”变“边”，“计算顺序”变“拓扑顺序”。

即便读者不懂 State 和 DAG 也没关係，只要抓住两个要点：每个小问题各是一个状态，只有数值范围不同；状态之间是单行道，依序求解，不能循环。

ICPC 5104

范例

Maximum Subarray 
1D p-Center Problem 
Longest Increasing Subsequence 
Longest Common Subsequence 
Longest Palindrome Substring 
0/1 Knapsack Problem 
Shortest Path

范例：巴斯卡三角形（Pascal's Triangle）

巴斯卡三角形左右对称，可以精简掉对称部分。巴斯卡三角形逆时针转 45˚，视觉上就可以一一对应至表格。

时间複杂度为 O(N^2)，空间複杂度为 O(N^2)。

UVa 369 485 10564

范例：矩阵相乘次序（Matrix Chain Multiplication）

一连串矩阵相乘，无论从何处开始相乘，计算结果都一样，然而计算时间却有差异。两个矩阵，大小为 a x b 及 b x c，相乘需要 O(a*b*c) 时间（当然还可以更快，但是此处不讨论）。那麽一连串矩阵相乘，最少需要多少时间呢？

一连串矩阵，从最后一次相乘的地方分开，化作两串矩阵相乘。考虑所有可能的分法。

f(i, k) = min { f(i, j) + f(j+1, k) + r[i] * c[j] * c[k] }
         i≤j< k

f(i, k)：从第 i 个矩阵乘到第 k 个矩阵，最少的相乘次数。
r[i]：第 i 个矩阵的 row 数目。
c[i]：第 i 个矩阵的 column 数目。

Dynamic Programming: bitset

bitset

bitset 是一个二进位数字，每一个 bit 分别代表每一件东西，1 代表开启，0 代表关闭。例如现在有十个灯泡，编号设定为零到九，其中第零个、第三个、第九个灯泡是亮的，剩下来的灯泡是暗的。我们用一个 10 bit 的二进位数字 1000001001，表示这十个灯泡的亮暗状态。

建立一个大小为 2^10 的阵列，便囊括了所有可能的状态。阵列的每一格，就代表一种灯泡开关的状态。

Dynamic Programming: stack / deque

概论

F[n] = min/max { F[i] ⋅ W[i] + C[i] }
       0<=i< n="" <="" pre="">

F[n]是未知数，F[i] W[i] C[i]是已知数。计算到 F[n]时，F[i]早已计算完毕，因此 F[i]是已知数。

这种形式的 recurrence，直接计算是 O(N^2)。此处介绍更快的演算法。

stack

括号配对极值。stack 保持严格递增（严格递减），以便即时获取过往最大值（最小值）、即时移除已处理数值。

          maximize problem
          keep monotone increasing  ---->
      ---------------------------------------
stack | F[2] | F[4] | F[6] |   ...   | F[10] 
      ---------------------------------------
                                      ^^^^^^^ extract maximum
                clean tops until monotonicity
                    then push new F[i] at top

F[i]放入尾端。放入前，先清除尾端数值，使得 F[i]放入尾端之后，stack 呈严格递增。最大值从尾端取得。

范例：Largest Empty Rectangle

详见“ Largest Empty Rectangle ”。

范例：All Nearest Smaller Values

http://en.wikipedia.org/wiki/All_nearest_smaller_values

deque

滑动视窗极值。deque 保持严格递增（严格递减），以便即时获取过往最小值（最大值）、即时移除已处理数值。

            minimize problem
            keep monotone increasing  ---->
        --------------------------------------
deque    F[2] | F[4] | F[6] |   ...   | F[10] 
        --------------------------------------
        ^^^^^^                         ^^^^^^^
     extract minimum          clean tails until monotonicity
                              then push new F[i] at end

F[i]放入尾端。放入前，先清除尾端数值，使得 F[i]放入尾端之后，deque 呈严格递增。放入后，再清除头端数值，使得元素个数符合滑动视窗大小。最小值从头端取得。

中文网路称为“单调队列优化”。

ICPC 4327

范例：Maxium Sum Subarray

详见“ Maxium Sum Subarray ”。

范例：Maximum Average Subarray

详见“ Maxium Average Subarray ”。

由于斜率是关键，因此中文网路称为“斜率优化”。

Dynamic Programming: convex hull

概论

F[n] = min/max { F[i] ⋅ W[n] + C[i] }
       0<=i< n="" <="" pre="">

W[i]换成 W[n]。前章节 W[i]不随时间 n 而变化，但是各有不同；本章节 W[n]随著时间 n 而变化，但是一律相同。

envelope

直线 y = F[i] x + C[i]、铅直线 x = W[n]，交点 Y 座标是 F[n]。

最小（大）值对应最低（高）交点。

最小（大）值位于下（上）包络线。

convex hull

如果讨厌包络线，可透过点线对偶，从包络线变成凸包。

直线穿过点(F[i], -C[i])，斜率 W[n]，Y 轴截距是-F[n]。

垂直方向翻转，让最小（大）值对应最低（高）截距。

直线穿过点(F[i], C[i])，斜率-W[n]，Y 轴截距是 F[n]。

最小（大）值位于下（上）凸包的切线，跟 Y 轴的交点。

如果不熟悉点线对偶，可透过移项推导，得到相同结论：

http://www.cnblogs.com/Rlemon/p/3184899.html

根据 F[i]与 W[n]的性质，时间複杂度随之变化：

一、W[n]皆相同：不必维护凸包，只需维护每个点在“斜率-W[n]的直线的垂直方向上”的先后顺序，彷彿“单调队列优化”。一个常见的例子是 W[n] = 1。O(N)。

二、F[i]与 W[n]皆单调：Andrew's monotone chain 维护下凸包（求最小值时）。切线斜率-W[n]递减/增。直接从上次切点开始，往左/右找到新切点。O(N)。

三、F[i]单调：Andrew's monotone chain 维护下凸包（求最小值时）。切线斜率-W[n]会变。三分搜寻找到切点，或者二分搜寻凸包斜率找到切点。O(NlogN)。

四、无特别性质：动态凸包资料结构。O(NlogNlogN)。

UVa 12524 ICPC 5133

范例：1D p-Median Problem

详见“ p-Median Problem ”。

https://algnotes.wordpress.com/2013/10/25/p-median/

范例：Bounded Knapsack Problem

详见“ Bounded Knapsack Problem ”。

Dynamic Programming: unimodal function

概论

F[n] = min/max { M[i] }   M[i] is monotone/unimodal
       0<=i< n="" <="" pre="">

根据 M[i]的性质，时间複杂度随之变化：

一、F[n]的子问题们，其答案 M[0]...M[n-1]恰好是单调函数：根本没啥好算，最佳解显然是第一个（最后一个）子问题。O(N)。

二、F[n]的子问题们，其答案 M[0]...M[n-1]恰好是单峰函数：三分搜寻山峰，或者二分搜寻斜率。O(NlogN)。

三、每个问题的单峰函数，山峰位置恰好递增（往右移动）：用同一条扫描线寻找山峰。O(N)。

unimodal function

什麽时候会是单峰函数呢？举两个例子。

F[n] = min { max(F[i], G[i]) + 5 }
     0<=i< n="" <="" pre="">

F 递增、G 递减，则 max(F[i], G[i]) + 5 是单峰函数。不过这个例子有点蠢，山谷恰好永远不动。

F[n] = min { F[i] + G[i] }
     0<=i< n="" <="" pre="">

F G 皆是凸函数，则 F[i] + G[i]是凸函数，即是单峰函数。不过这个例子也有点蠢，山谷恰好永远不动。

范例：Egg Drop

一堆蛋，已知耐力皆相同，不知耐力为多少。试求耐力。

耐力是以楼层衡量：大于某楼层，摔下必破，无法重複使用；小于等于某楼层，摔下必不破，完全不会折损，可以重複使用。

这个问题有许多变形，此处讨论实验场地是 n 层楼的情况：

一、最少摔破几颗蛋？需要事先准备几颗蛋？

答：一颗蛋。从一楼开始摔，逐步上楼，直到摔破为止。

二、无限多蛋，运气不好时，最少摔几次？

答：二分搜寻。F[0] = 0, F[1] = 1, F[n] = F[ceil((n-1)/2)] + 1。

三、一颗蛋，运气不好时，最少摔几次？

答：n 次。耐力不幸是 n 楼，从一楼开始摔，要摔 n 次。

四、两颗蛋，运气不好时，最少摔几次？

答：首发选在 i 楼。如果摔破了，剩下一颗蛋，只好从一楼开始测试；最差的情况，耐力是 i-1 楼，要摔 i-1 次。如果没有摔破，仍是两颗蛋，问题仍相同，范围缩小成 n-i 楼。两种情况取最大值。穷举 i，找到次数最少者。

F[n] = 1 +  min { max(i-1, F[n-i]) }
          1<=i<=n f[n]="1" +="" min="" {="" max(i,="" f[n-1-i])="" }="" 调整索引值="" 0<="i<" n="" <="" pre="">

i 递增，F[n-1-i]递减，因此 max(i, F[n-1-i]) 是单峰函数，而且山谷持续往右移动，可以使用扫描线解决。另外也有数学公式解：

https://www.ptt.cc/bbs/Prob_Solve/M.1398152375.A.C05.html

五、k 颗蛋，运气不好时，最少摔几次？

答：留给读者。

UVa 10934 882 ICPC 4554

范例：Isotonic Regression

https://algnotes.wordpress.com/2015/01/28/isotonic-regression/

http://stackoverflow.com/questions/10460861/

Dynamic Programming: totally monotone matrix

概论

F[n] = min/max { M[i][n] }   M[i][n] is monotone/totally monotone
       0<=i< n="" <="" pre="">

根据 M[i][n]的性质，时间複杂度随之变化：

一、M[i][n]是上三角 monotone matrix：似乎没有特别快的演算法，仍是 O(N^2)。

二、M[i][n]是上三角 totally monotone matrix：两个演算法，O(NlogN) 与 O(Nα(N))。以下只谈第一个，分成凹凸两种情况。

三、M[i][n]是上三角 Monge matrix：至今仍然没有专属演算法，大家都是沿用 totally monotone matrix 的演算法。

Monge matrix 比较常见。常见的形式是：

F[n] = min/max { F[i] ⋅ W[i] + C[i][n] }
       0<=i< n="" (1)="" f[i]="" is="" non-negative="" (2)="" w[i]="" (3)="" c[i][n]="" monge="" thus="" m[i][n]="F[i]" ⋅="" +="" (non-negative="" linearity)="" <="" pre="">

区间观点：本章节是尾端区间 C[i,n]，前章节是头端区间 C[0,i]（省略了 0）。

时变观点：本章节 C[i][n]随著时间 n 而变化（C[i][n]改写成 C[n][i]），前章节 C[i]不随时间 n 而变化。

Monge matrix 的不等式曾经称作 quadrangle inequality，因此中文网路称为“四边形不等式优化”。

convex totally monotone matrix

大意：直条最小值位置往上递减。使用 stack。

首先画出 C[i][n]，一个上三角矩阵。图片省略了实际数值。

计算 F[1]：F[0] ⋅ W[0]加到 C[0][1]即得。

计算 F[2]：F[0] ⋅ W[0]加到 C[0][2]，F[1] ⋅ W[1]加到 C[1][2]，取直条 C[:][2]最小值。

以此类推。时间複杂度为 O(N^2)。

重新反省计算过程，改良演算法：

一、算出 F[i]之后，F[i] ⋅ W[i]加到对应的横条，比较省事。由于 F[i] ⋅ W[i]非负，结果仍是凸 Monge 矩阵，亦是凸全单调矩阵！

二、计算 F[i]，即是取直条最小值。随时记录每个直条的最小值位置，每次 F[i] ⋅ W[i]加到对应的横条，顺手更新最小值位置。

得到一个更容易解释的演算法。时间複杂度仍为 O(N^2)。

凸全单调矩阵（直条版本），每个子矩阵都是凸单调矩阵，直条最小值位置总是往上递减！

算出 F[i]之后，从左往右更新最小值位置。最小值位置可能变 i、可能不变。变与不变有著唯一一条分界线，左侧一律变 i，右侧一律不变，以满足递减性质。

虽然可以提早 break，但是时间複杂度仍为 O(N^2)。

位置相同者，合併成一个区间，最多 N 个区间。每当更新最小值位置，从左往右判断每个区间的右端位置，直到遭遇不变的位置。然后二分搜寻该区间，找到分界线。

使用 stack 实作，一笔资料有两个参数：区间右端的直条编号、最小值位置。每回合 pop 一些区间、做一次二分搜寻、push 一个区间。时间複杂度为 O(NlogN)。

concave totally monotone matrix

大意：直条最小值位置往下递增。使用 deque。

改成从右往左更新最小值位置。时间複杂度为 O(NlogN)。

范例：Word Wrap

https://algnotes.wordpress.com/2013/10/26/word-wrap/

Dynamic Programming: interval

Knuth's optimization

F[i,j] =  min  { F[i,k] + F[k,j] + C[i,j] }
        i<=k<=j c[i,j]="" satisfies="" "monge="" matrix"="" and="" "sorted="" matrix".="" (upper="" trianglar)="" (toward="" ↗)="" interval="" coverage:="" c[a,b]="" <="C[c,d]" when="" [a,b]="" ⊆="" [c,d]="" c<="a<=b<=d" sorted="" matrix:="" ←="" ↓="" pre="">

四边形不等式，得到单调性的左边界。已排序矩阵，得到单调性的右边界。

问题依大小排列，问题的最佳分割点恰好也依大小排列。中文网路称为“决策单调性”。

http://www.quora.com/What-is-Knuths-optimization-in-dynamic-programming

范例：Optimal Binary Search Tree

N 笔资料，欲建立成一棵“ Binary Search Tree ”。并且预测了每笔资料的搜寻次数。

请问 Binary Search Tree 是什麽形状，才能让拜访到的节点数量最少呢？也就是说，每个节点的“深度”乘上“搜寻次数”，总和要最小。