大网站整站备份,免密码wifi万能连接,番禺人才网招聘网,织梦高端html5网站建设工作室网络公司网站模板1143.最长公共子序列
力扣题目链接/文章讲解
视频讲解
本题最大的难点还是定义 dp 数组
本题和718.最长重复子数组区别在于这里不要求是连续的了#xff0c;但要有相对顺序
直接动态规划五部曲#xff01;
1、确定 dp 数组下标及值含义
dp[i][j]#xff1a;取 text1…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) {vectorvectorint dp(text1.size() 1, vectorint(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]这两个子串的最长公共子序列的长度vectorvectorint dp(text1.size(), vectorint(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(vectorint nums1, vectorint nums2) {// dp[i][j]表示nums1[0, i]与nums2[0, j]这两个子数组的最长公共子序列的长度vectorvectorint dp(nums1.size(), vectorint(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(vectorint nums) {// 确定dp数组下标及值含义i表示以nums[i]为结尾的有最大和的子数组dp[i]的值表示该最大子数组和vectorint 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 数组是关键
