LeetCode 516. Longest Palindromic Subsequence

本文主要是介绍LeetCode 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”.

思路： 利用动态规划，dp[i][i]初始值都为1，如果s[i]和s[j]相等，那么分别索引向中间靠，为dp[i+1][j-1]+2，否则就为dp[i+1][j]和dp[i][j-1]中大的那个。最终结果就是返回索引为0到len-1区间内，回文序列最长的值。

代码：

class Solution {
public:int longestPalindromeSubseq(string s) {int len = s.length();int **dp = new int*[len];//给dp分配一个len*len大小的空间for (int i = 0; i < len; ++i){dp[i] = new int[len]();}for (int i = len - 1; i >= 0; i--) {dp[i][i] = 1;//dp[i][i]初始值都为1for (int j = i + 1; j < len; j++) {if (s[i] == s[j]) {//如果s[i]和s[j]相等，那么分别索引向中间靠，为dp[i+1][j-1]+2dp[i][j] = dp[i + 1][j - 1] + 2;}else {//否则就为dp[i+1][j]和dp[i][j-1]中大的那个dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][len - 1];//返回索引为0到len-1区间内，回文序列最长的值}
};

结果： 56ms

这篇关于LeetCode 516. Longest Palindromic Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---