1143.最长公共子序列
这道题其实跟昨天晚上做的那道题很像。整体的框架我写出来了，但是我没有想明白怎么让后续的值延续当前的状态，也就是说如果这个数相等，那么后面的数是不是也应该遵循这个数的值。看了Carl的题解，才明白应该怎么延续整个值，其实就是dp[i][j] = max(dp[i][j-1],dp[i-1][j])，也就是说让目前两个数组不相等时所得到的二维数组的值为左边和上面的最大值，这样就把之前的状态延续下来了。
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][j-1],dp[i-1][j]);
}
}
}
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. 最大子序和 动态规划
这道题其实自己也没有想出来，但是看了一眼Carl的题解，然后就明白是怎么做了。
其实我觉得这道题用动态规划的解法来解和贪心算法的逻辑是基本上一样的。这里面有一点需要注意，就是一定要设一个result，它是用来储存最大值的。开始的时候我就没有加这个variable，所以问题就是最后遍历完之后，可能结果并不是最大的，最大的结果可能在遍历的途中出现了。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(),0);
dp[0] = nums[0];
int result = dp[0];
for(int i=1; i<nums.size(); i++){
dp[i] = max(nums[i],nums[i]+dp[i-1]);
if(dp[i] > result){
result = dp[i];
}
}
return result;
}
};
