Day53【动态规划】1143.最长公共子序列、1035.不相交的线、53.最大子序和
1143.最长公共子序列
力扣题目链接/文章讲解
视频讲解
本题最大的难点还是定义 dp 数组
本题和718.最长重复子数组区别在于这里不要求是连续的了，但要有相对顺序
直接动态规划五部曲！
1、确定 dp 数组下标及值含义
dp[i][j]：取 text1 中下标 [0, i - 1] 的子字符串与 text2 中下标为 [0, j - 1] 的子字符串，dp[i][j] 的值表示这两个子字符串的最长公共子序列长度为 dp[i][j]
2、确定递推公式
主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1] 不相同
注意不要求连续
- 如果 text1[i - 1] 与 text2[j - 1] 相同，那么找到了一个公共元素，所以 dp[i][j] = dp[i - 1][j - 1] + 1
- 如果 text1[i - 1] 与 text2[j - 1] 不相同，则 text1[0, i - 1] 与 text2[0, j - 1] 的最长公共子序列长度一定为 text1[0, i - 2] 与 text2[0, j - 1] 的最长公共子序列长度或 text1[0, i - 1] 与 text2[0, j - 2] 的最长公共子序列长度之一，取最大的
即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
代码如下
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]);
}3、dp 数组初始化
需要初始化第一列和第一行 dp 数组
先看看 dp[i][0] 应该是多少呢？
test1[0, i-1] 和空串的最长公共子序列自然是 0，所以 dp[i][0] = 0
同理 dp[0][j] 也是 0
其他下标都是随着递推公式逐步覆盖，初始为多少都可以
4、确定遍历顺序
从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图
那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵
5、打印 dp 数组验证
代码如下
class 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(); ++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;elsedp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}return dp[text1.size()][text2.size()];}
};这里，定义 dp 数组为取 text1 中下标 [0, i - 1] 的子字符串与 text2 中下标为 [0, j - 1] 的子字符串，dp[i][j] 的值表示这两个子字符串的最长公共子序列长度为 dp[i][j]
这里的 i - 1 是为了方便初始化
我们也可以如下定义： 定义 dp 数组为取 text1 中下标 [0, i] 的子字符串与 text2 中下标为 [0, j] 的子字符串，dp[i][j] 的值表示这两个子字符串的最长公共子序列长度为 dp[i][j]
这样我们的代码在初始化部分会复杂一点
代码及注释如下
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// 1、定义dp数组下标及含义// dp[i][j]表示text1[0, i]与text2[0, j]这两个子串的最长公共子序列的长度vector<vector<int> > dp(text1.size(), vector<int>(text2.size(), 1));// 2、确定递推公式：考虑text1[i]与text2[j]是否相同// 如果相同，则dp[i][j] = dp[i-1][j-1]+1，即text1[0,i-1]与text2[0, j-1]这两子串的最长公共子序列长度+1// 如果不相同，则dp[i][j]一定为text1[0, i-1]与text2[0, j]的最长公共子序列长度或text1[0, i]与text2[0, j-1]的最长公共子序列长度之一，取最大的// 3、dp数组初始化，需要初始化第一行和第一列for (int j = 0; j < text2.size(); ++j) { // 初始化第一行// dp[0][j]表示text1[0]与text2[0, j]的最长公共子序列长度，如果text2[0, j]包含text1[0]，则为1，否则为0if (text2[j] == text1[0])break; // 如果遍历到满足条件的了，则当前包括后面的text2[0, j]一定包含text1[0]了，就为1dp[0][j] = 0; // 否则说明当前串text2[0, j]一定不含text1[0]}for (int i = 0; i < text1.size(); ++i) { // 初始化第一列if (text1[i] == text2[0])break;dp[i][0] = 0;}// 4、确定遍历顺序：从前向后从上向下遍历填充for (int i = 1; i < text1.size(); ++i)for (int j = 1; j < text2.size(); ++j)if (text1[i] == text2[j])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);// 5、打印dp数组验证return dp[text1.size() - 1][text2.size() - 1];}
};1035.不相交的线
力扣题目链接/文章讲解
视频讲解
本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度
和上一道题一模一样
直接上代码
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// dp[i][j]表示nums1[0, i]与nums2[0, j]这两个子数组的最长公共子序列的长度vector<vector<int> > dp(nums1.size(), vector<int>(nums2.size(), 1));for (int j = 0; j < nums2.size(); ++j) {if (nums2[j] == nums1[0]) break;dp[0][j] = 0;}for (int i = 0; i < nums1.size(); ++i) {if (nums1[i] == nums2[0]) break;dp[i][0] = 0;}for (int i = 1; i < nums1.size(); ++i)for (int j = 1; j < nums2.size(); ++j) {if (nums1[i] == nums2[j])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}return dp[nums1.size()-1][nums2.size()-1];}
};53.最大子数组和
力扣题目链接/文章讲解
视频讲解
本题可以用贪心算法，也可以用动态规划
1、确定 dp 数组下标及值含义
dp[i]：下标 i 表示以 nums[i] 为结尾的有最大和的连续子数组，值表示该子数组和
注意 nums[i] 一定是有着最大和的连续子数组中的最后一个元素
2、确定递推公式
dp[i] 只有两个方向可以推出来：
- dp[i - 1] + nums[i]，即：nums[i] 加入当前以 nums[i-1] 为结尾的连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i])
3、dp 数组初始化
从递推公式可以看出来 dp[i] 是依赖于 dp[i - 1] 的状态，dp[0] 就是递推公式的基础
根据 dp 下标及值含义：dp[0] = nums[0]
4、确定遍历顺序
递推公式中 dp[i] 依赖于 dp[i - 1] 的状态，需要从前向后遍历，保证被依赖的 dp 值是已被更新后的正确值
5、打印 dp 数组验证
代码如下
class Solution {
public:int maxSubArray(vector<int>& nums) {// 确定dp数组下标及值含义：i表示以nums[i]为结尾的有最大和的子数组，dp[i]的值表示该最大子数组和vector<int> dp(nums.size());// 递推公式：要么将nums[i]加入具有最大和的子数组，要么从nums[i]重新开始统计具有最大和的子数组// 初始化dp[0]dp[0] = nums[0];// 从左向右遍历填充dpfor (int i = 1; i < nums.size(); ++i)dp[i] = max(dp[i - 1] + nums[i], nums[i]);return *max_element(dp.begin(), dp.end());}
};回顾一下 dp[i] 的定义：下标 i 表示以 nums[i] 为结尾的有最大和的连续子数组
那么我们要找有最大和的子数组，就应该找每一个 nums[i] 为终点的有最大和的子数组
回顾总结
操作两个序列需要二维 dp
还是定义 dp 数组是关键