1143. 最长公共子序列

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int t1 = text1.size();int t2 = text2.size();vector<vector<int>> dp(t1+1, vector<int> (t2+1, 0));for(int i=1; i<t1+1; ++i){for(int j=1; j<t2+1; ++j){if(text1[i-1] == text2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = max(dp[i][j-1], dp[i-1][j]);}}}return dp[t1][t2];}
};

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()+1; ++i){for(int j=1; j<nums2.size()+1; ++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 out = *max_element(nums.begin(), nums.end());if(out<0){return out;}int startid = 0;while(startid<nums.size() && nums[startid]<0){startid++;}int dp_last = nums[startid];int sum_tmp = 0;int dp = out;for(int i=startid+1; i<nums.size(); ++i){if(nums[i]<0){sum_tmp += nums[i];}else{int tmp = dp_last + nums[i] + sum_tmp;dp = max(tmp, nums[i]);out = max(out, dp);sum_tmp = 0;dp_last = dp;}}return out;}
};

• 动规只考虑一个方向就可以了

392. 判断子序列

class Solution {
public:bool isSubsequence(string s, string t) {while(s.size()!=0 && t.size()!=0){if(t.back() == s.back()){s.pop_back();}t.pop_back();}return s.size()==0;}
};

• 投机省事要仔细