代码随想录算法训练营 Day44 动态规划 ⅩⅠ 子序列问题

时间：2025-05-15 08:16:38

动态规划

题目

1143. 最长公共子序列 - 力扣（LeetCode）
公共子序列，类似于最长重复子数组，但是不要求连续 (子序列)
1. 定义 dp，dp[i][j] 表示以 i-1 与 j-1 结尾的最长公共子序列的长度
2. 定义递推公式
如果字符相同，则在基础上+1
if (text1[i-1] == text2[i-1]) dp[i][j] = dp[i-1][j-1] +1
如果字符不同，分别屏蔽 i-1 和 j-1 对比字符
else dp[i][j] = std::max(dp[i][j-1], dp[i-1][j])
3. 初始化 dp，由于 dp 是从前往后推导，且定义为 i-1, j-1
其中 0-1 时候结果为 0 意思是字符串与空字符查找那最大的公共子序列结果为 0
4. 遍历顺序是从前往后，从上到下遍历
5. 打印 dp

int longestCommonSubsequence(string text1, string text2) {
	// 定义dp数组
	std::vector<std::vector<int>> dp(text1.size()+1, std::vector<int>(text2.size()+1, 0));
	// 遍历dp数组
	for (int i = 1; i <= text1.size(); ++i) {
		for (int j = 1; j <= text2.size(); ++j) {
			// 递推公式两种情况
			if (text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
		}
	}
	return dp[text1.size()][text2.size()];
}

1035. 不相交的线 - 力扣（LeetCode）
本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
1. 定义 dp，dp[i][j] 表示以 i-1 j-1 结尾的最长公共子序列长度
2. 递推公式类上题
3. 初始化类似上题
4. 遍历顺序同上题
5. 打印 dp

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
	// 定义dp数组 i-1 j-1 结尾之前最大的公共子序列
	std::vector<std::vector<int>> dp(nums1.size()+1, std::vector<int>(nums2.size()+1, 0));
	// for
	for (int i = 1; i <= nums1.size(); ++i) {
		for (int j = 1; j <= nums2.size(); ++j) {
			if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
		}
	}
	return dp[nums1.size()][nums2.size()];
}

53. 最大子数组和 - 力扣（LeetCode）
之前贪心做过 [[Day27 贪心Ⅰ 分饼干 摆动序列 最大子序列和#题目]]，贪心就是小于 0不取
使用 dp 再做一遍，整体类似于基本的 dp 如打家劫舍、股票
1. 定义 dp，dp[i] 表示 i 之前的最大连续子数组和
2. 递推公式：基于之前的结果与当前结果的最大值作为当前 i 的 dp 值
dp[i] = max(dp[i-1]+nums[i], nums[i])
3. 初始化由于都是从前面推导的，因此 dp[0] = nums[0]
最大和要寻找 dp 最大值，使用 res 比较获取
4. 遍历顺序从前往后
5. 打印 dp

int maxSubArray(vector<int>& nums) {
	// 定义dp数组
	std::vector<int> dp(nums.size(), 0);
	// 初始化dp res也定义为nums[0]值保不忽略第一个元素
	dp[0] = nums[0];
	int res = nums[0];
	// 遍历dp
	for (int i = 1; i < nums.size(); ++i) {
		dp[i] = std::max(dp[i-1] + nums[i], nums[i]);
		if (dp[i] > res) res = dp[i];
	}
	return res;
}

392. 判断子序列 - 力扣（LeetCode）
编辑距离问题，本体的本质就是求 s 与 t 的最长公共子序列，只不过这个 s 不可删除
1. dp[i][j] 表示 i-1, j-1 为结尾的 s/t 字符串的最长公共子序列的长度
2. 递推公式类似求最长公共子序列固定 s 不变，只删除 t（dp[i][j-1]）
if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]+1
else dp[i][j] = dp[i][j-1]
3. 初始化 dp 数组
因为定义为 i-1,j-1 因此初始化为 0 即可，之后使用递推公式就可以推出
4. 遍历顺序从前往后遍历，结果与 s 相等说明可以匹配
5. 打印 dp

bool isSubsequence(string s, string t) {
	// 定义dp
	std::vector<std::vector<int>> dp(s.size()+1, std::vector<int>(t.size()+1, 0));
	// 遍历dp
	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]; // t 删除 匹配s
		}
	}
	if (dp[s.size()][t.size()] == s.size()) return true;
	else return false;
}

相关文章