最长公共子序列
leetcode:1143. 最长公共子序列
动态规划
思路
和最长重复子序列很像,但是这个不要求连续。
意义略有不同,因此result不需要找最大值,直接就是最末的dp元素。
代码实现
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
// 0~i-1和0~j-1子串的最长公共子序列为dp[i][j]
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]);
// cout<<dp[i][j]<<' ';
}
// cout<<endl;
}
return dp[text1.size()][text2.size()];
}
};
不相交的线
leetcode: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()];
}
};
最大子序和
leetcode:53. 最大子数组和
动态规划
思路
类似贪心法(如果累和为负数,从下一个开始重新计算累和),
比较之前的累和加上当前元素
&当前元素自身
比谁大(如果累和为负数,则舍弃当前元素)。
代码实现
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// if(nums.size() == 1) return nums[0];
// 以nums[i]结尾的最大连续子数组和为dp[i]
vector<int> dp(nums.size(),0);
dp[0] = nums[0];
int result = nums[0];
for(int i = 1;i < nums.size();i++){
dp[i] = max(dp[i-1] + nums[i],nums[i]);
if(dp[i] > result) result = dp[i];
}
return result;
}
};
标签:nums,int,53,60,vector,result,子序,dp,size
From: https://www.cnblogs.com/tazdingo/p/18102129