在阅读下面的题目之前，首先需要确定的是，求子序列还是子串，子串需要是连续的，子序列无需连续，比如“Hello”,子串可以是Hel, llo, lo等，子序列可以是Hlo, Heo.
下面步入正题：
516. 最长回文子序列
解题思路：
我们定义 dp[i][j] 表示从索引i到索引j最长的回文子序列，最后我们需要求的是dp[0][len]从0到len-1下标的最大回文串长度，显然当dp[i][i]为1，当只有一个字符串的时候，假设已知dp[i+1][j-1]的大小，我们需要确定更外层的大小，也就是dp[i][j]取决于s[i]和s[j]是否相等，如果相等，dp[i][j] = dp[i+1][j-1]+2;否则取决于 dp[i+1][j], dp[i][j-1]最大值。
class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();if(len == 0) return 0;int[][]dp = new int[len][len];for(int i = len-1; i>=0; i--){dp[i][i] = 1;for(int j = i+1; j<len; j++){if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1]+2;else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}return dp[0][len-1];}}
这里有个问题，dp[i+1][j-1]中j-1 < i+1这种情况，这里需要注意的是，因为默认dp[i][j] && i>j的情况全为0，所以并不影响结果
最长回文子串
这个题目大概是我提交次数最多的一个题目，总是出各种各样的小毛病，需要做一个小总结：
class Solution {public String longestPalindrome(String s) {int len = s.length();if(len <= 1) return s;char[] ch = s.toCharArray();boolean[][] dp = new boolean[len][len];for(int i = 0; i<len; i++) dp[i][i] = true;int maxlen = 1; // 注意 "ad"这种情况如果不设置为1，会返回空串，实际上返回 a,d都行int start = 0;for(int i = len-1; i>=0; i--){for(int j = i+1; j<len; j++){if(ch[i] == ch[j]) {if(j-i < 3) dp[i][j] = true;else dp[i][j] = dp[i+1][j-1];}else dp[i][j] = false;if(dp[i][j] && j-i+1 > maxlen){start = i;maxlen = j-i+1;}}}return s.substring(start, start+maxlen);}}
这里if(j-i < 3) dp[i][j] = true;这段是因为 “aba”, “aa” 这种情况考虑的
最长公共子序列：
dp[i][j] 表示
class Solution {public int longestCommonSubsequence(String text1, String text2) {int len1 = text1.length();int len2 = text2.length();if(len1 * len2 == 0) return 0;int[][]dp = new int[len1+1][len2+1];for(int i = 1; i<=len1; i++){for(int j = 1; j<=len2; j++){if(text1.charAt(i-1) == text2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);}}return dp[len1][len2];}}
进阶 输出最长子序列
public String LCS (String s1, String s2) {// write code hereint len1 = s1.length();int len2 = s2.length();char[] ss1 = s1.toCharArray();char[] ss2 = s2.toCharArray();String[][] dp = new String[len1+1][len2+1];for(int i = 0; i<=len1; i++) dp[i][0] = "";for(int i = 0; i<=len2; i++) dp[0][i] = "";for(int i = 1; i<=len1; i++){for(int j = 1; j<=len2; j++){if(ss1[i-1] == ss2[j-1]) dp[i][j] = dp[i-1][j-1]+ss2[j-1];else dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ? dp[i-1][j]:dp[i][j-1];}}return dp[len1][len2] == "" ? "-1":dp[len1][len2];}
最长公共子串：
class Solution {public int findLength(int[] A, int[] B) {int len1 = A.length;int len2 = B.length;if(len1 * len2 == 0) return 0;int[][]dp = new int[len1+1][len2+1];int res = 0;for(int i = 1; i<=len1; i++){for(int j = 1; j<=len2; j++){if(A[i-1] == B[j-1]) {dp[i][j] = dp[i-1][j-1]+1;}elsedp[i][j] = 0;res = Math.max(res, dp[i][j]);}}return res;}}
观察以上几个题目，可以得出结论，子串和子序列的处理，主要是体现在A[i-1] != B[j-1]这种情况下的处理，子串的话，置零，子序列的话，取最大。
如果觉得《总结几个字符串类的动态规划（最长公共子串 回文子串 子序列）》对你有帮助，请点赞、收藏，并留下你的观点哦！
