声明：
本文仅为作者为了复习而写，并非作为教程使用！
斐波那契类型
通常是线性的，状态转移为相邻元素或受到限制的邻元素
1.使用最小花费爬楼梯
n<=2 特殊处理 当前楼梯阶层可由i-1或i-2而来 推出状态转移方程 ： f[i] = min(f[i - 1] + cost[i - 1] , f[i - 2] + cost[i - 2])
题目描述：
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> f(n + 1 , 0x3f);
f[0] = f[1] = 0;
for (int i = 2 ; i <= n ; i ++ )
{
f[i] = min(f[i - 1] + cost[i - 1] , f[i - 2] + cost[i - 2]);
}
return f[n];
}
};
2.打家劫舍
n<=2特殊处理 当前房间选择偷或不偷，若为偷则f[i] = f[i - 2] + nums[i]，若为不偷则f[i] = f[i - 1]
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (!n) return 0;
vector<int> f(n , 0);
f[0] = nums[0];
if (n == 1) return nums[0];
f[1] = max(f[0] , nums[1]);
if (n == 2) return max(nums[0] , nums[1]);
for (int i = 2 ; i < n ; i ++ )
{
f[i] = max(f[i - 2] + nums[i] , f[i - 1]);
}
return f[n - 1];
}
};
矩阵
通常为有限制的从一个或者多个方向转移而来，需要注意边界问题
1.三角形最小路径和（数字三角形）
需要注意当j(列) 边界(0)的时候，只能从上方而来，当i=j(对角线位置)边界的时候，只能从左上方而来。对于其他位置则可推出状态转移方程：f[i][j] = min(f[i - 1][j] , f[i - 1][j - 1]) + triangle[i][j];
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例： 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int> > f(n , vector<int>(n , 0x3f));
f[0][0] = triangle[0][0];
for (int i = 1 ; i < n ; i ++ )
{
f[i][0] = f[i - 1][0] + triangle[i][0];
for (int j = 1 ; j < i ; j ++ )
f[i][j] = min(f[i - 1][j - 1] , f[i - 1][j]) + triangle[i][j];
f[i][i] = f[i - 1][i - 1] + triangle[i][i];
}
int ans = 0x3f3f3f3f;
for (int i = 0 ; i < n ; i ++ ) ans = min(ans , f[n - 1][i]);
return ans ;
}
};
2.最大正方形
注意边界当i=0或j=0时，最多面积只能为1。将当前位置作为正方形的右下角，则一定满足以此右下角为正方形的边长一定为其min(上方、左方、左上方三个位置为右下角的正方形的边长) + 1。即可推出状态转移方程为：f[i][j] = min(min(f[i - 1][j] , f[i][j - 1]) , f[i - 1][j - 1]) + 1;
题目描述：
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
详细题目描述https://leetcode.cn/problems/maximal-square/?envType=study-plan-v2&envId=dynamic-programming
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int> > f(n , vector<int>(m , 0));
int ans = 0;
for (int i = 0 ; i < n ; i ++ )
{
for (int j = 0 ; j < m ; j ++ )
{
if (matrix[i][j] == '1')
{
if (!i || !j) f[i][j] = 1;
else f[i][j] = min(min(f[i - 1][j] , f[i - 1][j - 1]) , f[i][j - 1]) + 1;
}
ans = max(ans , f[i][j]);
}
}
return ans * ans ;
}
};
最长递增子序列
通常是根据一些特定的条件确定状态转移的上一个位置 如递增，不下降，定差，多元组等思路比较简单
1.最长上升子序列
只要满足在当前元素之前且小于当前元素，即为转移目标。状态转移方程：f[i] = max(f[i] , f[j - 1] + 1);
题目描述：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1 , 1);
int res = 1;
for (int i = 0 ; i < n ; i ++ )
{
for (int j = 0 ; j < i ; j ++ )
{
if (nums[j] < nums[i]) f[i] = max(f[i] , f[j] + 1);
res = max(f[i] , res);
}
}
return res;
}
};
2.最长上升子序列的个数
此题为1题的变式，状态转移相同。需要注意的是题意是统计最长上升子序列的个数，即长度相同且最长。为每个下标位置存下以该下标结尾的子序列的个数(最长)，需要添加参照(如maxLen)确保每次更新的是否为最长序列个数。
题目描述：
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例： 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1 , 1) , cnt(n + 1 , 1);
int res = 0 , maxLen = 0;
for (int i = 0 ; i < n ; i ++ )
{
for (int j = 0 ; j < i ; j ++ )
{
if (nums[j] < nums[i])
{
if (f[i] < f[j] + 1)
{
f[i] = f[j] + 1;
cnt[i] = cnt[j];
}
else if (f[i] == f[j] + 1) cnt[i] += cnt[j];
}
}
if (f[i] > maxLen)
{
maxLen = f[i];
res = cnt[i];
}
else if (f[i] == maxLen)
res += cnt[i];
}
return res;
}
};
3.最长定差子序列
题目所给的定差在状态转移过程中可能存在让我们的中间状态的下标为负数的情况，而使用unordered_map就可以很好的解决这个问题。使用一维代表值为i的时候其差为difference的序列长度，则有状态转移方程为：f[i] = f[i - difference] + 1;
题目描述：
给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例： 输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2 输出：4 解释：最长的等差子序列是 [7,5,3,1]。
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int n = arr.size();
if (!n) return 0;
unordered_map<int , int> f;
int res = 0;
for (int i : arr)
{
f[i] = f[i - difference] + 1;
res = max(res , f[i]);
}
return res;
}
};
3.最长等差序列
整体思路同2题，但是等差序列存在多个不一样的d(公差)，因此需要使用二维来记录不同的d(公差)的序列长度。f[i][d]表示以第i个元素结尾的公差为d的序列的长度。则状态转移方程为:f[i][d] = f[j][d];此处的i,j和1题具有相同意义。
题目描述：
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
示例： 输入：nums = [9,4,7,2,10] 输出：3 解释：最长的等差子序列是 [4,7,10]。
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size();
int res = 0;
vector<unordered_map<int , int> > f(n);
for (int i = 1 ; i < n ; i ++ )
{
for (int j = 0 ; j < i ; j ++ )
{
int d = nums[i] - nums[j];
f[i][d] = f[j][d] + 1;
res = max(res , f[i][d]);
}
}
return res + 1;
}
};
4.俄罗斯套娃信封问题
需要考虑信封的长、宽均小于才能套娃进去。使用 Lambda 表达式自定义排序规则。状态转移的思路同1.题 即f[i] = max(f[i] , f[j] + 1);
题目描述：
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例： 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
});
int res = 1;
vector<int> f(n + 1 , 1);
for (int i = 0 ; i < n ; i ++ )
{
for (int j = 0 ; j < i ; j ++ )
{
if (envelopes[i][1] > envelopes[j][1] && envelopes[i][0] > envelopes[j][0])
{
f[i] = max(f[i] , f[j] + 1);
}
res = max(res , f[i]);
}
}
return res;
}
};
二分优化
但是以上这个做法在数据较大的时候不能通过题目O(n²)的时间复杂度。所以使用二分查找的方式减小时间复杂度O(nlogn);
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty()) {
return 0;
}
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
});
vector<int> f = {envelopes[0][1]};
for (int i = 1; i < n; ++i) {
if (int num = envelopes[i][1]; num > f.back()) {
f.push_back(num);
}
else {
auto it = lower_bound(f.begin(), f.end(), num);
*it = num;
}
}
return f.size();
}
};
最长公共子序列
通常为考虑两个序列互相为参照物从特定的位置状态转移过来的max值。在某些特殊情况下，回文串的寻找也可以转换为最长公共子序列问题。
1.最长公共子序列
每次到一个新的位置的时候先初始化当前位置的最长值为max(1序列以上一个字符结尾最长值 ， 2序列以上一个字符结尾的最长值)(或者理解为当前位置两个序列的字符不相同的情况),如果相同则有状态转移:f[i][j] = max(f[i - 1][j - 1] + 1 , f[i][j])；
题目描述：
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例： 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
text1 = " " + text1;
text2 = " " + text2;
vector<vector<int>> f(n + 1 , vector<int>(m + 1 , 0));
int res = 0;
for (int i = 1 ; i <= n ; i ++ )
{
for (int j = 1 ; j <= m ; j ++ )
{
f[i][j] = max(f[i - 1][j] , f[i][j - 1]);
if (text1[i] == text2[j]) f[i][j] = max(f[i - 1][j - 1] + 1 , f[i][j]);
res = max(f[i][j] , res);
}
}
return res;
}
};
2.让字符串成为回文串的最小插入次数
前文提到过，可以通过将回文串问题转化为最小公共子序列问题，即一个序列于他相反的序列(reverse)的最长公共子序列的长度即为最长回文串的长度。
题目描述：
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例： 输入：s = "mbadm" 输出：2 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
auto rs = s;
reverse(rs.begin() , rs.end());
rs = " " + rs;
s = " " + s;
int res = 0;
vector<vector<int> > f(n + 1 , vector<int>(n + 1 , 0) );
for (int i = 1 ; i <= n ; i ++ )
{
for (int j = 1 ; j <= n ; j ++ )
{
f[i][j] = max(f[i - 1][j] , f[i][j - 1]);
if (s[i] == rs[j])
f[i][j] = max(f[i - 1][j - 1] + 1 , f[i][j]);
res = max(f[i][j] , res);
}
}
return n - res;
}
};
背包问题
背包问题是一个很经典的dp通常为二维，可根据题目要求优化到一维。核心是推导转移方程：以前i个物品结尾的不超过j的代价所获得的最大/最小价值
1.01背包问题
f[i][j] 表示前i个物品在使用背包容积不超过j的最大价值。分为选or不选 不选的时候当前的最大价值就是上一个(i - 1)个物品的最大价值 ： f[i][j] = f[i - 1][j]; 选的时候：f[i][j] = max(f[i][j] , f[i - 1][j - v] + w);
题目描述：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
示例： 输入：[[4,5],[1,2],[2,4],[3,4],[4,5]] 输出：8 解释： 在这个样例中，背包容量为 5，物品信息如下： 物品 1：体积 1，价值 2 物品 2：体积 2，价值 4 物品 3：体积 3，价值 4 物品 4：体积 4，价值 5 可以选择物品 2 和物品 3，总体积为 5，总价值为 8，这是最大价值。
class Solution {
public :
int o1BagQusetionSolve(int n , int m , vector<int>& v , vector<int>& w)
{
vector<vector<int> > f(n + 1 , vector<int>(m + 1 , 0));
for (int i = 1 ; i <= n ; i ++ )
{
for (int j = 0 ; j <= m ; j ++ )
{
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j] , f[i - 1][j - v[i]] + w[i]);
}
}
return f[n][m];
}
};
01背包的空间优化O(n)
二维背包的转移方程中的i始终是由i - 1而来的，可以尝试去掉i - 1。倒叙遍历是因为正序会导致某些状态被使用多次。
class Solution {
public :
int o1BagQusetionSolve(int n , int m , vector<int>& v , vector<int>& w)
{
vector<int> f(m + 1 , 0);
for (int i = 1 ; i <= n ; i ++ )
{
for (int j = m ; j >= v[i] ; j -- )
{
f[j] = max(f[j] , f[j - v[i]] + w[i]);
}
}
return f[m];
}
};
2.完全背包
题目描述：
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
示例： 输入样例：[[4,5][1,2],[2,4],[3,4],[4,5]]; 输出样例：10 解释： 物品 2 放入背包 5 次，总体积为 5，总价值为 10。 物品 3 放入背包 2 次，总体积为 4，总价值为 8。 物品 4 放入背包 2 次，总体积为 6，总价值为 8。 物品 1 放入背包 2 次，总体积为 8，总价值为 10。 物品 5 放入背包 2 次，总体积为 8，总价值为 10。
class Solution {
public :
int completeBagQuestionSolve(int n , int m , vector<int>& v , vector<int>& w)
{
vector<vector<int> > f(n + 1 , vector<int>(m + 1 , 0));
for (int i = 1 ; i <= n ; i ++ )
{
for (int j = 0 ; j <= m ; j ++ )
{
if (j >= v[i]) f[i][j] = max(f[i - 1][j] , f[i][j - v[i]] + w[i]);
else f[i][j] = f[i - 1][j];
}
}
return f[n][m];
}
};
完全背包的空间优化
原理和01背包空间优化类似，但是需要重复使用状态所以正序遍历。
class Solution {
public :
int completeBagQuestionSolve(int n , int m , vector<int>& v , vector<int>& w)
{
vector<int> f(m + 1 , 0);
for (int i = 1 ; i <= n ; i ++ )
{
for (int j = v[i] ; j <= m ; j ++ )
{
f[j] = max(f[j] , f[j - v[i]] + w[i]);
}
}
return f[m];
}
};
多重背包类似、混合背包类似写法省略。
完结撒花
(暂时)
给时光以生命，给岁月以文明。
Comments 3 条评论
18₴fihveweiAgJ🗝 https://m.tb.cn/h.6eKdAX8 HU926 ~这个商品很不错，我还有一张【5】元，限量优惠I券送给你，快来看看！【哔哩哔哩2025新品+GSC+BanG+Dream!+Ave+Mujica+制服ver.毛绒玩偶】
哇哇哇 好厉害！
@huyushuang 哇哇哇