行业知识
算法：动态规划
文章目录
- 引子：凑零钱
- 一、斐波那契数列模型
- 引例：第 N 个泰波那契数
- 动态规划步骤
- 空间优化
- 例题1 三步问题
- 例题2：使用最小花费爬楼梯★
- 例题3：解码方法 ★
- 二、路径问题
- 例题4：不同路径
- 例题5：下降路径最小和
- 例题6：地下城游戏 ★
- 三、简单多状态 dp 问题
- 例题7：按摩师 ★
- 例题8：打家劫舍 II
- 例题9：删除并获得点数
- 例题10：粉刷房子
- 例题11：买卖股票的最佳时机含冷冻期 ★
- 例题12：买卖股票的最佳时机 III ★
- 例题13：买卖股票的最佳时机 IV
- 四、子数组、子串系列
- 例题14：最大子数组和 ★
- 例题15：环形子数组的最大和
- 例题16：乘积最大子数组
- 例题17：乘积为正数的最长子数组长度
- 例题18：等差数列划分
- 例题19：最长湍流子数组 ★
- 例题20：单词拆分 ★
- 例题21：环绕字符串中唯一的子字符串
- 五、子序列问题
- 例题22：最长递增子序列
- 例题23：摆动序列
- 例题24：最长递增子序列的个数 ★
- 例题25：最长数对链
- 例题26：最长定差子序列 ★
- 例题27：最长的斐波那契子序列的长度 ★
- 例题28：最长等差数列 ★
- 例题29：等差数列划分 II - 子序列
- 六、回文串问题
- 例题30：回文子串 ★
- 例题31：最长回文子串
- 例题32：分割回文串 II
- 例题33：最长回文子序列 ★
- 例题34：让字符串成为回文串的最少插入次数 ★
- 七、两个数组的 dp
- 例题35：最长公共子序列 ★
- 例题36：不相交的线
- 例题37：不同的子序列 ★
- 例题38：通配符匹配 ★
- 例题39：正则表达式匹配 ★
- 例题40：交错字符串 ★
- 例题41：两个字符串的最小ASCII删除和 ★
- 例题42：最长重复子数组 ★
- 八、01 背包问题
- 例题43：【模板】01背包
- 例题44：分割等和子集
- 例题45：目标和 ★
- 例题46：最后一块石头的重量 II ★
- 九、完全背包问题
- 例题47：【模板】完全背包 ★
- 例题48：零钱兑换
- 例题49：零钱兑换 II
- 例题50：完全平方数
- 十、二维费用的背包问题
- 例题51：一和零 ★
- 例题52：盈利计划
- 十一、似包非包
- 例题53：组合总和 Ⅳ
- 十二、卡特兰数
- ���题54：不同的二叉搜索树 ★
引子：凑零钱
这部分全是我的碎碎念：本来是在刷蓝桥杯真题的，结果有一道题不会，看别人的题解说用到了什么“状态压缩DP”，不明白，就去DP是什么意思 —— Dynamic Programming（动态规划），于是就去找资料学动态规划，后来发现一个点赞量超高的知乎帖子，看那位大佬写的那么多那么细，以为自己能学懂，不想最开始的问题就给我整不会了（其实现在看来大佬写的确实很清楚，可能是我太笨了，当时就是看不懂 —— 如果你和我一样笨，这篇博客应该能帮到你），这个问题即：凑零钱
知乎大佬的文章：
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
问：你现在手上有面额为 1 5 11 三种纸币，数量不限，如何用最少的纸币凑出 n 元？
示例：输入 15，输出 3（5+5+5）
显然这道题用所谓的贪心算法做不出来（贪心算法思路：每次取当前能使用的最大面额的纸币尽快凑出结果 – 显然对于人民币那 1 5 10 20 50 100 的面额去凑钱，贪心算法就是最优解，但我们这道题就是这么奇葩）
于是就可以用所谓的动态规划解这道题：
//写法和知乎大佬略有不同，但殊途同归int func(int money) { int n = money; vector dp(n+1);//dp[i]：i 块钱最少需要几张 dp[0] = 0; dp[1] = 1; //dp[i] = max(dp[i-1],dp[i-5],dp[i-11]); for (int i = 2; i if (i看不懂？没关系，我一开始也看不懂，就连这个代码也是我学了一段时间后才写出来的，接下来正式开始动态规划的学习：
一、斐波那契数列模型
引例：第 N 个泰波那契数
第 N 个泰波那契数
显然这道题用递归直接秒了：
class Solution {public: void func(int n1,int n2,int n3,int& res, int num){ if(num == 0) return; res = n1 + n2 + n3; func(n2,n3,res,res,num - 1); } int tribonacci(int n) { if(n == 0) return 0; if(n == 1 || n == 2) return 1; int res = 0; func(0,1,1,res,n - 2); return res; }};但我们不是来学递归怎么写的，我们要想的是：动态规划是什么？如果用动态规划应该怎么办？
动态规划步骤
- 状态表示
- 状态转移方程
- 初始化
- 填表顺序
- 返回值
第一步：状态表示
我们先创建一个dp表（是一个一维或二维数组）并将其填满，其中的某一个值可能就是我们的最终结果。dp表中其中相应位置的值有特殊的含义，我们称这个为状态表示
感性理解：状态表示是什么？ —— dp表里的值代表的含义
状态表示怎么来的（是如何确定的）？
1.题目要求
2.经验（多做题）+题目要求
3.在分析问题的过程中发现重复子问题（听起来挺抽象，但其实不难，比如引子的解法就是用了这个思路，不过老师建议先把重心放在前两种情况）
4.其他方法
在这个题目中我们创建一个一维的dp表，由题目要求得到 它的状态表示 dp[i] 为第 i 个泰波那契数的值
第二步：状态转移方程
即：dp[i] 等于什么？ 这个问题听起来很抽象，但我们结合题目，这个题目很直观的写出了 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]，这个公式就是状态转移方程
重点就在前两步上
后三步在处理一些细节问题
第三步：初始化
保证填表的时候不越界
显然状态转移方程中的 dp[i] 中的i不能是 0、1、2，所以我们先把他们初始化：dp[0] = 0; dp[1] = 1; dp[2] = 1;
第四步：填表顺序
为什么需要确定填表顺序：我们需做到 填写当前状态时，所需要的状态已经计算过了
eg. 根据本题的方程，我们肯定是dp[3]、dp[4]、dp[5]……挨个填，不能跳过dp[3]去填dp[4]
第五步：返回值
本题返回 dp表的最后一个数
class Solution {public: int tribonacci(int n) { //处理一些边界情况，防越界 if(n == 0) return 0; if(n == 1 || n == 2) return 1; //创建dp表 int dp[n+1]; //初始化，防越界 dp[0] = 0; dp[1] = 1; dp[2] = 1; for(int i = 3; i dp[i] = dp[i-1]+dp[i-2]+dp[i-3]; } return dp[n]; }};public: int tribonacci(int n) { //处理一些边界情况，防越界 if(n == 0) return 0; if(n == 1 || n == 2) return 1; //dp表换成滚动“数组” int a = 0, b = 1, c = 1, d = 0; //修改状态转移方程 for(int i = 3; i d = a + b + c; //滚动操作 a = b; b = c; c = d; } //修改返回值 return d; }};p空间优化的结果（空间复杂度）：/ppO(n^2) - O(n)/ppO(n) -> O(1)例题1 三步问题
三步问题
不难，直接上题解：
class Solution {public: int waysToStep(int n) { int MOD = 1e9+7; //处理边界情况 if(n == 1) return 1; if(n == 2) return 2; if(n == 3) return 4; //状态表示 dp表 int dp[10000001]; //状态转移方程：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; //逻辑：第i阶台阶怎么上？i-1阶上1步、i-2阶上两步、i-3阶上三步 //——为什么全是一步到位，不考虑像是i-3阶上1步再上2步这些步骤吗——这个已经在i-2中包含了，你猜怎么上的i-2阶？ //初始化 dp[1] = 1; dp[2] = 2; dp[3] = 4; for(int i = 4;i dp[i] = ((dp[i - 1] + dp[i - 2])%MOD + dp[i - 3])%MOD;//因为数很大，需要在这里取模处理一下 //(dp[i - 1] + dp[i - 2])%MOD 在整体取模前还要这样给这两个数取一次模是因为我这个数组的数据类型是int（默认有符号整形），范围为-20亿到20亿（显然我们不想得到负数），虽然数组里的每个数据的大小都被最后的整体取模限制在了MOD（10亿）的范围以内，但如果这里没有取模操作，但凡是三个10亿相加超了20亿，那我们的结果就错了 //综上所述，如果你不想取这个模，你也可以把数组的数据类型换一下：unsigned int dp[10000001] } //返回 return dp[n]%MOD; }};public: int minCostClimbingStairs(vector //状态表示dp表 int n = cost.size(); vector//时间复杂度O(N) dp[i] = min(dp[i-1] + cost[i-1],dp[i-2]+cost[i-2]); } return dp[n]; }};public: int minCostClimbingStairs(vector const int n = cost.size(); vector dp[i] = cost[i] + min(dp[i+1], dp[i+2]); } return min(dp[0],dp[1]); }};public: int numDecodings(string s) { int n = s.size(); //状态表示 vector=10 && t if (s[i] != '0') dp[i] += dp[i - 1]; int t = (s[i - 1]-'0')*10 + s[i] -'0'; if(t=10 && tpublic: int numDecodings(string s) { int n = s.size(); //状态表示 vector if (s[i - 1] != '0') dp[i] += dp[i - 1]; int t = (s[i - 2]-'0')*10 + s[i - 1] -'0'; if(t=10 && tpublic: int uniquePaths(int m, int n) { //状态表示 vector for(int j = 1; j dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m][n]; }};public: int uniquePathsWithObstacles(vector int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); //状态表示 vector for(int j = 1; j dp[i][j] = dp[i-1][j] + dp[i][j-1]; if(obstacleGrid[i-1][j-1] == 1) dp[i][j] = 0; } } return dp[m][n]; }};public: int minFallingPathSum(vector //状态表示，dp表 int m = matrix.size(); int n = matrix[0].size(); vector for(int j = 1;j状态表示：
f[i]：以 i 位置结尾的所有子数组中，最后呈现 “上升” 状态的最长湍流子数组的长度
g[i]：以 i 位置结尾的所有子数组中，最后呈现 “下降” 状态的最长湍流子数组的长度
状态转移方程：
（做例题23回顾这道题时的疑问）为什么 f[i] 在 a>b 时是1不是0 ？明明是下降状态，跟定义的上升完全没关系啊？
由题意，单单一个数也能是湍流数组，可以认为一个数的时候就是万能的状态
初始化：把所有数据全初始化为 1
初始化技巧3
class Solution {public: int maxTurbulenceSize(vector& arr) { int n = arr.size(); vector f(n,1),g(n,1); int ret = 1; for(int i = 1; i arr[i]) g[i] = f[i-1]+1; ret = max(ret,max(f[i],g[i])); } return ret; }};例题20：单词拆分 ★
单词拆分
状态表示：
dp[i]：以 i 位置结尾的字符串是否能够被拼接成
状态转移方程：
dp[i]：若 以 j-1 位置结尾的字符串能够被拼接成 且 j 到 i 位置的字符串对应字典中的单词 —— dp[i] = 1
初始化：
显然单独给 dp[0] 初始化有些麻烦，所以增加一个虚拟空间
class Solution {public: bool wordBreak(string s, vector& wordDict) { //优化，方便查找 unordered_set hash; for(auto& s : wordDict) hash.insert(s); int n = s.size(); vector dp(n+1); dp[0] = 1; //保证后序填表正确 s = ' ' + s;//使得下标统一 for(int i = 1; i for(int j = i; j =1; j--){ if(dp[j-1] && hash.count(s.substr(j,i-j+1))){ dp[i] = true; break; } } } return dp[n]; }};例题21：环绕字符串中唯一的子字符串
环绕字符串中唯一的子字符串
class Solution {public: int findSubstringInWraproundString(string s) { //dp[i]：以位置 i 结尾的子串中有多少不同非空子串在 base 中出现 int n = s.size(); vector dp(n,1); //状态转移方程： //dp[i]：单看s[i]肯定可以，和前面组合时，判断s[i]是否为s[i-1]的下一个字母 //若是，dp[i] = dp[i-1] + 1 //但这道题还有一个问题：不能重复 //设想：zabc和abc都以c结尾，而zabc显然包含了abc的所有情况 //——相同字符结尾，只需统计dp[i]较大值即可避免重复，我们用一个数组来实现这个想法 int count[26] = {0}; count[s[0]-'a'] = 1; for(int i = 1; i五、子序列问题
例题22：最长递增子序列
最长递增子序列
不难，甚至我都可以自己写出来（思路有一部分（指再套一层循环）来源于例题20）：
class Solution {public: int lengthOfLIS(vector& nums) { int n = nums.size(); if(n == 1) return 1; //dp[i]：以i位置结尾的子序列中的最长递增子序列 vector dp(n,1); int ret = 0; for(int i = 1; i = 0; j--){ if(nums[i] > nums[j]){ dp[i] = max(dp[i],dp[j]+1); } } ret = max(ret,dp[i]); } return ret; }};例题23：摆动序列
摆动序列
例题19 最长湍流子数组 的改版，基本没有区别
class Solution {public: int wiggleMaxLength(vector& nums) { int n = nums.size(); vector f(n,1),g(n,1); int ret = 1; for(int i = 1; i =0 ; j--){ if(nums[j] nums[i]) g[i] = max(g[i],f[j]+1); } ret = max(ret,max(f[i],g[i])); } return ret; }};例题24：最长递增子序列的个数 ★
最长递增子序列的个数
感觉算不上难……但我就是没做出来（
class Solution {public: int findNumberOfLIS(vector& nums) { int n = nums.size(); //状态表示： //len[i]：以i位置结尾的最长递增子序列的长度 //count][i]：以i位置结尾的最长递增子序列的个数 vector len(n,1),count(n,1); int retlen = 1, retcount = 1;//最终返回的最长递增子序列的长度即其个数 for(int i = 1; i =0; j--){//给自己的注释：这第二层循环正着反着都一样 if(nums[i]>nums[j]){ //i位置的数据能够和此前数据形成递增子序列 if(len[i]例题25：最长数对链
最长数对链
class Solution {public: int findLongestChain(vector& pairs) { //对原始数组进行预处理（但这里连仿函数都不需要写是我没想到的） sort(pairs.begin(),pairs.end()); //为什么这样预处理就可以了？试想v1--[1,4]与v2--[2,3]，题目规定了数对数组注定右大于左，所以v1[0] for(int j = 0; j = b）dp[i][j] = 2（如果 c
（如果 c
优化：寻找数字 a 所在的位置，比起套一层循环，哈希表更好
class Solution {public: int lenLongestFibSubseq(vector& arr) { int n = arr.size(); unordered_map hash; for(int i = 0; i例题28：最长等差数列 ★
最长等差数列
细节很多的题
分析后可知，就像例题27一样，dp[i]是解决不了问题的，所以用 dp[i][j] 表示以 i j （i
状态转移方程：
分析知，我们根据 i j 位置元素算得 a 可以组成等差数列，如果 i 位置前有多个 a，最靠近 i 位置的 a，以其和 i 位置为结尾的最长等差子序列一定最长
但这道题不像上一题一样数组严格递增，提前把数据和相应位置都映射到哈希表里以快速找到最靠近 i 位置的 a 的方式也不可取，但如果不优化的话时间复杂度高达 O(N^3)
两种优化思路：
- 用哈希表存储 数据 和 数据所在的位置（位置用数组存储）
—— 但存在问题：找到数据对应的位置数组后也得遍历数组去寻找最靠近 i 位置的位置，如果数据量过大，复杂度仍是O(N^3)
- 一边dp，一边填写哈希表：
class Solution {public: int longestArithSeqLength(vector& nums) { unordered_map hash; hash[nums[0]] = 0; int n = nums.size(); vector dp(n,vector(n,2)); int ret = 2; //还要注意循环始末： for(int i = 1; i例题29：等差数列划分 II - 子序列
等差数列划分 II - 子序列
● 这道题没说统计的等差子序列不能重复
与上一题不同的是，上一题统计最长长度，这一题统计等差数列个数
状态表示：
dp[i][j]：以 i j 位置元素结尾的数组中等差子序列的数目
状态转移方程：
i 位置元素 b，j 位置元素 a，算得元素 c = 2b - a，设 c 位置为 k
（如果k位置存在且 k
初始化：
不用初始化，全 0 即可
优化：
使用了上一题的第一种思想：用哈希表存储 数据 和 数据所在的位置（位置用数组存储）
class Solution {public: int numberOfArithmeticSlices(vector& nums) { int n = nums.size(); unordered_map hash;//-2^31 for(int j = i+1; j七、两个数组的 dp
例题35：最长公共子序列 ★
最长公共子序列
据老师所述的超经典的一道题，我们许多的经验都由这道题而来
状态表示：
对于两个字符串的问题：
1.选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象
2.根据题目要求确定状态表示
dp[i][j]：s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内所有的子序列中，最长的公共子序列的长度
状态转移方程：
首先需要明白的是：若s[i] == s[j] == x，则 s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内所有的子序列中，最长的公共子序列一定是以最后这个 x 结尾的
反证法：
如果其中一个（以 s1 为例）的最长公共子序列的结尾是其内部的某个数，显然这个数肯定是 x，那么 s1 最后的 x 显然也能充当最长公共子序列的结尾；
如果两个字符串的最长公共子序列的结尾都是内部的某个数，s1、s2 的末尾是两个相同的 x，显然也能接上成为最长公共子序列的结尾
如果 s[i] == s[j]：dp[i][j] = dp[i-1][j-1] + 1
如果 s[i] != s[j]：dp[i][j] = max( dp[i][j-1], dp[i-1][j], dp[i-1][j-1] )（分析可知，这道题里最后一种情况已被前两种情况包含，但因为这道题只是求最大长度，这么写并无影响（当然，删掉更优））
初始化：
首先，关于字符串的 dp 问题，空串是有研究意义的；然后，突然说这个是因为如果我们引入空串的概念，是可以方便我们去初始化的
本来我们需要将左边第一列和上面第一行初始化，但若我们增添一行一列，将格外多出的部分当做空串并设为 0（含义：连数都没有自然也就没有公共子序列），我们的初始化就完成了
填表顺序：从上到下，从左向右
返回值：dp[m][n]（增添一行一列后，m：s1的长度，n：s2的长度）
class Solution {public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); text1 = " " + text1; text2 = " " + text2;//●统一下标 vector dp(m+1,vector(n+1)); //从上向下，从左往右 for(int i = 1; i for(int j = 1; j if(text1[i] == text2[j]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max( dp[i][j-1], dp[i-1][j]); } } return dp[m][n]; }};public: int maxUncrossedLines(vector int m = nums1.size(), n = nums2.size(); vector for(int j = 1; j if(nums1[i-1] == nums2[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[m][n]; }};public: int numDistinct(string s, string t) { const int MOD = 1e9 + 7; //dp[i][j]：s的以i位置结尾的所有子序列中有多少能表示t以j位置结尾的子串（做这么多题了，想必你能分清子序列和子串的区别） //s[i] == t[j] dp[i][j] += dp[0 ~ i-1][j-1] //s[i] != t[j] dp[i][j] = 0 int m = s.size(), n = t.size(); vector for(int j = 1; j if(s[i-1] == t[j-1]) for(int k = 0; k初始化：
初始化情况和 01背包第二问 一样
返回值：
若最终为 -1 ，要注意返回 0
#include using namespace std;#includeconst int N = 1010;int n, V, v[N], w[N];int dp[N][N];int main() { cin >> n >> V; for(int i = 1; i > v[i] >> w[i]; for(int i = 1; i for(int j = 0; j dp[i][j] = dp[i-1][j]; if(j = v[i]) dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]); } } cout for(int j = 0; j dp[i][j] = dp[i-1][j]; if(j = v[i] && dp[i][j-v[i]] != -1) dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]); } } cout cin n V; for(int i = 1; i for(int j = v[i]; j dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } cout for(int j = v[i]; j if(dp[j-v[i]] != -1) dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } cout public: int coinChange(vector int n = coins.size(); vector for(int j = 0; j dp[i][j] = dp[i-1][j]; if(j = coins[i-1]) //注意coins的下标 dp[i][j] = min(dp[i-1][j],dp[i][j - coins[i-1]] + 1); } } return dp[n][amount] == 0x3f3f3f3f ? -1 : dp[n][amount]; }};public: int change(int amount, vector //dp[i][j]：从前 i 个硬币中选，总价值为 j，有多少种组合方式 //不选 i：dp[i][j] = dp[i-1][j] //选一个 i：dp[i][j] += dp[i-1][j-coins[i]]（j = coins[i]） //………………………… //dp[i][j] = dp[i-1][j] (+ dp[i][j-coins[i]]) int n = coins.size(); vector for(int j = 0; j dp[i][j] += dp[i-1][j]; if(j = coins[i-1]) //注意coins的下标 dp[i][j] += dp[i][j-coins[i-1]]; } } return dp[n][amount]; }};public: int numSquares(int n) { const int INT = 0x3f3f3f3f; int num = sqrt(n);//★ vector for(int j = 0; j dp[i][j] = dp[i-1][j]; if(j = i*i) dp[i][j] = min(dp[i-1][j], dp[i][j-i*i] + 1); } } return dp[num][n]; }};public: int findMaxForm(vector int num = strs.size(); vector //统计该字符串i中 0 1 的个数 int a = 0, b = 0; for(auto ch : strs[i-1]){ if(ch == '0') a++; else b++; } for(int j = 0; j for(int k = 0; k dp[i][j][k] = dp[i-1][j][k]; if(j = a && k = b) dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-a][k-b] + 1); } } } return dp[num][m][n]; }};public: int findMaxForm(vector int num = strs.size(); vector //统计该字符串i中 0 1 的个数 int a = 0, b = 0; for(auto ch : strs[i-1]){ if(ch == '0') a++; else b++; } for(int j = m; j = a; j--){ for(int k = n; k = b; k--){ dp[j][k] = max(dp[j][k], dp[j-a][k-b] + 1); } } } return dp[m][n]; }};public: int profitableSchemes(int n, int minProfit, vector const int MOD = 1e9 + 7; int len = group.size();//len个工作，n个人，minProfit的利润 vector for(int j = 0; j for(int k = 0; k dp[i][j][k] = dp[i - 1][j][k]; if(j = group[i-1]) dp[i][j][k] += dp[i - 1][j - group[i-1]][max(0, k - profit[i-1])];//注意下标 dp[i][j][k] %= MOD; } } } return dp[len][n][minProfit]; }};public: int combinationSum4(vector vector for(auto x : nums){ if(i = x) dp[i] += dp[i - x]; } } return dp[target]; }};public: int numTrees(int n) { vector
- ���题54：不同的二叉搜索树 ★
上一篇：方舟怎么找其他服务器?
下一篇：怎么进入id服务器?
