题目1:1143 最长公共子序列
题目链接:最长公共子序列
对题目的理解
返回两个字符串的最长公共子序列的长度,如果不存在公共子序列,返回0,注意返回的是最长公共子序列,与前一天的最后一道题不同的是子序列是可以不连续的
动态规划
动规五部曲
1)dp数组及下标i的含义
dp[i][j]:以[0,i-1]的nums1和以[0,j-1]的nums2的最长公共子序列的长度
2)递推公式
主要是两种情况,1)元素相同;2)元素不同
3)dp数组初始化
dp[i][0]和dp[0][j] 无意义,但是为了递推公式的需要,均初始化为0,其余下标位置处的数值初始化为任意值均可,但是为了方便起见,均初始化为0。
4)遍历顺序
根据递推公式,由左往右推导遍历,从上到下推导遍历。
5)打印dp数组
最终结果在dp[num1.size()][nums2.size()]
代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//定义并初始化dp数组
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;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[text1.size()][text2.size()];
}
};
- 时间复杂度: O(n * m),其中 n 和 m 分别为 text1 和 text2 的长度
- 空间复杂度: O(n * m)
题目2:1035 不相交的线
题目链接:不相交的线
对题目的理解
连接数组nums1和nums2中的相同数字代表的点,每条直线不能相交,计算最大连线数
直线不能相交,这就是说明在字符串A中找到一个与字符串B相同的子序列,且这个子序列不能改变相对顺序,只要相对顺序不改变,连接相同数字的直线就不会相交。
本题就是套了一层连线的外壳,代码与上一道题一模一样,就是找两个数组中存在的最大相同子序列的长度。
分析过程与上一道题一模一样
代码
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
//定义并初始化dp数组
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
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-1][j],dp[i][j-1]);
}
}
return dp[nums1.size()][nums2.size()];
}
};
- 时间复杂度: O(n * m)
- 空间复杂度: O(n * m)
题目3:53 最大子序和
题目链接:最大子序和
对题目的理解
找出具有最大和的连续子数组(至少包含一个元素),返回最大和,注意子数组是连续的
贪心算法
局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小;全局最优:选取最大“连续和”
不断调整最大子序和区间的起始位置,只要连续和还是正数就会对后面的元素起到增大总和的作用。 所以只要连续和为正数就保留。
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int count=0;//记录连续和
int result = INT_MIN;//记录最大连续和
for(int i=0;i<nums.size();i++){
count += nums[i];
if(count>result) result = count;
if(count<0) count = 0;//连续和为负数,重新计算连续和
}
return result;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)
动态规划
动规五部曲
1)dp数组及下标i的含义
dp[i]:以nums[i]结尾(包括nums[i])的最大连续子序列的和
2)递推公式
dp[i]可以从两个方向推导出来
1)延续前面的和:dp[i]=dp[i-1]+nums[i]
2)从nums[i]重新计算:dp[i]=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]
非0下标的dp数组,可以初始化为任意值,因为可以在后续计算中被覆盖,但是为了初始化方便,统一初始为nums[0]
4)遍历顺序
根据递推公式,dp[i]依赖于dp[i-1],从前往后遍历
for(i=1;i<nums.size();i++) 注意i从1开始遍历
5)打印dp数组
根据dp数组定义,最终结果不一定是dp[nums[i]-1],应该找每一个i为终点的连续最大子序列,需要把所有结果遍历一遍,求得最大值
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//定义并初始化dp数组
vector<int> dp(nums.size(),nums[0]);
int result = INT_MIN;
for(int i=1;i<nums.size();i++){
dp[i]=max(dp[i-1]+nums[i],nums[i]);
cout<<dp[i]<<endl;
result = max(result,dp[i]);
}
return result;
}
};
上述代码会出现如下的案例错误
错误的原因在于:result初始化为最小值,而for循环中计算的是dp[1],就是max(dp[0]+nums[1],nums[1]),是从数组中的第二个元素开始考虑的,如果这样的话,对于只有一个元素的数组根本就没有经过for循环,直接输出了result,所有result不能这样初始化,应该初始化为nums[0],即初始化为数组的第1个元素值,这样才能在数组只有1个元素的情况下,result考虑到第一个元素。
代码改正如下:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//定义并初始化dp数组
vector<int> dp(nums.size(),nums[0]);
int result = nums[0];
for(int i=1;i<nums.size();i++){
dp[i]=max(dp[i-1]+nums[i],nums[i]);
cout<<dp[i]<<endl;
result = max(result,dp[i]);
}
return result;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)