516. Longest Palindromic Subsequence

516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1: Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is “bbbb”. Example 2: Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is “bb”.

思路： 这是一个动态规划的题目，对于动态规划的题目，我们首先要明确这个大问题如何用子问题来表示，然后分情况写出动态规划的递归表达式，这样编程实现就简单多了。 1、子问题的解如何表达？ 给定一个字符串，把它划分成什么样的子问题呢？通过分析我们发现，这样的子问题是：任意一个该字符串的子串包含的回文串的长度，那么对于这个字符串的子串，我们可以用它在原字符串中的起始位置和结束位置来表示。因此，我们可以用一个二维数组来对子问题进行表示，dp[i][j]表示he longest palindromic subsequence’s length of substring(i, j)。 2、大问题如何用子问题来表示？

Initialization: dp[i][i] = 1if s.charAt(i) == s.charAt(j) dp[i][j] = dp[i+1][j-1] + 2otherwise dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])

class Solution { public int longestPalindromeSubseq(String s) { return helper(s, 0, s.length() - 1, new int[s.length()][s.length()]); } private int helper(String s, int i, int j, int[][] memo) { if (memo[i][j] != 0) { return memo[i][j]; } if (i > j) return 0; if (i == j) return 1; if (s.charAt(i) == s.charAt(j)) { memo[i][j] = helper(s, i + 1, j - 1, memo) + 2; } else { memo[i][j] = Math.max(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo)); } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。