动态规划是运筹学中一种经典的求解方法，其基本原则是最优原则
最优原则
不论第一次选择的状态是什么，接下来的选择一定是最优选择
只要最优原则是适用的，那么就可以用动态规划方法去求解这个规划问题。下面用最经典的0-1 背包问题来解释何为最优原则
0-1 背包问题
有 n n n 个物品和一个容量为 c c c 的背包， n n n 个物品的重量储存在向量 w w w 中， n n n 个物品的的价值储存在向量 v v v 中，应当装入哪些物品，使得总重量不超过背包的容量
对于 0-1 背包问题，我们可以从第一件物品开始，到最后一件物品，决定装入还是不装入。
如果装入第一件物品：前提是 w 1 ≤ c w_1\leq c w1≤c，那么背包容量剩下 c − w 1 c-w_1 c−w1，问题转化成剩下的 n − 1 n-1 n−1 件物品装入容量为 c − w 1 c-w_1 c−w1 的背包中，怎么使得价值最大化，设这个最大价值为 V 1 V_1 V1，此时能获得最大价值为 v 1 + V 1 v_1+V_1 v1+V1
如果不装入第一件物品：剩下的 n − 1 n-1 n−1 件物品装入容量为 c c c 的背包中，怎么使得价值最大化，设这个最大价值为 V 2 V_2 V2
动态规划递归方程： 最大价值= max ( v 1 + V 1 , V 2 ) \max(v_1+V_1,V_2) max(v1+V1,V2)
假设 d p ( c , b e g i n ) dp(c,begin) dp(c,begin) 是将将第 begin 件物品到最后一件物品装入容量为 c c c 的背包可以获得的最大价值，于是，动态规划递归方程可以表示为 d p ( c , i ) = { m a x ( d p ( c − w i , i + 1 ) + v i , d p ( c , i + 1 ) ) c > w i d p ( c , i + 1 ) c < = w i 1 ≤ i ≤ n − 1 d p ( c , n ) = { 0 c < v n v n c ≥ v n \begin{aligned} &dp(c,i)=\begin{cases} max( dp(c-w_{i},i+1)+v_{i},dp(c,i+1) )&c>w_{i}\\\\ dp(c,i+1)&c<=w_i \end{cases}\\\\ &1\leq i\leq n-1\\\\ &dp(c,n)=\begin{cases} 0&c<v_n\\\\ v_n&c\geq v_n \end{cases} \end{aligned} dp(c,i)=⎩⎪⎨⎪⎧max(dp(c−wi,i+1)+vi,dp(c,i+1))dp(c,i+1)c>wic<=wi1≤i≤n−1dp(c,n)=⎩⎪⎨⎪⎧0vnc<vnc≥vn
这样，就可以用递归的方法去求解这个优化问题，因此，用动态规划问题求解的一般解题步骤可以概括为
- 定义状态，证实最优原则是适用的
- 确定动态规划递归方程
- 求解动态规划递归方程以获得最优解
- 沿着最优解生成过程进行回溯
如上面的0-1背包问题写成C++代码是很容易的。
int dp(vector<int>& weight,vector<int>& value,int c,int i){
int n=weight.size();
if(i==n-1) return (weight[n-1]<=c)?value[n-1]:0;
else{
return max(
(weight[i]<c)?(weight[i]+dp(weight,value,c-weight[i],i+1)):0,
dp(weight,value,c,i+1));
}
}
int max_value(vector<int>& weight,vector<int>& value,int c){
int n=weight.size();
if(n==1) return (weight[0]<=c)?value[0]:0;
else return dp(weight,value,c,0);
}
但是，动态规划的问题是可能存在大量的重复计算，递归的过程中有一些动态规划递归方程是已经计算过的，但是还要重新走一遍递归，时间复杂度是非常大，因此，虽然直接用递归的方式代码很简单，这种方法看起来很诱人。但是是用大量重复计算换来的，所以如何避免重复计算是非常重要的。
一般的解决方法是：模拟整个递归过程，将后面已经计算得到的，可能被重复利用的值储存起来，从而避免重复计算，减小时间复杂度。
暴力递归的时间复杂度
0-1背包问题采用暴力递归方法的最坏时间复杂度可以用一下差分方程来计算 t ( n ) = 2 t ( n − 1 ) + 1 t(n)=2t(n-1)+1 t(n)=2t(n−1)+1
其中 d d d是一个常数，该差分方程的通解为 t ( n ) = c . 2 n − d t(n)=c.2^n-d t(n)=c.2n−d， c c c是一个常数暴力递归的时间复杂度是 O ( 2 n ) O(2^n) O(2n)，这显然是不可接受的， n n n非常大时计算量非常大，实际上， O ( 2 n ) O(2^n) O(2n)的复杂度并没有比暴力穷举的方法快多少， n n n件物品所有可能的组合的数量就是 2 n 2^n 2n
0-1背包问题的进一步讨论：
实际上，对于固定的 w , v , i w,v,i w,v,i， f i ( c ) = d p ( w , v , c , i ) f_i(c)=dp(w,v,c,i) fi(c)=dp(w,v,c,i)关于 c c c是一个单调递增的阶梯函数，设 n = w . s i z e ( ) n=w.size() n=w.size()
如果 n = = i n==i n==i，那么 f n ( c ) = { v 1 c ≥ w n 0 c < w n f_n(c)=\begin{cases} v_1&c\geq w_n\\\\ 0&c<w_n \end{cases} fn(c)=⎩⎪⎨⎪⎧v10c≥wnc<wn
我们再来看 f n − 1 ( c ) f_{n-1}(c) fn−1(c)，由动态规划递归方程： f n − 1 ( c ) = { max ( v n − 1 + f n ( c − w n − 1 ) , f n − 1 ( c ) ) c ≥ w n − 1 f n − 1 ( c ) c < w n − 1 f_{n-1}(c)=\begin{cases} \max(v_{n-1}+f_n(c-w_{n-1}),f_{n-1}(c))&c\geq w_{n-1}\\\\ f_{n-1}(c)&c<w_{n-1} \end{cases} fn−1(c)=⎩⎪⎨⎪⎧max(vn−1+fn(c−wn−1),fn−1(c))fn−1(c)c≥wn−1c<wn−1
通过这个我们很容易得到 f n − 1 f_{n-1} fn−1的具体表达式：
如果 w n − 1 ≤ w n w_{n-1}\leq w_n wn−1≤wn，就有 f n − 1 ( c ) = { 0 c < w n − 1 v n − 1 w n − 1 ≤ c < w n max ( v n − 1 , v n ) w n ≤ c < w n + w n − 1 v n − 1 + v n c ≥ w n + w n − 1 f_{n-1}(c)=\begin{cases} 0&c<w_{n-1}\\\\ v_{n-1}&w_{n-1}\leq c<w_{n}\\\\ \max(v_{n-1},v_n)&w_n\leq c < w_n+w_{n-1}\\\\ v_{n-1}+v_n&c\geq w_n+w_{n-1} \end{cases} fn−1(c)=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧0vn−1max(vn−1,vn)vn−1+vnc<wn−1wn−1≤c<wnwn≤c<wn+wn−1c≥wn+wn−1
可见， f n − 1 f_{n-1} fn−1是一个右连续，单调递增的阶梯函数。为了求解 f n − 1 ( c ) f_{n-1}(c) fn−1(c)，我们可以对 w w w按升序的方式进行排序， v v v也进行相应的排序，付出的时间复杂度是 O ( n log n ) O(n\log n) O(nlogn)，于是，我们总假定 w 1 ≤ w 2 ≤ ⋯ ≤ w n w_1\leq w_2\leq\cdots \leq w_n w1≤w2≤⋯≤wn。如上面的 f n − 1 f_{n-1} fn−1，我们可以用下表来表示 f n − 1 ( c ) f_{n-1}(c) fn−1(c)
| 临界值 | w n − 1 w_{n-1} wn−1 | w n w_n wn | w n + w n − 1 w_{n}+w_{n-1} wn+wn−1 |
|---|---|---|---|
| dp | v n − 1 v_{n-1} vn−1 | max ( v n , v n − 1 ) \max(v_{n},v_{n-1}) max(vn,vn−1) | v n + v n − 1 v_n+v_{n-1} vn+vn−1 |
(接上)对于更一般的 f i ( c ) f_i(c) fi(c)，我们也如此表示
| 临界值 | c 1 c_1 c1 | c 2 c_2 c2 | ⋯ \cdots ⋯ | c m c_m cm |
|---|---|---|---|---|
| dp | V 1 V_1 V1 | V 2 V_2 V2 | ⋯ \cdots ⋯ | V m V_m Vm |
取值的规则是：小于 c 1 c_1 c1的值取0，大于或等于 c m c_m cm的值取 V m V_m Vm，如果 c c c介于（大于等于） c i c_i ci和（小于） c i + 1 c_{i+1} ci+1之间，取 V i V_i Vi。
按照动态规划递归方程：
f i ( c ) = { max ( v i + f i + 1 ( c − w i ) , f i + 1 ( c ) ) c ≥ w i f i + 1 ( c ) c < w i f_{i}(c)=\begin{cases} \max(v_{i}+f_{i+1}(c-w_{i}),f_{i+1}(c))&c\geq w_{i}\\\\ f_{i+1}(c)&c<w_{i} \end{cases} fi(c)=⎩⎪⎨⎪⎧max(vi+fi+1(c−wi),fi+1(c))fi+1(c)c≥wic<wi
由于 w w w是单调上升的，用归纳法不难证明 c 1 = w i + 1 c_1=w_{i+1} c1=wi+1， w i ≤ w i + 1 w_i\leq w_{i+1} wi≤wi+1，当 c < w i c < w_i c<wi时， f i ( c ) = f i + 1 ( c ) = 0 f_i(c)=f_{i+1}(c)=0 fi(c)=fi+1(c)=0，当 c ≥ w i c\geq w_i c≥wi时 f i ( c ) = max ( v i + f i + 1 ( c − w i ) , f i + 1 ( c ) ) f_i(c)=\max(v_i+f_{i+1}(c-w_i),f_{i+1}(c)) fi(c)=max(vi+fi+1(c−wi),fi+1(c))
根据这个动态规划递归方程，就可以写出 f i f_{i} fi的表格，临界值是 { c 1 + w i , c 2 + w i , ⋯ , c m + w i , c 1 , c 2 , ⋯ , c n , w i } \{c_1+w_i,c_2+w_i,\cdots,c_m+w_i,c_1,c_2,\cdots,c_n,w_i\} {c1+wi,c2+wi,⋯,cm+wi,c1,c2,⋯,cn,wi}从小到大排列，可见 f 1 f_1 f1的临界值数量是 O ( 2 n ) O(2^n) O(2n)
重量为整数的0-1背包问题:
从上面的讨论可以看出，重量为整数时，复杂度可以进一步下降，因为 f i ( c ) f_i(c) fi(c)的临界点只能取整数，且不超过容量初始容量 c 0 c_0 c0的临界点才是有意义的，因此，我们可以储存一个二维数组 d p [ i ] [ j ] = f i − 1 ( j + 1 ) dp[i][j]=f_{i-1}(j+1) dp[i][j]=fi−1(j+1)，其中， 0 ≤ i ≤ n − 1 0\leq i\leq n-1 0≤i≤n−1， 0 ≤ j ≤ c − 1 0\leq j\leq c-1 0≤j≤c−1，这种情况下，我们只要按 i = n − 1 , n − 2 , ⋯ , 0 i=n-1,n-2,\cdots,0 i=n−1,n−2,⋯,0的顺序进行计算，就避免重复计算，时间复杂度和空间复杂度均为 O ( c n ) O(cn) O(cn)，如果 c ≪ 2 n c\ll 2^n c≪2n，那时间复杂度将远远小于 O ( 2 n ) O(2^n) O(2n)，将比暴力递归方法快很多。
C++代码如下：
int max_value(vector<int>& weight,vector<int>& value,int c){
int n=weight.size();
if(n==1) return (weight[0]<=c)?value[0]:0;
else{
vector<vector<int>> dp(n-1,vector<int>(c,0));
//初始化
for(int i=c-1;i>=0;i--){
dp[n-2][i]=(weight[n-1]<=i+1)?value[n-1]:0;
}
for(int i=n-3;i>=0;i--){
for(int j=c-1;j>=0;j--){
if(weight[i]>j+1) dp[i][j]=dp[i+1][j];
else if(weight[i]==j+1){
dp[i][j]=max(dp[i+1][j],value[i]);
}else{
dp[i][j]=max(value[i]+dp[i+1][c-weight[i]-1],dp[i+1][j]);
}
}
}
if(weight[0]>c) return dp[0][c-1];
else if(weight[0]==c) return max(dp[0][c-1],value[0]);
else{
return max(value[0]+dp[0][c-weight[0]-1],dp[0][c-1]);
}
}
}
所以，通常我们需要分析整个迭代过程，将后面的迭代过程计算结果储存起来，以降低动态规划的时间复杂度，而这些值通常以数组的形式储存起来，就能以远远小于暴力解法的时间复杂度来求解一个算法问题。本节先以0-1背包问题来引入动态规划方法的基本概念，后面我们将以leetcode上具体的题目作为例子，以刷题笔记的形式，讲解动态规划。