LeetCode1143. 最长公共子序列
题目链接：1143. 最长公共子序列
独上高楼，望尽天涯路
和之前那道题思路又不太一样了，第一次接触还是挺难想出来的。
慕然回首，灯火阑珊处
首先是dp数组以及下标的含义。
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列长度为dp[i][j]。
然后是确定递推公式。
主要就是两大情况： 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[i - 2]与text2[j - 1]的最长公共子序列和 text1[i - 1]与text2[j - 2]的最长公共子序列，取最大的。
这种解题思路只能多做，多见，多积累。
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() + 1; i++) {
for (int j = 1; j < text2.size() + 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 - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.size()][text2.size()];
}
};
LeetCode1035. 不相交的线
题目链接：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()];
}
};
LeetCode53. 最大子序和
题目链接：53. 最大子序和
独上高楼，望尽天涯路
这次思路想对了一半，没有接着想下去，感觉还是没有到开窍的那个点。
慕然回首，灯火阑珊处
首先是确定dp数组以及下标的含义。
dp[i]：以nums[i]为结尾的最大连续子序列和为dp[i]。
为了通过dp[i-1] + nums[i]推导出dp[i]，所以一定是要以nums[i]为结尾，同时应该想到答案需要用result变量在遍历过程中获得。
然后是确实递推公式。
dp[i]只有两个方向可以推出来：
- dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
这里不需要去考虑nums[i]的正负，因为限制条件是nums[i]为结尾，所以必须带着nums[i]；需要考虑的是要不要带着dp[i-1]，即之前的最大连续子序列和，用max来做决定，最后要最大的那个就行了。
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(dp[i - 1] + nums[i], nums[i]);
if (result < dp[i]) {
result = dp[i];
}
}
return result;
}
};