1143.最长公共子序列

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector> dp(text1.size()+1,vector(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-1][j],dp[i][j-1]);}}return dp[text1.size()][text2.size()];}
};

此题要求是有序的（数组中的相对位置）。如果不要求有序，那么我觉得用一个nums[27]数组，来记录重叠的个数，比使用哈希表要快。

1035.不相交的线

此题和 1143.最长公共子序列  一模一样

53. 最大子序和 (动态规划实现)

此解法有三个巧妙之处：

第一，将dp[i]定义为包含第i个数字的最大子数组和，如此一来可以十分顺利的写出dp数组的递推公式；

第二，由于最大自序和不一定是包含最后一位的和，也就是不一定是dp[nums.size()-1]，所以在每次遍历都需重新判断一下调整之后的dp[i]是不是最大值；

第三，当nums.size() ==1时，程序无法进入循环，如果把res=0就会报错，所以把res设置为nums[0]。

class Solution {
public:int maxSubArray(vector& nums) {if(nums.size()==0) return 0;vector dp(nums.size(),0);int res = nums[0];dp[0] = nums[0];for(int i=1;i res) res = dp[i];//使用res保存最大的dp值}return res;}
};