leetcode上的题目
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入:"bbbab"
输出:4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:"cbbd"
输出: 2
一个可能的最长回文子序列为 "bb"。
降维后的动态规划，执行用时 :20 ms, 在所有 Java 提交中击败了88.84%的用户 内存消耗 :40.9 MB, 在所有 Java 提交中击败了96.52%的用户
class Solution { public int longestPalindromeSubseq(String s) { if (null == s || s.length() == 0) { return 0; } int len = s.length(); // 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] = dp[i+1][j] > dp[i][j-1] ? dp[i+1][j] : dp[i][j-1]; // // dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); // } // } // return dp[0][len-1]; int dp[] = new int[len]; int temp = 0; int pre = 0; for (int i=len-1; i>=0; --i) { dp[i] = 1; pre = 0; for (int j=i+1; j<len; ++j) { temp = dp[j]; dp[j] = s.charAt(i) == s.charAt(j) ? dp[j] = pre + 2 : Math.max(dp[j], dp[j-1]); pre = temp; } } return dp[len-1]; } }
原文：https://www.cnblogs.com/steve-jiang/p/12327270.html