1143.最长公共子序列
体会一下本题和 718. 最长重复子数组 的区别
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ
https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
Tips：
继续动规五部曲分析如下：
- 确定dp数组（dp table）以及下标的含义
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
有同学会问：为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？
这样定义是为了后面代码实现方便，如果非要定义为长度为[0, i]的字符串text1也可以，我在 动态规划：718. 最长重复子数组 (opens new window)中的「拓展」里 详细讲解了区别所在，其实就是简化了dp数组第一行和第一列的初始化逻辑。
- 确定递推公式
主要就是两大情况： 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 - 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]);
}- dp数组如何初始化
先看看dp[i][0]应该是多少呢？
test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;
同理dp[0][j]也是0。
其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。
代码：
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));- 确定遍历顺序
从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图：
那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。
- 举例推导dp数组
以输入：text1 = "abcde", text2 = "ace" 为例，dp状态如图：
最后红框dp[text1.size()][text2.size()]为最终结果
我的题解：
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
int result = INT_MIN;
for(int i = 1; i<=text1.size();i++){
for(int j = 1; j<=text2.size();j++){
// 这种写法会超时
// if(text1[i-1]==text2[j-1]){
// int tempMax = INT_MIN;
// for(int m = 0; m<i;m++){
// for(int n = 0; n<j;n++){
// tempMax = max(tempMax,dp[m][n]);
// }
// }
// dp[i][j] = max(dp[i][j],tempMax+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]);
}
result = max(result,dp[i][j]);
}
}
return result;
}
};1035.不相交的线
其实本题和 1143.最长公共子序列 是一模一样的，大家尝试自己做一做。
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP
https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
Tips：
我的题解：
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
// 其实就是最大公共子序列
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
int result = INT_MIN;
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] = max(dp[i][j-1],dp[i-1][j]);
}
result = max(result,dp[i][j]);
}
}
return result;
}
};53. 最大子序和
这道题我们用贪心做过，这次 再用dp来做一遍
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5
Tips：
动规五部曲如下：
- 确定dp数组（dp table）以及下标的含义
dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
- 确定递推公式
dp[i]只有两个方向可以推出来：
- dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
- dp数组如何初始化
从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
dp[0]应该是多少呢?
根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。
- 确定遍历顺序
递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
- 举例推导dp数组
以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。
在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。
那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。
所以在递推公式的时候，可以直接选出最大的dp[i]。
我的题解：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 动规版本的答案
vector<int> dp(nums.size(),0);
int result = nums[0];
dp[0] = nums[0];
for(int i = 1;i < nums.size();i++){
dp[i] = max(dp[i-1] + nums[i], nums[i]);
result = max(result,dp[i]);
}
return result;
}
};标签：1143,nums,E5%,53,text2,text1,子序,dp,size From： https://www.cnblogs.com/GavinGYM/p/17147932.html