1143. 最长公共子序列
思路：
dp[i][j]：以0~i-1和0~j-1位置中最长公共子序列的长度为dp[i][j]。递推关系：如果nums1[i-1]与nums2[i-1]相等的话，dp[i][j]=dp[i-1][j-1]+1,如果二者不相等，可能是nums1[i-1]==nums2[j-2],也可能是nums1[i-2]==nums2[j-1]，所以dp[i][j]=max(dp[i][j-1],dp[i-1][j])。初始化：由dp[i][j]的定义可以知道dp[i][0]、dp[0][j]都应该初始化为0。遍历顺序：从小到大，从前向后。
代码：
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. 最大子数组和
思路：
dp[i]:下标为i的最大子数组的和为dp[i]（包含第i位元素）。递推关系：如果该位置的元素大于0，则为dp[i-1]+nums[i]，如果该位的元素小于0，则应该不加上这一位，但是子数组要保持数组的连续性，所以这里应该从头开始，所以dp[i]=max(dp[i-1]+nums[i],nums[i])。初始化：dp[0]=nums[0]。遍历关系：从小到大。
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len=nums.size();
if(len==0)return 0;
vector<int> dp(len,0);
dp[0]=nums[0];
int res=dp[0];
for(int i=1;i<len;i++)
{
dp[i]=max(dp[i-1]+nums[i],nums[i]);
if(res<dp[i]) res=dp[i];
}
return res;
}
};
