前言
如果说搜索算法占据了机试算法题的半壁江山，那么动态规划DP就占据了机试算法题的八分江山，可能有些夸张，但是在做题的时候明显可以感觉得到，万物皆可DP不是天方夜谭，什么组合的个数，最长匹配长度，最少的个数，凡是跟最优解有关的（无论最多还是最少）都可以用的上DP，所以之前的DFS、BFS中的最优解问题，亦可以用DP去解决，而且对于组合数的回溯问题，在n超过一定长度的情况下，只能用DP去解决。
动态规划是求解决策过程最优化的过程，是一种空间换时间的方法（这也就是它能够解决O(2^n)问题的核心，从而放弃DFS的使用），本质其实类似分治思想，把待求解的问题分解成多个子问题，不同子问题之间是相互关联的，前面计算过的子问题可以提供给后面子问题使用。
那DP这么强大，为什么常常让coder望而却步呢？因为它实在是太灵活了，且因题而异，DP的核心——状态转移方程，是只有根据题目的意思才能够构建出来。要说有无模板，也是有的，但是都是依据做题经验总结出来的，如果不能剖析问题的本质，往往就无法构建出来状态转移方程，所以在这里我根据自己的经验通过举例子列举几种DP常见类型，希望能给自己和读者在阅读时有所思考和启发，那么就开始叭~
1. 动态规划解题思路
1.1 解题思路
首先抛砖引玉，祭出可能是最简单的动态规划问题，斐波那契数列问题，该问题经常用递归的方式解决（会有很多重复计算，递归只是因为简单），递归的代码如下：
class Solution {
public:
int fib(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return fib(n - 1) + fib(n - 2);
}
};
但是出现的明显问题是重复运算，从最后一行的fib(n-1) + fib(n-2)可以看出，fib(n-1)里面的最后一行是fib(n-2)+fib(n-3)，显然fib(n-2)又重复算了一次，这样的情况还有很多，就不一一列举了，这就是递归的弊端。但是动态规划可以很好地解决该问题，动态规划的代码如下：
class Solution {
public:
int fib(int n) {
if(n == 0 || n == 1) {
return n;
}
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
int a = 0, b = 1;
for(int i = 2; i <= n; i ++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
只是开辟了一个一维数组，就不需要重复进行大量计算了（计算结果保存在数组中，直接调用），此外，再仔细观察发现，每次遍历只用了dp[i - 1]和 dp[i - 2]，也就是说可以用两个变量存储dp[i - 1]和 dp[i - 2]，每一轮遍历更新一下即可，代码如下：
class Solution {
public:
int fib(int n) {
if(n == 0 || n == 1) {
return n;
}
int a = 0, b = 1;
for(int i = 2; i <= n; i ++) {
int temp = b;
b = a + b;
a = temp;
}
return b;
}
};
这样又进一步节省了空间复杂度！这就是滚动数组的方法，在降低空间复杂度上是一个不错的选择。
接下来介绍一般的动态规划解题思路：
- 找到合适的数据结构存储中间值，比如斐波那契数列中的定义的dp[n]或者a和b；
- 找到状态转移方程，这一般根据题目的要求设计；
- 初始化方法，根据题目所给的条件对定义的dp数组初始化，一般都是在边界位置进行；
- 运算顺序，这里举一个例子，假设
dp[i][j]记录从i到j是否回文，实际上我们只用到了上三角的部分，有状态转换方程：dp[i][j]=dp[i+1][j-1] && str[i]==str[j]，对于i来说，i是根据i+1得来的，所以i是从后往前遍历，对j来说，j是根据j -1来的，所以j从前往后遍历。
1.2 问题特点
动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。
能采用动态规划解决的问题，一般要具有三个性质：
- 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
- 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
理解上述内容后，就开始我们真题的演练吧！
2. 背包问题
背包问题是最经典的动态规划问题，至少有一半的DP题都可以借鉴背包问题的思想，变成背包问题的变种形式。背包问题不是某一个题目，而是一系列题目，包括01背包问题，完全背包问题，多重背包问题等，这是个循序渐进的过程，认真阅读一定会有所收获的，包括日后回首的自己。
2.1 01背包问题
这里选取的是蓝桥杯练习题上的01背包问题，给定N个物品，每个物品有一个重量W和一个价值V，你有一个能装M重量的背包，问怎么装使得所装价值最大，每个物品只有一个。
如果你看过我上一篇对DFS的总结，你一定会眼前一亮，这不就是heroding所说的一维数据结构的DFS吗，遍历所有满足题意的组合，找到最大的结果不就行了。确实，背包问题完全适合DFS的解法，至少从理论上是可以的，实际上如果n过大，肯定会内存爆炸，直接超时。。。这就是为什么我说，解决这类题型，动态规划比DFS好，所以仔细看完这篇解读，你又有了一个解题利器！
01背包问题，物品只有一个（不重复），即对每一个物品只有选择和不选两种选择，分析题目所给要素：
- N件商品；
- 总容量M；
- 质量数组weight；
- 价值数组value；
我们按照1.1给的解题思路去面对这道题目，步骤如下：
- 找到合适的数据结构存储
分析题目，有选择的物品，以及有限的重量，那么首先定义的数据结构是二维int型数组dp[i][j]，i，j分别代表遍历到第i个物品时背包中的重量为j； - 找到状态转移方程
这里是整个dp最关键的部分，对于每一个物品，有选择和不选择两种状态，如果不选择，那么背包中的价值不变，跳到下一个物品，即dp[i][j] = dp[i - 1][j];如果选择的话，就需要更新一下背包中的重量，以及价值，dp[i][j] = dp[i - 1][j - weight[i]] + value[i]; - 初始化
初始化根据自定义的dp数组和状态转移方程去理解，背包为0时，不管遍历到哪个都是0（放不进去），所以dp[i][0] = 0;如果一个都不遍历，那么不管背包容量多大都没有东西，即dp[0][j] = 0; - 运算顺序
在本题中，i和j都是通过之前的状态得到的，所以都应该从小到大遍历。
好了，那么让我们上手一道一模一样的题目来练习一下吧，这是一道北大的复试机试题目，本质上就是01背包问题，代码如下：
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main() {
int C, N;
while(scanf("%d%d", &C, &N) != EOF) {
vector<int> prices(N + 1);
vector<int> values(N + 1);
for(int i = 1; i <= N; i ++) {
cin >> prices[i] >> values[i];
}
vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0));
for(int i = 1; i <= N; i ++) {
for(int j = 0; j <= C; j ++) {
if(j >= prices[i]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - prices[i]] + values[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[N][C] << endl;
}
return 0;
}
观察一下代码可以发现，仍然有可以优化的地方，就是在状态转移方程那里，dp[i]只与dp[i - 1]有关系，所以可以将二维dp数组化简为一维，如下所示：
vector<int> dp(C + 1, 0);
for(int i = 1; i <= N; i ++) {
for(int j = C; j >= prices[i]; j --) {
dp[j] = max(dp[j], dp[j - prices[i]] + values[i]);
}
}
那么这里要注意几点，一个对于j要从后往前进行，因为正向进行的话会把i-1的值修改了，换言之，就是每次更新dp[j]必须是用i - 1的dp[]更新的，只有倒着进行才不会出现上述情况，如果还不理解这里举个简单的例子，比如dp[1]刚刚进行更新，结果更新dp[2]的时候需要使用dp[1]，但是此时的dp[1]不是i - 1时候的dp[1]了，结果就导致结果完全错误。还有个需要注意的是在二维数组中，如果j < prices[i]需要进行dp[i][j] = dp[i - 1][j];但是在一维dp数组中不需要，因为dp[j] = dp[j]没有什么意义。
这里留下两道练习题，一个是北大机试题目采药问题，另一个是清华大学复试上机题最小邮票数，都是不错的01背包问题的练习题目，其中最小邮票数取的是min，所以在初始化要以一个尽可能大的值初始化。
2.2 完全背包问题
这是有关01背包问题的拓展，此时每件物品不只可以取一个，而是可以选择多件，在这样的条件下使得背包中物品价值总和最大。
同样，设置二维数组dp[][]，令dp[i][j]表示前i个物品装进容量为j的背包能够获得的最大价值，通过设置这么一个二维数据，数组dp[n][m]的值就是完全背包问题的解。
和01背包一样，只考虑第i件物品时，可将情况分为是否放入dii件物品两种：
- 对于容量为j的背包，如果不放入第i件物品，那么这个额问题和01背包问题一样，即
dp[i][j] = dp[i - 1][j]。 - 对于容量为j的背包，如果放入第i件物品，那么放入之前背包的容量就变成j - weight[i]，并得到这个物品的价值value[i]，由于第i个物品是可以无限获取的，所以状态转移方程变成：
dp[i][j] = dp[i][j - weight[i]] + value[i];
所以最后的状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
此外由于dp[i][j]只和dp[i - 1]，dp[i][j]有关，可以进一步优化，状态转移方程为：
? ??????????????????????dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
关键在于遍历的顺序，i还是正向遍历，但是j和01背包不同，这里需要让dp[j - weight[i]]已经完成了本次的更新修改。这就需要在每次更新中，正序遍历所有的j的值，因为只有这样才能保证完成正确的状态转移。
好了，那就开始题目的练习与讲解吧，这里我首先挑选了一道最基础的完全背包问题，LeetCode 418 零钱兑换II，这里给出的就是给定的硬币个数有无限个，代码如下：
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for(auto& coin : coins) {
for(int i = 1; i <= amount; i ++) {
if(i >= coin) {
dp[i] = dp[i] + dp[i - coin];
}
}
}
return dp[amount];
}
};
可以看到代码中已经是优化后的结果，下面再来一道经典的完全平方数问题，这里不是求最大值，而是求最小的组合，代码如下：
class Solution {
public:
int numSquares(int n) {
int INF = 1e8;
vector<int> dp(n + 1, INF);
dp[0] = 0;
for(int i = 1; i * i <= n; i ++) {
for(int j = i * i; j <= n; j ++) {
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};
可以看到和01背包问题的求最小值方法一样的，首先都要先初始化为一个足够大的值，然后再套用模板进行。
2.3 多重背包问题
多重背包问题算是比较少见的背包问题了，它的本质是01背包和完全背包问题的折中，每种物体至多只能取k件，此时的数据结构多了一个k[i]，专门记录不同物体的个数，多重背包可以转换为01背包问题，只不过还有更加便捷的方法去解决，将原数量为k的物品拆分为若干组，将每组视为一件物品，其价值和重量为该组中所有物品的总和。每组物品的数量为20,21,22……2c-1,k-2c+1，其中c是使得k - 2c + 1 >= 0的最大正数，这相当于二进制的拆分，这样大大降低了背包问题的时间复杂度。
下面是一道来自HDU OJ题，可惜网址现在不给访问，题目是珍惜现在、感恩生活，题目大意是你有资金n元，市场有m种大米，每种大米袋装价格不等，在有限的资金最够构面多少千克粮食。代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
int dp[MAXN];
int v[MAXN];
int w[MAXN];
int k[MAXN];
int value[MAXN];
int weight[MAXN];
int main() {
int caseNumber;
cin >> caseNumber;
while(caseNumber --) {
int n, m;
cin >> n >> m;
int number = 0;
for(int i = 0; i < n; i ++) {
cin >> w[i] >> v[i] >> k[i];
for(int j = 1; j <= k[i]; j <<= 1) {
value[number] = j * v[i];
weight[number] = j * w[i];
number ++;
k[i] -= j;
}
if(k[i] > 0) {
value[number] = k[i] * v[i];
weight[number] = k[i] * w[i];
number;
}
}
for(int i = 0; i <= m; i ++) {
dp[i] = 0;
}
for(int i = 0; i < number; i ++) {
for(int j = m; j >= weight[i]; j --) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[m] << endl;
}
return 0;
}
3. 字符串问题
以上都是与数字有关的动态规划题目，其实很多与字符串相关的题目也可以用到动态规划的方法，比如最长匹配，回文串个数，这里我也是简单举几个例子帮助大家理解。
3.1 最长公共子序列
本题是LeetCode 1143 最长公共子序列，非常经典的一道关于字符串匹配的动态规划题，dp[i][j]表示第一个字符串的1—i序列与第二个字符串的1—j序列最长匹配的长度，代码如下：
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.length(), m = text2.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i < n + 1; i ++) {
for(int j = 1;j < m + 1; j ++) {
if(text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
};
这道题就是常说的，看着简单实现困难的那类问题，代码不长，不到20行，核心代码部分也就四五行，但是真正能想到用这样的思路去解决才是最困难的地方，所以还是希望读者自己手敲一遍，自己感受往往会有意想不到的收获。
3.2 分割回文串II
第二道字符串题目是LeetCode 132 分割回文串II，这道题是双重动态规划的巧用，首先第一次动态规划是为了标记所有的回文串，第二次动态规划是为了统计所有的回文串（尽可能长的字符串），相信经过我的描述，代码已经在各位脑海中浮现了，代码如下：
class Solution {
public:
int minCut(string s) {
int len = s.size();
vector<vector<bool>> judge(len, vector<bool>(len, true));
for (int i = len - 1; i >= 0; --i) {
for (int j = i + 1; j < len; ++j) {
judge[i][j] = (s[i] == s[j]) && judge[i + 1][j - 1];
}
}
vector<int> times(len, INT_MAX);
for(int i = 0; i < len; i ++) {
if(judge[0][i]) {
times[i] = 0;
} else {
for(int j = 0; j < i; j ++) {
if(judge[j + 1][i]) {
times[i] = min(times[i], times[j] + 1);
}
}
}
}
return times[len - 1];
}
};
而且观察代码可以发现，第二次的动态规划，实际就是背包问题中求min的过程，状态转移方程是 times[i] = min(times[i], times[j] + 1)，即0——i分割的次数，如果judge[0][i]为True，说明不用分割，不为True就从0到i找回文的位置，如果j + 1 到 i 是回文串，就进行状态转移，选择不分割和分割的最小值。
4. 股票问题
股票问题是经典的组合动态规划方法，比如股票的sale和buy这两种状态就是相互进行转换的，而且同一时期只能有一个状态，首先看LeetCode 123 买卖股票的最佳时机III，因为最多可以交易两次，所以可以 设定四种状态，分别是buy1，buy2，sell1，sell2，四个数据结构代表的意义如下：
- buy1: 在该天第一次买入股票可获得的最大收益；
- sell1: 在该天第一次卖出股票可获得的最大收益；
- buy2: 在该天第二次买入股票可获得的最大收益；
- sell2: 在该天第二次卖出股票可获得的最大收益；
最后返回的一定是sell2（最后一种状态），那么这四种状态怎么更新呢？buy1肯定挑最便宜买入的那天买入，sell1等于上次卖出和这次卖出的最大值，buy2等于上次买过后的钱和上次卖的钱减去买的股的最大值，sell2是上次卖出和这次卖出的最大值，代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int buy1 = INT_MIN;
int sell1 = 0;
int buy2 = INT_MIN;
int sell2 = 0;
for(int p : prices) {
buy1 = max(buy1, -p);
sell1 = max(sell1, buy1 + p);
buy2 = max(buy2, sell1 - p);
sell2 = max(sell2, buy2 + p);
}
return sell2;
}
};
股票问题第二个就是当买卖为k次的情况，那么四种状态是远远不够了，不然干脆定义成两个数组，思路都是一样的，只不过这次对于每一天，要遍历k次，状态转移方程为buy[i] = max(buy[i], sell[i - 1] - ele);sell[i] = max(sell[i], buy[i] + ele);代码如下：
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<int> sell(k + 1, 0);
vector<int> buy(k + 1, INT_MIN);
for(auto &ele : prices)
{
for(int i = 1; i < k + 1; i ++)
{
buy[i] = max(buy[i], sell[i - 1] - ele);
sell[i] = max(sell[i], buy[i] + ele);
}
}
return sell[k];
}
};
5. 总结
码了一天的动态规划，说到底对我本人来说，也就是背包问题理解的比较透彻了，字符串问题还是没能够总结出一定的方法，希望在日后的完善过程中可以总结出规律，读者如果没有太足够的耐心，只用看背包问题部分即可；或者觉得某一个部分讲解的不够好或者没说明白，请私信或者评论区指出，我会尽快解答和改正，无论如何，今天算是我收获满满的一天，也希望会是在看的各位有所感悟的一次阅读体验！下一篇算法笔记，可能会是并查集（图论题目利器），或者是二分法，这两种方法都是某些常见问题的利器，敬请期待！
|