DolorHunter 
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
递归代码简洁又可读，但是因为会可能重复计算子问题，所以往往不能直接写递归。我们需要有一块空间用来存储已经计算过的数据，这样再次使用时只需要取用，就避免了重复运算。当然动态规划也不只能用在对递归的优化上，很多具有状态转移的 Brute Force 办法也能用DP进行优化。
动态规划被用来求最优解，难点主要就是找递归关系(状态转移方程)。
动态规划
动态规划应用于子问题重叠的情况：
- 问题有递归解法（状态转移）
- 开辟存储空间；
- 找到计算子问题的顺序
比如说动态规划的常用例子，Climbing Stairs（上楼梯问题），Wood Cutting (木条/钢条切割) ，Knapsack （背包问题）等等就是如此实现的。
Climbing Stairs (爬楼梯问题)
爬楼梯问题其实就是斐波那契数列(Fibonacci sequence)，只不过用每次可以上一级或两级楼梯来包装了一下。状态转移方程都是 $T(n) = T(n-1) + T(n-2)$，即第 n 次的可能性为 n-1 次的可能性与 n-2 次的可能性之和。
斐波那契数列常用递归计算，但是因为递归会重复计算内容，例如下面的 fib(5) 将 fib(3) 计算了 2 次，fib(2) 计算了 3 次，fib(1) 计算了 4 次，fib(0) 计算了 2 次。时间复杂度为O($2^n$)。
def fib(n):
if n <= 1:
return n
return fib(n − 1) + fib(n − 2)
sourse: Wikipedia - Fibonacci Tree 5.svg
因此我们在找到 Base Case (n=0为0, n=1为1) 和状态转移方程 $T(n) = T(n-1) + T(n-2)$ 后，可以用 DP 来实现这个问题的解。开辟一块存储空间，之后从小到大逆序计算 fib。计算后的 fib 存入存储空间中，需要用时从存储中取值即可。时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。
# big o = n
def fib(n):
mem = [0 for _ in range(n+1)]
for i in range(n+1):
if i <= 1:
mem[i] = i
else:
mem[i] = mem[i-1] + mem[i-2]
return mem[n]
ans = fib(5)
print(ans)
# 5
Wood Cutting (木条/钢条切割)
木条切割问题给定一段钢条，和不同长度的价格，问如何切割使得总价格最大。通过找到状态转移方程 best 计算最大总价格，并且把最大价值选择的切口记录到 choice 中。
$best[i]=max^{i}_{j=1}\left { best[j]+min(best[i]+price[i-j]) \right }$
$choice[i] = choice[j-1]+[i-j+1]$
初始化 best 和 choice，并且通过两层遍历找到最优解，存入 best[i] 与 choice[i]。当遍历完成后，结果在 best[n] 与 choice[n] 中。时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。
# big o = n^2
def wood_cutting(price):
n = len(price)
best, choice = [0 for _ in range(n+1)], [[] for _ in range(n+1)]
for i in range(1, n+1):
temp_max = 0
temp_choice = []
for j in range(1, i+1):
temp = best[j-1] + price[i-j]
if temp > temp_max:
temp_max = temp
temp_choice = choice[j-1] + [i-j+1]
best[i] = temp_max
choice[i] = temp_choice
return best[n], choice[n]
ans = wood_cutting([1,18,24,36,50,50])
print(ans)
(54, [2, 4])
射击问题
射击问题类似钢条切割问题。陨石与时间关系为 x，蓄力时间与攻击关系为 d，要求如何射击使得击落陨石最多。
例如 (x1, x2, x3, x4) = (1, 10, 10, 1), (d1, d2, d3, d4) = (1, 2, 4, 8)。最佳解法为 5（在 3 和 4 的时候射击）。
# big o = n^2
def best_laser_dp(x, d):
xn, dn = len(x), len(d)
best, choice = [0 for _ in range(xn+1)], [[] for _ in range(xn+1)]
for i in range(1, xn+1):
temp_max, temp_choice = 0, []
for j in range(1, i+1):
temp = best[j-1] + min(x[i-1], d[i-j])
if temp > temp_max:
temp_max = temp
temp_choice = choice[j-1] + [i]
best[i] = temp_max
choice[i] = temp_choice
return best[xn], choice[xn]
ans = best_laser_dp([1, 10, 10, 1], [1, 2, 4, 8])
print(ans)
# (5, [3, 4])
Knapsack 0/1 (0/1背包问题)
已知一些物品 (k) 的重量 ($w_k$)、价值 ($v_k$)，以及背包的总容量 (w)，求背包可以装载的最大价值。
背包问题为二维DP问题，比前面的爬楼梯、钢条切割与射击问题要难一些。背包问题的 Base Case 为 k=0 或 w=0 时, best[k, w]=0，即没有物品用于装载或者是背包没有装载空间时，价值为 0。
背包装载分为三种情况：
- 没有空位装载物品 best[k, w] = best[k-1, w]
- 有空位并且装载物品 best[k, w] = best[k, w-wk] + vk
- 有空位但是不装载物品 best[k, w] = best[k-1, w]
# big o = n^2
def knapsake(val, weight, max_weight):
k, w = len(val), max_weight
best = [[0 for _ in range(w + 1)] for _ in range(k + 1)]
for i in range(k + 1):
for j in range(w + 1):
if i == 0 or j == 0:
best[i][j] = 0 # base case
elif j - weight[i-1] < 0:
best[i][j] = best[i-1][j] # case 1
else:
val_with_kth = best[i-1][j-weight[i-1]] + val[i-1] # case 2
val_without_kth = best[i-1][j] # case 3
best[i][j] = max(val_with_kth, val_without_kth)
return best[k][w]
ans = knapsake([3,5,6], [1,2,3], 4)
print(ans)
# 9
Matrix Chain Multiplication (矩阵串乘法)
不同位置矩阵相乘的结果不同，目标将矩阵串相乘，并且找到结果最小的乘法结果。
如果使用 Brute Force 解法，复杂度约为 $Ω(4^n/n^{(3/2)})$。但使用 DP 复杂度为 $O(n^3)$。代码参考 mskitten - dp方法论——由矩阵相乘问题学习dp解题思路。
# big o = n^3
def mat_chain_mul(chain):
n = len(chain)
best = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if i == j:
best[i][j] = 0
else:
temp_min = 65535
for k in range(i, j):
ri, ck, cj = chain[i][0], chain[k][1], chain[j][1]
temp = best[i][k] + best[k+1][j] + ri*ck*cj
if temp < temp_min:
temp_min = temp
best[i][j] = temp_min
return best[0][n-1]
ans = mat_chain_mul([[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]])
print(ans)
# 15125
Perfect Squares（长方形分割为正方形问题）
将 n*m 的长方形切分为若干个正方形 (Perfect Squre)，求最小需要切几次。遍历行列，并且用 a 作为分割线计算最小切割数量，时间复杂度 O($n^3$)。思路参考 CSDN - 动态规划处理长方形分割为正方形问题。
# big o = n^3
def chocolate(n, m):
cut = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
for j in range(m+1):
# perfect square
if i == j:
cut[i][j] = 1
# cut[i][j] = min(cut[i-a][j] + cut[a][j]
# cut[i][a] + cut[i][j-a])
else:
temp_min = 65535
for a in range(1, i):
temp = cut[i-a][j] + cut[a][j]
if temp < temp_min:
temp_min = temp
for a in range(1, j):
temp = cut[i][a] + cut[i][j-a]
if temp < temp_min:
temp_min = temp
cut[i][j] = temp_min
return cut[n][m]
ans = chocolate(5, 6)
print(ans)
# 5
Highway Billboard (公路广告牌)
广告牌问题要求在 D 间隔外安装广告牌，要求整体收益最大。有点类似 0/1 背包问题，但是选项更为简单，只需要找到距离为 D 以上的广告牌 (best buddy)，比较当前广告牌和 best buddy 收益和与前一个广告牌的收益和，取两值的最大效益即可。难点在于需要预先计算 best buddy，就能把复杂度从 $n^2$ 降低至 $n$。数据参考 includehelp - Highway billboard。
# big o = n
def highway_billboard(x, val, dist):
n = len(x)
r, l = n-1, n-1
# pre-process best buddy
best_buddy = [0 for _ in range(n)]
best = [0 for _ in range(n)]
while r > 0 and l > 0:
if x[r] - x[l] >= dist:
best_buddy[r] = l
r -= 1
l = r
else:
l -= 1
for i in range(1, n):
best[i] = max(best[i-1], val[i] + best[best_buddy[i]])
return best[n-1]
ans = highway_billboard([6,7,12,13,14], [5,6,5,3,1], 5)
print(ans)
# 11
Longest Common Sub-sequence (最长公有子序列)
已知两个字符串，求最长公有子序列。公有序列并不需要连续，例如 abcb 和 bdcabd 的最长公有序列为 bcb。
最长公有序列分为两种情况：
- 元素相等 x[i]==y[j]，LCS[i][j] = LCS[i-1][j-1] + 1
- 元素不等 x[i]!=y[j]，比较 x[i-1]==y[j]，x[i]==y[j-1]，LCS[i][j] 取长的序列
# big o = n^2
def longest_common_subsequence(x, y):
xn, yn = len(x), len(y)
lcs = [[0 for _ in range(yn+1)] for _ in range(xn+1)]
for i in range(xn+1):
for j in range(yn+1):
if i == 0 or j == 0: # base case
lcs[i][j] = 0
elif x[i-1] == y[j-1]: # eq
lcs[i][j] = lcs[i-1][j-1] + 1
else: # not eq
lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
return lcs[xn][yn]
ans = longest_common_subsequence('abcb', 'bdcab')
print(ans)
# 3
Typesetting (整齐打印)
调整每行单词的数量，使得每行行末的空格方差最小。题目参考 huihoo - Application: Typesetting Problem
# big o = n^2
def typesetting(words, m):
n = len(words)
best, choice = [0 for _ in range(n+1)], [[] for _ in range(n+1)]
s = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
s[i][i] = m - words[i-1]
for j in range(i+1, n+1):
s[i][j] = s[i][j-1] - words[j-1] - 1
if s[i][j] < 0:
while j <= n:
s[i][j] = 65535
j += 1
break
for i in range(1, n+1):
temp_min = 65535
temp_choice = []
for j in range(i):
temp = best[j] + s[j+1][i] ** 2
if temp < temp_min:
temp_min = temp
temp_choice = choice[j-1] + [j]
best[i] = temp_min
choice[i] = temp_choice
return best[n], choice[n]
ans = typesetting([2,3,3,4,2,6,2,3,3,5,2,6,2,3,3,3,2,7,2,3,3,3,2,12,2,3,3,5,2,7,2,3,3,5,2,12,2,3,3,6,2], 42)
print(ans)
# (123, [0, 7, 15, 24, 34])
总结
DP 问题大概的流程可以分为三步：Base Case -> 状态转移关系 -> 分支条件。
DP 问题的模板包括：开辟 best 空间（n+1），按顺序循环计算 best，返回 best[n]（通常为末元素）。
def dp(arr):
n = len(arr, val)
# 通常 0 为 base case 存放位置，计算 1~n
best = [0 for _ in range(n+1)]
for i in range(n+1):
# 第0行/列通常存放 Base Case
if i == 0:
best[i] = 0
# 分支条件1
elif i < best[i-1]:
# 状态转移方程1
best[i] = min(best[i-1], best[i-2] + val[i])
# 分支条件2
else:
# 状态转移方程2
best[i] = max(best[i-3], best[i-4] + val[i])
return best[n]
不同的 DP 问题区别通常在于 best 的规模(一维或二维，或者多个 best)，循环方向，分支条件，最佳化条件 (max/min)。DP 的难点主要是在抽象出状态转移方程，以及描述各个参数的关系和范围。
参考资料：
算法笔记101 - 分治算法 Divide and Conquer
