1. 基本定义
动态规划（Dynamic Programming，dp）是对普通递归（分治法）的改进。这不是一种具体的算法，是一种解题和编程的思路。是一种求解全局最优的思路。
Programming 是表格的意思，而非编程的意思。动态规划这个名词我的理解是，我们需要维护一个不断变化的表格，所以这是动态的且是可规划的。（其实也有一种说法是这个名字其实是为了应付领导，随便取的一个看起来很高大上的名字，未加考证，当趣闻看待即可，hhh）
2. 适用条件
我们把每个时刻的递归称为一个子问题。
- 对子问题本身而言，任意两个子问题间的步骤是相互独立的。（例如，我们有问题q分出q1和q2两个子问题，如果q1用到的变量，q2没有用到，则q1和q2就是独立的）
- 对整个问题而言，具有重叠子问题，每个子问题都会对结果产生影响。所以，动态规划问题一般是序列问题，而非离散问题。（这一步并不是必要的，但是如果不符合这一步，问题本身其实已经退化为一般的分治法）
- 每个子问题都有最优解，即每个子问题都必须是凸优化问题。
3. 设计步骤
- 求子问题和初始状态
- 确定状态转移方程 \(F(n) = G(\vec N)+f(\vec N)\)
- 编程实现转移方程，可以采用带备忘的自顶向下法（下面直接称递归的方法）或者不带备忘的自底向上法（下面直接称循环的方法），这两种方法的时间复杂度是相近的。
- 求最优解路径（如果只需要求最优解的值，则这一步可以忽略）
其实上面一套下来，就是高中学过的数学归纳法的步骤-_-||
4. 一些例子
动态规划难点在于怎么求状态转移方程，其变种太多了，但其实来来去去都是那三板斧，开始解题时把模板套上，然后下面只能靠个人去领悟了，只可意会不能言传~ 下面简单的介绍几个比较经典的例子，其他的举一反三，“伺机”而变即可。
其实，动态规划的问题无非就两种：求达到目的的方法总数或求达到目的的最优解。无论是哪一种，我们首先都应该把总数或最优值设为 \(F(X)\)，然后根据题目提供自变量（但一些自变量隐藏得会很深）的数目判断 \(X\) 的维度。然后从上一时刻入手，根据自变量和 \(F(X)\) 的变化给出当前时刻的转移方程，最后求初始值，就可以得到完整的转移方程了。
另外，下面的例子只展示了核心的代码，一些参数的非法边界判定可能没有给出。
4.1. 一维模型
4.1.1. 求符合条件数
4.1.1.1. 区间划分问题-钢管切割
问题描述
已知一段 \(n\) 米长的钢管，可以切成1米或2米的小段，问：把钢管全部切完一共有多少种切法？
求解状态方程
求子问题。设已经切了\(x\)米时有 \(F(x)\) 种切法，那么切了\(x\)米的前一个状态只能是切了 \(x-1\) 米或 \(x-2\) 米，所以当前切法总数应该是前两种切法总数之和。
求初始状态。即求 \(x-1\) 或 \(x-2\) 得初始状态，即求 \(x=1\) 或 \(x=2\) 时 \(F(x)\) 值。
故可得下面转移方程（其实就是斐波那契数列）。 \[ F(x) = \left \{ \begin{array}{ll} 1 &, x=1 \\ 2 &,x=2 \\ \text{sum} \{ F(x-1), F(x-2) \} &,2<x \leq n \end{array} \right . \]
循环
def bottom_up(n, f): for i in range(3, n + 1): f[i] = f[i - 1] + f[i - 2] return f[n]递归
def memoized(n, f): if f[n] > 0: return f[n] else: f[n] = memoized(n - 1, f) + memoized(n - 2, f) return f[n]程序验证
输入如下测试数据：
n = 10 f = [0] * (n + 1) f[1:3] = 1, 2 # 赋初值 bottom_up(n, f) memoized(n, f)得到如下中间缓存矩阵
f = [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]求解
f[n]即 n 米长的钢管的切割方法总数。
4.1.2. 求最值
4.1.2.1. 区间划分问题-钢管切割
问题描述
已知对一段钢管切成 \(i\) 米长的利润为 \(p_i\) ，其中， $1 i l $ 且 \(i\) 为自然数。现在，有一段长 \(n\) 米的钢管，怎样切割可使利润最大化。假设切割不产生成本。
求解状态方程
求子问题。设切割 \(x\) 米长的钢管的最大利润为 \(F(x)\)，把\(x\)分成两部分，即 \(x=i+j(i>0,j>0)\)，有 \(F(x) =F(i) + F(j)\) ，因为 \(i\) 米和 \(j\) 米的钢管的最大利润我们是已知的，所以我们有一个关于不同切割的利润的集合，集合中的最大值记为 \(x\) 的最大利润。
求初始状态。初始状态为切割0米长的钢管。
故可得下面转移方程 \[ F(x) = \left \{ \begin{array}{ll} 0 &, x=0 \\ \max\{ p_i + F(x-i) | 1 \leq i \leq \min\{l, x\} \} &,0 < x \leq n \end{array} \right . \]
循环
def bottom_up(n, l, p, f, s): for j in range(1, n + 1): # x的取值范围 for i in range(1, min(l + 1, j + 1)): # i的取值范围 # 转移方程表达式 q = p[i] + f[j - i] if q > f[j]: f[j] = q s[j] = i return f[n]递归
def memoized(n, l, p, f, s): if f[n] > 0: # 说明已经有缓存过该时刻的数据，直接返回即可 return f[n] else: for i in range(1, min(l + 1, n + 1)): # 转移方程表达式 q = p[i] + memoized(n - i, l, p, f, s) if q > f[n]: f[n] = q s[n] = i return f[n]程序验证
输入如下测试数据：
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] l = len(p) - 1 n = 11 # n+1是因为0米也是一种状态，需要一份内存来存储，或者说，下标为i表示第i米的状态 # 如果不知道什么时候要 n+1，建议全都使用n+1，结果是不会出错的，就是会浪费一些内存而已 # 初始化为0，是因为0为该问题下为最小值 f = [0] * (n + 1) # 每个时刻状态方程的值 s = [0] * (n + 1) # 最优解的路径 bottom_up(n, l, p, f, s) memoized(n, l, p, f, s)得到如下中间缓存矩阵
f = [0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30, 31] s = [0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10, 1]求最优解
例如，求解切割7米长的钢管的最大利润：
当
i=7时，s[7]=1，表示先切割1米长的钢管，此时，i=7-1=6,s[6]=6，表示再切割6米长的钢管，此时，i=0，读取结束。所以，钢管切成1米和6米长的钢管会使利润最大化，其中最大值为f[7]=18。
4.2. 二维模型
现实中遇到问题基本都是二维模型
4.2.1. 求符合条件数
4.2.1.1. 前缀问题-机器人寻路
问题描述
在一个m*n的网格中，开始时位于左上角，每次只能向下或向右移动一格，现在要到达右下角，问：有多少种移动的方式。
求解状态方程
求子问题。设当前坐标 \((i,j)\) 是通过 \(F(i,j)\) 种方式到达的，由于只能向下或向右移动一格，那么其前一个状态的坐标只能是 \((i-1,j)\) 或 \((i, j-1)\)，所以当前坐标移动方式的数量也应该是前一个状态的两个坐标的移动方式之和。
求初始状态。即求\((i-1,j)\) 或 \((i, j-1)\) 的初始状态，即求 \(i=1,j=0\) 或 \(i=0,j=1\) 时 \(F(i, j)\) 的值
故状态方程如下
\[ F(i, j) = \left \{ \begin{array}{ll} 1 &, i=1,j=0 \\ 1 &,i=0,j=1 \\ \text{sum} \{F(i-1, j), F(i, j-1) \} &,1<i \leq m, 1<j \leq n \end{array} \right . \]
循环
def bottom_up(m, n, f): for i in range(1, m): for j in range(1, n): f[i][j] = f[i - 1][j] + f[i][j - 1] return f[m - 1][n - 1]递归
def memoized(i, j, f): if f[i][j] > 1: return f[i][j] else: f[i][j] = memoized(i - 1, j, f) + memoized(i, j - 1, f) return f[i][j]程序验证
输入如下测试数据：
m, n = 7, 3 # 这里有一个减少空间复杂度的小trick：在这道题的条件下，可以改写为 `f = [[1] * n] * m` # 后者的写法相当于 `a = [1] * n, f = a * m` # 尽管后者的写法改变f[i][j]时，会改变f[i][:]所有的值，但我们不会再利用到x<j的区域，而对于x>j的值，后面会重新计算并覆盖 # 后者的写法虽然只有最终结果是有效的，中间的缓存矩阵是没有什么价值的，但空间复杂度由前者的 O(n*m) 减少为后者的 O(n) f = [[1] * n for _ in range(m)] bottom_up(m, n, f)得到如下中间缓存矩阵
f = [[1, 1, 1], [1, 2, 3], [1, 3, 6], [1, 4, 10], [1, 5, 15], [1, 6, 21], [1, 7, 28]]求解
f[m-1][n-1]即 m*n 网格的不同移动方式数量。
4.2.2. 求最值
4.2.2.1. 数轴问题-01背包
问题描述
已知有\(n\)个物品，第 \(i\) 物品的重量为 \(w_i\)，价值为 \(v_i\)，背包的最大可装载的重量为 \(W\)，所有物品只能整个装进背包，问：怎样装可使价值最大化。
求解状态方程
首先，这个问没有规定装载物品的顺序，乍一看是离散的问题，感觉不能用动态规划解决。但实际上，这是一道伪离散问题。上述问题可以转化为一个物品的序列，有序的装载进背包，但装载的时候，每个物品都可以选择装载或丢弃。这样就可以用动态规划进行解决了。
求子问题。设当前装载第 \(i\) 个物品，背包剩余的重量为 \(j\)，其最大价值为 \(F(i,j)\)，那么这个物品有两种选择：选择丢弃，那么当前价值为前一状态（即第 \(i-1\) 个物品）的最大价值；选择装填（为了使当前背包剩余装载仍为 \(j\) ，则前一状态的剩余装载应为 \(j-w_i\) ，这里是一个比较难理解的点），那么当前价值为前一状态的最大价值加上当前物品的价值。
求初始状态。即求 \(i-1\) 和 \(j-w_i\) 的初始状态，但 \(j-w_i\) 的初始状态是不能直接给出的（或者说，\(j\)的状态不能直接给出），所以，使用循环的方法的时候，只能暴力枚举所有 \(j\) 的状态（如果输入的 \(w_i\) 是非自然数，则调用循环的方法将会变得很麻烦），而递归则不用。
\[ F(i, j) = \left \{ \begin{array}{ll} 0 &, i=0 \\F(i-1,j) &, 0 \leq j < w_i \\ \max \{ F(i-1,j), F(i-1,j-w_i)+v_i \} &, j \geq w_i \end{array} \right . \]
循环
def bottom_up(n, W, w, v, f, s): for i in range(n): for j in range(1, W + 1): if j < w[i]: f[i][j] = f[i - 1][j] else: q = f[i - 1][j - w[i]] + v[i] if q > f[i - 1][j]: f[i][j] = q s[i][j] = w[i] return f[n - 1][W]递归
def memoized(i, j, w, v, f, s): if i == 0: return 0 if f[i][j] > 0: return f[i][j] if j < w[i]: f[i][j] = memoized(i - 1, j, w, v, f, s) else: q1 = memoized(i - 1, j - w[i], w, v, f, s) + v[i] q2 = memoized(i - 1, j, w, v, f, s) if q1 > q2: f[i][j] = q1 s[i][j] = 1 else: f[i][j] = q2 return f[i][j]程序验证
输入如下测试数据：
W = 10 w = [2, 3, 5, 7] v = [1, 5, 2, 4] n = len(w) f = [[0] * (W + 1) for _ in range(n)] s = [[0] * (W + 1) for _ in range(n)] bottom_up(n, W, w, v, f, s)得到如下中间缓存矩阵（特别地，循环和递归得到的中间矩阵是不一样的，因为循环是遍历所有的数值，其中包括利用w数组组合出来的数值，而递归只遍历可以利用w数组组合出来的数值。下面采用的循环的方法。）
f = [[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 1, 5, 5, 6, 6, 6, 6, 6, 6], [0, 0, 1, 5, 5, 6, 6, 6, 7, 7, 8], [0, 0, 1, 5, 5, 6, 6, 6, 7, 7, 9]] s = [[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]求最优解
例如，求解
n=4,W=10的最大价值：s[3][10]=1表示把w[3]=7装进背包，此时背包剩余W=3；s[2][3]=0，表示把w[2]=5丢弃，此时背包剩余W=3；s[1][3]=1，表示把w[2]=3装进背包，此时背包剩余W=0，求解结束。最接结果为把重量为3和7的物品放进背包，最大价值为f[3][10]=9
4.2.2.2. 区间划分问题-最小矩阵乘法次数
问题描述
对于 \(n\) 个矩阵序列 \(\langle A_1, A_2, \cdots , A_n \rangle\) 之间的矩阵乘法，怎样的计算顺序可使其总的计算次数最小化。
求解状态方程
求子问题。这个题目怎么找子问题是一个难点，跟上面的子问题不太一样，其子问题是 \(l\) 个矩阵进行运算。设矩阵 \(A_i(1 \leq i \leq n)\) 的大小为 \(p_{i-1} \times p_i\)，\(A_iA_{i+1}...A_j(i<j)\) 的最小计算次数为 \(F(i,j)\)。所以，其子问题为，在区间 \([i,j]\) 中找到一个点 \(k\) ，使得矩阵 \(B_0=A_i...A_k\) 、矩阵 \(B_1=A_{k+1}...A_j\) 及 \(B_0B_1\) 的总计算次数最小，其中，\(B_0B_1\) 的计算次数为 \(p_{i-1}p_kp_j\)，
求初始状态。初始条件为只有一个矩阵进行运算，即 \(i=j\)
故转移方程如下 \[ F(i,j) = \left \{ \begin{array}{ll} 0 &, i=j \\ \min \{ F(i,k) + F(k+1,j) + p_{i-1}p_{k}p_{j}| i \leq k < j \} &, 1 \leq i<j \leq n \end{array} \right . \]
循环
def bottom_up(n, p, f, s): for l in range(2, n + 1): # 有l个矩阵相乘，这里忽略了l=1即i=j的情况，因为f初始为0，就不需要再另外定义初始值了。 for i in range(1, n - l + 2): j = i + l - 1 f[i][j] = float('inf') for k in range(i, j): # 转移方程表达式 q = f[i][k] + f[k + 1][j] + p[i - 1] * p[k] * p[j] if q < f[i][j]: f[i][j] = q s[i][j] = k return f[1][n]二维模型的循环方法有一个难点，在于确定循环的边界，而下面递归的方法就没有这一烦恼。
递归
def memoized(i, j, p, f, s): if f[i][j] > 0: return f[i][j] if i == j: return 0 else: f[i][j] = float('inf') for k in range(i, j): q = memoized(i, k, p, f, s) + memoized(k + 1, j, p, f, s) + p[i - 1] * p[k] * p[j] if q < f[i][j]: f[i][j] = q s[i][j] = k return f[i][j]程序验证
输入如下测试数据：
p = [30, 35, 15, 5, 10, 20, 25] # 例如，A1的大小为30*35，A2的大小为35*15，依次类推 n = len(p) - 1 # 这里其实可以使用 n*n 的数组，但为了跟方程的下标对应上，这里往外扩了一维 f = [[0] * (n + 1) for _ in range((n + 1))] s = [[0] * (n + 1) for _ in range((n + 1))] bottom_up(n, p, f, s) memoized(1, n, p, f, s)得到如下中间缓存矩阵
f = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 15750, 7875, 9375, 11875, 15125], [0, 0, 0, 2625, 4375, 7125, 10500], [0, 0, 0, 0, 750, 2500, 5375], [0, 0, 0, 0, 0, 1000, 3500], [0, 0, 0, 0, 0, 0, 5000], [0, 0, 0, 0, 0, 0, 0]] s = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 3, 3, 3], [0, 0, 0, 2, 3, 3, 3], [0, 0, 0, 0, 3, 3, 3], [0, 0, 0, 0, 0, 4, 5], [0, 0, 0, 0, 0, 0, 5], [0, 0, 0, 0, 0, 0, 0]]求最优解
例如，求解 \(A_1...A_6\) 的最小计算次数：
当
i=1,j=6时，s[1][6]=3，表示在 \(A_3\) 处分成左右两部分，左边部分i=1,j=3，即s[1][3]=1，右边部分i=4,j=6，即s[4][6]=5，依次类推，即可得最小计算次数时的表达式为 \(A_1(A_2A_3)(A_4A_5A_6)\)，最小次数为15125次
Good night!
