Day53 动态规划part14 1143. 最长公共子序列 1035. 不相交的线 53. 最大子数组和
Day53 动态规划part14 1143. 最长公共子序列 1035. 不相交的线 53. 最大子数组和
1143. 最长公共子序列
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));//长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]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)); //nums1.size()+1 * nums2.size()+1)矩阵，第一行和第一列初始化数值为默认值0for(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) { //贪心，一旦有0，重新找起点计数
// int result = INT32_MIN;
// int count = 0;
// for(int j = 0; j<nums.size();j++){
// count += nums[j];
// result = count > result ? count : result;
// count = count < 0 ? 0 :count;
// }
// return result;vector<int> dp(nums.size());if (dp.size()==0) return 0;dp[0] = nums[0];int result = dp[0];for(int i = 1; i<nums.size();i++){dp[i] = max(dp[i-1]+nums[i],nums[i]);result = (result>dp[i])?result:dp[i];}return result;}
};