关键词：
万物皆可DP
前言
如果说搜索算法占据了机试算法题的半壁江山，那么动态规划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];
// 定义dp数组+初始化
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)
// dp[i]表示总金额为i时组合个数
vector<int> dp(amount + 1);
dp[0] = 1;
// 遍历每一种硬币
for(auto& coin : coins)
// 遍历从1——amount的所有情况
for(int i = 1; i <= amount; i ++)
if(i >= coin)
dp[i] = dp[i] + dp[i - coin];
return dp[amount];
;
/*作者：heroding
链接：https://leetcode-cn.com/problems/coin-change-2/solution/cdong-tai-gui-hua-by-heroding-gg0q/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
可以看到代码中已经是优化后的结果，下面再来一道经典的完全平方数问题，这里不是求最大值，而是求最小的组合，代码如下：
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]; // dp数组
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) // 按2的幂取 1,2,4....
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];
;
/*作者：heroding
链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/cdong-tai-gui-hua-by-heroding-nbxv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
这道题就是常说的，看着简单实现困难的那类问题，代码不长，不到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)
// 动态规划思想，i到j是否为回文串取决于i与j是否相等或者s[i]、s[j]相等，[i + 1]到[j - 1]范围内满足回文
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 ++)
// 如果j + 1 到 i 是回文串
if(judge[j + 1][i])
times[i] = min(times[i], times[j] + 1);
return times[len - 1];动态规划类型总结
...)2.背包问题(uva12563,金明的预算方案）3.区间DP（zxh,488--502,算法导论相应题目）4.坐标DP（noip2007,noip2008，滑雪）5.子矩阵问题（zxh562--569,挑战 查看详情
leetcode552学生出勤记录ii[动态规划]heroding的leetcode之路(代码片段)
解题思路：一道不同寻常的动态规划类型题目，主要是题目的场景设定非常有意思，构建的dp数组dp[i][j][k]表示，遍历到i位置时，A的数量为j，连续L数量为k时的出勤奖励次数，那我们得分三种情况讨论... 查看详情
算法题套路总结（三）——动态规划
参考技术A前两篇我总结了链表和二分查找题目的一些套路，这篇文章来讲讲动态规划。动态规划从我高中开始参加NOIP起就一直是令我比较害怕的题型，除了能一眼看出来转移方程的题目，大部分动态规划都不太会做。加上后来A... 查看详情
leetcode516最长回文子序列[动态规划]heroding的leetcode之路(代码片段)
解题思路：非常经典的一道字符串动态规划题目，首先是dp数组的定义，dp[i][j]代表着从i到j最长回文子序列长度，对于dp[i][i]，每个字符自身就是回文串，长度为1，遍历得从子字符串往整个字符串的方... 查看详情
leetcode799香槟塔[模拟+动态规划]heroding的leetcode之路(代码片段)
解题思路：很好理解的模拟动态规划题，对于每个i层j位置的玻璃杯，如果超出了1，它会平均流给i+1层j位置和j+1位置的玻璃杯，这样自上而下把香槟流下去即可，代码如下：classSolutionpublic:doublech... 查看详情
leetcode813最大平均值和的分组[动态规划前缀和]heroding的leetcode之路(代码片段)
解题思路：一道非常有有参考价值的动态规划题型，是前缀和和动态规划的结合，首先计算前缀和，便于求解dp时计算区间的和，对于dp数组，dp[i][j]表示对于长度为i的序列，将其分为j组所得到的最大... 查看详情
leetcode375猜数字大小ii[动态规划]heroding的leetcode之路(代码片段)
...所拥有的钱能够满足猜中任何一个数的代价，那么用动态规划可以很好解决。状态转移方程为cost=min(cost,k+max(dp[i][k-1],dp[k+1][j]));通过i和j固定范围，k在范围内找最小 查看详情
leetcode787k站中转内最便宜的航班[动态规划]heroding的leetcode之路(代码片段)
...可能会有时间复杂度爆炸的用例，所以还是决定使用动态规划，定义dp数组dp[dst][k]，表示到达dst经过k次中转所花费的最少金额，当dp[from][k-1]不为INT_M 查看详情
leetcode467环绕字符串中唯一的子字符串[动态规划]heroding的leetcode之路(代码片段)
解题思路：非常简单的一道dp题目，就是不断找在p中连续的字符个数，更新dp中对应元素所在的最长连续位置，返回和即可，代码如下：classSolutionpublic:intfindSubstringInWraproundString(stringp)vector<int>dp(26,0);int... 查看详情
数据结构与算法acwing算法自学笔记总结
...、最长公共子序列、最短编辑距离题解与模板【动态规划算法】零基础区间DP自学笔记图论【图论】最短路算法：Dijkstra、bellman-ford、spfa、Floyd和拓扑排序【图论算法】零基础最小生成树学习与总结【图论算法】二分图：... 查看详情
leetcode801使序列递增的最小交换次数[动态规划]heroding的leetcode之路(代码片段)
解题思路：一道稍微复杂一点的动态规划题型，其实本质上就是二维动态数组，每个位置对应两种状态，交换或者不交换，每个位置也就有两种判断条件，一种是对应位置都满足严格递增，一种是交换... 查看详情
leetcode801使序列递增的最小交换次数[动态规划]heroding的leetcode之路(代码片段)
解题思路：一道稍微复杂一点的动态规划题型，其实本质上就是二维动态数组，每个位置对应两种状态，交换或者不交换，每个位置也就有两种判断条件，一种是对应位置都满足严格递增，一种是交换... 查看详情
动态规划学习笔记(代码片段)
1.动态规划步骤2.一维dp数组做题记录入门/简单题爬楼梯使用最小花费爬楼梯最大子序和中等题打家劫舍打家劫舍II删除并获得点数1.动态规划步骤（1）确定dp数组以及下标的含义（2）确定递推公式（3）dp数... 查看详情
动态规划学习笔记(代码片段)
1.动态规划步骤2.一维dp数组做题记录入门/简单题爬楼梯使用最小花费爬楼梯最大子序和中等题打家劫舍打家劫舍II删除并获得点数3.二维dp数组做题记录中等题不同路径1.动态规划步骤（1）确定dp数组以及下标的含义（... 查看详情
常见动态规划算法问题策略分析
本文总结了几种常见动态规划算法的分析策略，但不做案例的具体分析，阅读前最好对这几种算法有一定基础了解。动态规划策略1.动态规划介绍动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转... 查看详情
学习笔记：动态规划
最近写了一些动态规划……简单总结一下 区间DP做了好多道感觉都非常套路……就感觉都和合并石子长一个样。无非就是区间从短到长依次更新，然后还有一些奇奇怪怪的转移方法（这个就因题而异了）。区... 查看详情
dp动态规划-打acm你必须知道的算法(代码片段)
动态规划1.什么是动态规划？动态规划（DynamicProgramming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。解决DP问题，要明确转移和状态两个问题。这么说大家可能也不知道啥是动态规划，那... 查看详情
由leetcode详解算法之动态规划（dp）(代码片段)
...，发现许多题目的解题思路相似，从中其实可以了解某类算法的一些应用场景。这个随笔系列就是我尝试的分析总结，希望也能给大家一些启发。动态规划的基本概念一言以蔽之，动态规划就是将大问题分成小问题，以迭代的方... 查看详情