1143.最长公共子序列
递推方程:
主要就是两大情况:
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]);
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;
}
else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[text1.size()][text2.size()];
}
};
1035.不相交的线
这题和上题几乎一样的。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
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()];
}
};
53. 最大子序和
贪心:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum=0;
int res=INT_MIN;
for(int i=0;i<nums.size();i++){
sum += nums[i];
if(sum>res){
res=sum;
}
if(sum < 0) sum=0;
}
return res;
}
};
dp:
这里要注意,我们需要保存遍历到当前的最大子序列之和。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size()<=1) return nums[0];
vector<int> dp(nums.size());
dp[0]=nums[0];
int res=nums[0];
for(int i=1;i<nums.size();i++){
dp[i]= max(nums[i],dp[i-1]+nums[i]);
if(dp[i] > res) res=dp[i];
}
return res;
}
};
392.判断子序列
这题和前两题几乎一样的。
else语句有两种写法:
dp[i][j] = dp[i][j - 1]; 这个写法还需要举例推导理解。
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
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] =max(dp[i][j-1],dp[i-1][j]);
//dp[i][j] =dp[i][j-1];
}
}
}
return dp[s.size()][t.size()] == s.size();
}
};