【Weekly Algorithm】算法周记之《代码随想录》动态规划（七）
学习小结
本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习子序列相关内容，其中的编辑距离在网络搜索引擎的期末考试见过。但通过本次学习，逐渐感受到在算法，或者说计算机的世界中，很多事情往往会通过抽象来变得简洁从而易于处理。
动态规划
最长重复子数组
题意：给两个数组，问两个数组中最长重复的子数组长度是什么
方法：用二维dp，dp[i][j] 代表第一个数组 i-1 为尾部和第二个数组 j-1 处为尾部，最长重复子数组长度。
递推公式，当 num1[i-1]==num2[j-1]，即可 dp[i][j] = dp[i-1][j-1]+1;
初始化，都为0
遍历顺序，无所谓，不过从前向后就可
举例……参考代码随想录思路的解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
int max_len = 0;
for (int i = 1; i < nums1.size()+1; i++) {
for (int j = 1; j < nums2.size()+1; j++) {
if(nums1[i-1] == nums2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > max_len) max_len = dp[i][j];
}
}
}
return max_len;
}
};优化一下，用滚动数组，注意每次从后向前遍历，以及刷0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
// vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
vector<int> dp(nums2.size()+1, 0);
int max_len = 0;
for (int i = 1; i < nums1.size()+1; i++) {
for (int j = nums2.size(); j > 0; j--) {
if(nums1[i-1] == nums2[j-1]) {
dp[j] = dp[j-1] + 1;
if (dp[j] > max_len) max_len = dp[j];
}
else {
dp[j] = 0; // 需要刷零避免前两层的记录影响
}
}
}
return max_len;
}
};最长公共子序列
题意，给两个字符串，给出两串的最长公共子序列的长度
方法：与[[最长重复子数组]]相近，不过本题不要求连续，所以递推公式除了上一个相同+1之外，还保存两个子序列可能的最长情况。
参考代码随想录的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0));
for (int i = 1; i < text1.size()+1; i++) {
for (int j = 1; j < text2.size()+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]);
}
}
}
// for (int i = 0; i < text1.size()+1; i++) {
// for (int j = 0; j < text2.size()+1; j++) {
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
return dp[text1.size()][text2.size()];
}
};不相交的线
题意：两个整型数组，相同数字可以两两相连，但是线不能交错。求最大连线数。
方法：换了个题意的[[最长公共子序列]]，除了题目，其余都一样，其余省略。
最大子序和
题意：给一个数组，找个其中子序列之和最大的和。
方法：
dp[i] 是到下标为 i 为尾部的子序列最大和数值
递推公式比较有意思，两种情况，一个是延续之前的最大和 dp[i] = dp[i-1]+num[i];或者不延续，从 i 处新开 dp[i] = num[i]，两种情况取较大数值即可。
初始化，dp[0] 取 num[0],其它的初始化不重要，毕竟都会被覆盖。
遍历顺序：从前向后。
举例：……参考代码随想录思路的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i-1]+nums[i], nums[i]);
if (dp[i] > result) {
result = dp[i];
}
}
// for (int i = 0; i < nums.size(); i++) {
// cout << dp[i] << " ";
// }
// cout << endl;
return result;
}
};判断子序列
题意：给两个字符串序列，判断一个字符串是否为另一个字符串的子序。
方法：其实[[最长公共子序列]]类似，只是说判断公共字符串的长度是否为子串长度相等，而且递推公式中，如果两个字符不相等，稍微更改，只会继承本字符的匹配情况，因为明确表示了该字符串是否为另一字符串的子串，不能反过来。
参考代码随想录思路的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size()+1, vector<int>( t.size()+1, 0));
// dp[i][j] 字符串s[i-1] 和 t[j-1] 为止最长子序列长度
// 初始化 第一行和第一列都为 0 即可
// 递推公式，当两个字符相等时，dp[i][j]=dp[i-1][j-1]+1;不同时，dp[i][j]则取dp[i][j-1];相当于匹配t失败，延续之前匹配结果（要么是匹配上的情况，要么是0，也就是断匹配了
for(int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i-1] == t[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = dp[i][j-1];
}
}
}
return (dp[s.size()][t.size()] == s.size()) ? true : false;
}
};不同子序列
题意，判断一个字符串和另一个字符串的几种不同子序列相同（这里的子序列由字符串删除字符获得），求不同子序列的数量。
方法，是编辑距离的简单版，只考虑删除字符的情况，如果对应字符相等，就取上个字符的匹配情况
dp[i][j]是s[i]到t[j]匹配时，已有匹配到的数量，这个数量指的是可能出现的前缀数量，如果字符匹配成功，就继承上一个；如果之前有重复字符，则会叠加参考代码随想录思路的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size()+1, 0));
for(int i = 0; i < s.size(); i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i-1] == t[j-1]) {
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.size()][t.size()];
}
};两个字符串的删除操作
题意：给两个字符串，请给出多少次删除（一次删除任意字符串的一个字符）能使两个字符串相等。
方法：
- dp[i][j] 对于一个字符串的前 i-1 个字符和另一个字符串的前 j-1 个字符相同需要删除次数
- 递推公式，当字符相同时，dp[i][j] = dp[i-1][j-1]；也就是说对于这两个位置的字符不需要删除。当字符不相同时，dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);也就是删除其中个字符串中的字符，那可能说，要是两个字符都要删除呢？这个状态包含于上一次内，也就是说两个删除一个字符情况也就是删除两个字符。
- 初始化，第一行第一列，分别是一个字符串与空字符串相等需要的删除次数，也就是删完，取字符串长度。
- 遍历顺序，从前向后，前上到下，普通顺序
- 举例……
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1, 0));
for (int i = 0; i < word1.size()+1; i++) {
dp[i][0] = i;
}
for (int j = 0; j < word2.size()+1; j++) {
dp[0][j] = j;
}
for (int i = 1; i < word1.size()+1; i++) {
for (int j = 1; j < word2.size()+1; j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
else {
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);
}
}
}
return dp[word1.size()][word2.size()];
}
};编辑距离
题意，给两个字符串，要求编辑距离（也就是对任意字符串增删换使其相同的次数），增一个字符，删一个字符，换一个字符的操作个数。
方法，[[两个字符串的删除操作]]的进阶，现在不只是删除，还有增加字符和替换的操作，但是，增加字符，其实可以等效为另一个字符串删除那个要增加的字符。而替换操作，可以理解为两边字符串同时删除，但只算一次操作(dp[i][j]=dp[i-1][j-1]+1)，除了这个递推公式加上一条，其余相同。
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
for(int i = 0; i < word1.size()+1; i++) {
dp[i][0] = i;
}
for(int j = 0; j < word2.size()+1; j++) {
dp[0][j] = j;
}
for (int i = 1; i < word1.size()+1; i++) {
for (int j = 1; j < word2.size()+1; j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
else {
dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]})+1;
}
}
}
return dp[word1.size()][word2.size()];
}
};回文子串
题意，给一个字符串，统计其中回文字符串的个数
方法，如果按照之前思路dp[i]代表到下标 i 回文字符串个数的话，各个状态间无联系无规律。故用下面的 dp 定义。
除了 dp 定义有改变，还有遍历顺序与以往不太一样，由于递推公式的关系。
具体内容在注释中参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45class Solution {
public:
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
// 这里的 dp[i][j] 是字符串 i 到 j（闭区间）是否为回文字符串、
// 初始化默认全部为 false
// 先看递推公式，当 s[i] != s[j] dp[i][j] = false;
// 复杂的是 s[i] == s[j]时，如果 i==j，那么 dp[i][j] = true，因为”a“算回文字符串
// 如果j==i+1，那么也是true，“aa”这种情况中也算回文字符串
// 如果 上述都不是，那么 dp[i][j] = dp[i+1][j-1] ，i到j是否为回文字符串取决于 i+1到j-1是否为回文字符串
// 由于递推公式有 dp[i][j] = dp[i+1][j-1],那么要先遍历 i 较大的情况以及 j 较小的情况
for(int i = s.size()-1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if (s[i] != s[j]) {
dp[i][j] = false;
}
else if (i == j) {
dp[i][j] = true;
}
else if (j == i + 1) {
dp[i][j] = true;
}
else {
dp[i][j] = dp[i+1][j-1];
}
}
}
int count = 0;
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < s.size(); j++) {
if (dp[i][j] == true) {
count++;
}
//cout << dp[i][j] << " ";
}
//cout << endl;
}
return count;
}
};最长回文子序列
题意：找出字符串上，最长回文子序列长度（可删字符）
方法：详情写在注释中，值得注意的是，dp是闭区间
参考代码随想录思路的解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
// dp[i][j]代表了 s[i]到s[j] 最长回文子序列的长度
// 在 s[i] == s[j] 时，dp[i][j] = dp[i+1][j-1]+2
// 不相等时， 则从两个方向取大值，dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
// 初始化时，所有相等得先赋值1
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
for (int i = s.size()-1; i >= 0; i--) {
for (int j = i+1; j < s.size(); j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i+1][j-1] + 2;
}
else {
dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
}
}
}
return dp[0][s.size()-1];
}
};
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-01-12
【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...
2025-02-09
【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...
系列文章