剑指 Offer 42. 连续子数组的最大和 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 提示： 1 <= arr.length <= 10^5 -100 <= arr[i] <= 100
分析： 1.dp[i]:以nums[i]作为结尾的最大连续序列和 2.dp[i] = max(dp[i-1]+nums[i],nums[i]) 看当前元素加在上一个最大序列之后得到的和大，还是将当前元素作为一个新的开始得到的和大。 3.比较所有元素作为结尾得到的连续子数组和的大小。 4.初始化：因为至少选择数组中的一个数，所以当只有一个元素时，最大和就是元素的值，dp[0] = nums[0]。
class Solution { public: int maxSubArray(vector<int>& nums) { vector<int>dp(nums.size(),0); dp[0] = nums[0]; int ans = dp[0]; for(int i=1;i<nums.size();i++){ dp[i] = max(nums[i],dp[i-1]+nums[i]); ans = max(ans,dp[i]); } return ans; } };300. 最长上升子序列 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明: 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
子序列：可以不连续 连续子序列：连续的
分析： 1.dp[i]:以nums[i]作为结尾的最长上升子序列长度 2.假设现在已知dp[0]…dp[i-1] 分别以nums[0]…nums[i-1]作为结尾的最长上升子序列长度，如果想要在加入nums[i]后依然是最长上升子序列，就需要判断两个条件:nums[i]是否大于nums[j],nums[i]加在哪个序列后才能得到最长。 dp[i] = max(dp[0]+1,…,dp[j]+1,…,dp[i-1]+1,1)（nums[j]<nums[i]） 同时考虑到nums[i]有可能小于前面所有的元素，所以它自己作为一个序列，也就是序列长度为1.
class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int>dp(nums.size(),0); int res = 0; for(int i=0;i<nums.size();i++){ dp[i] = 1; for(int j =0;j<i;j++){ if(nums[i]>nums[j]) dp[i] = max(dp[i],dp[j]+1); } res = max(res,dp[i]); } return res; } };1143. 最长公共子序列 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。 若这两个字符串没有公共子序列，则返回 0。 示例 1: 输入：text1 = “abcde”, text2 = “ace” 输出：3 解释：最长公共子序列是 “ace”，它的长度为 3。 示例 2: 输入：text1 = “abc”, text2 = “abc” 输出：3 解释：最长公共子序列是 “abc”，它的长度为 3。 示例 3: 输入：text1 = “abc”, text2 = “def” 输出：0 解释：两个字符串没有公共子序列，返回 0。 提示: 1 <= text1.length <= 1000 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。
分析： 1.dp[i][j]:以text1[i]，text2[j]分别为结尾的序列的最长公共子序列长度。 2.转移方程 3.初始状态：需要注意的是text1[0]和text2[j]的最长公共子序列长度只能是1，也就是说text1[0]和text2[j]相同时，dp[0][j] =1,不同时dp[0][j]=dp[0][j-1]。dp[i][0]同理。
class Solution { public: int longestCommonSubsequence(string text1, string text2) { //dp[i][j]:以text[i] text[j]作为结尾的最长公共子序列长度 int m = text1.size(),n=text2.size(); int dp[m][n]; memset(dp,0,sizeof(dp)); if(text1[0]==text2[0])dp[0][0] =1; int res = dp[0][0]; for(int i=1;i<n;i++){ if(text1[0]==text2[i]) dp[0][i] = 1; else dp[0][i] = dp[0][i-1]; res = max(res,dp[0][i]); } for(int i=1;i<m;i++){ if(text1[i]==text2[0]) dp[i][0] = 1; else dp[i][0] = dp[i-1][0]; res = max(res,dp[i][0]); } for(int i=1;i<m;i++){ for(int j = 1;j<n;j++){ if(text1[i]==text2[j]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]); res = max(res,dp[i][j]); } } return res; } };516. 最长回文子序列 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。 示例 1: 输入: “bbbab” 输出: 4 一个可能的最长回文子序列为 “bbbb”。 示例 2: 输入: “cbbd” 输出: 2 一个可能的最长回文子序列为 “bb”。 提示： 1 <= s.length <= 1000 s 只包含小写英文字母
1.dp[i][j]:以s[i]作为开头，s[j]作为结尾的序列中包含的最长回文子序列长度 *Note：这里的dp[i][j]是指想要求的回文序列包含在是s[i…j]里面的，而不是回文序列就是s[i…j]。而最大连续子序列和最长上升子序列的dp[i]都是A[i]一定在目标序列中。要注意区别。 2.转移方程 3.初始化：单个字母也是回文，所以对角线上的元素为1。而且作为开头的字母在序列中给的下标应该小于结尾的下标，所以矩阵应该是一个上三角矩阵，下三角的部分都初始化为0。 4.计算顺序：从下到上，从左到右。
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); int dp[n][n];//dp[i][j]:以s[i]作为开头，s[j]作为结尾的序列中包含的最长回文子序列长度 memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++){ dp[i][i] = 1; } for(int i=n-1;i>=0;i--){ for(int j=i+1;j<n;j++){ if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1]+2; else dp[i][j] = max(dp[i+1][j],dp[i][j-1]); } } return dp[0][n-1]; } };5. 最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2： 输入: “cbbd” 输出: “bb”
这个题和上个题的区别在于，一个是求最长回文串长度一个是求最长回文串，在思路上是一脉相承的。只要在每次比较最长回文长度时，记录下起始位置和长度即可。 1.dp[i][j]：s[i.j]是否是一个回文串。 2. 3.单个字符和两个字符时都可以直接判断，所以初始化不仅要初始化对角线上的，还要初始化（i，i+1）位置上的。 4.计算顺序同上题。
class Solution { public: string longestPalindrome(string s) { if(s.size()==0)return ""; int n = s.size(); int dp[n][n]; memset(dp,0,sizeof(dp)); int len =0,start; for(int i=0;i<n;i++){ dp[i][i] = 1; if(i!=n-1&&s[i]==s[i+1]){ dp[i][i+1] = 1; } if(dp[i][i]==1&&1>len){ len = 1; start = i; } if(i!=n-1&&dp[i][i+1]==1&&2>len){ len = 2; start = i; } } for(int i=n-1;i>=0;i--){ for(int j =i+2;j<n;j++){ if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1]; if(dp[i][j]==1&&j-i+1>len){ len = j-i+1; start = i; } } } return s.substr(start,len); } };*Note:substr（）的用法是传入起始位置和截取长度。
139. 单词拆分 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。 示例 2： 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。 示例 3： 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false
1.dp[i]:到第i个字母构成的序列是否满足条件 2.dp[i]=dp[j]&&（s[j+1…i]在单词表中） 3.j代表的含义就是分割序列的位置，j及其之前的序列是否符合条件由上一轮计算得到，所以i是对字符串s的遍历，而j是枚举可能的分割点。 需要注意的是： i)当已经找到一个合适的分割使dp[i]等于1，就不用再往下循环了，不然就会覆盖正确答案。 ii)j应该小于i，而不是等于i结束内层循环，j=i时需要判断的字符串就是空的，没有必要。 4.初始化：dp[0] = true，dp[0]代表的并不是下标为0的字符是否满足条件，而是一个字符都没有的情况。dp[i]中的i比字符串下标多1，也就是说dp[i]对应的是s[0…i-1]，需要判断的是s[j…i-1]。
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { map<string,int>mp; for(int i=0;i<wordDict.size();i++){ mp[wordDict[i]] = 1; } vector<bool>dp(s.size()+1);//dp[i]:到第i个字母的序列是否满足条件 dp[0]= true; for(int i=1;i<=s.size();i++){ for(int j =0;j<i;j++){ dp[i] = (dp[j]&&mp[s.substr(j,i-j)]==1)?true:false;//j是分割点 if(dp[i]==1)break; //cout<<i<<" "<<j<<" "<<s.substr(j,i-j)<<" "<<dp[i]<<endl; } } return dp[s.size()]; } };