516. Longest Palindromic Subsequence

Question

LeetCode Problem

Given a string s, return the length of the longest palindromic subsequence in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

Solutions

Use DP

• DP 定義：dp[i][j] 是字串範圍 [i, j] 內，最長的回文子序列長度。
• 遞推公式：
  • case 1: if i == j , then dp[i][j] = 1
  • case 2: if j - j > 0 and s[i] == s[j] then dp[i][j] = dp[i+1][j-1] + 2 else dp[i][j] = max(dp[i+1][j] , dp[i][j-1])

int longestPalidromeSubseq(string s) {
	int m = static_cast<int>(s.size());
	if (m == 0) return 0;
	vector<vector<int>> dp(m, vector<int>(m, 0));
	
	for (int i = 0; i < m; ++i) {
		dp[i][i] = 1;
	}
	
	for (int i = (m - 1); i >= 0; i--) {
		for (int j = i + 1; j < m; ++j) {
			if (s[i] == s[j]) {
				dp[i][j] = dp[i+1][j-1] + 2;
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
			}
		}
	}
	
	return dp[0][m-1];
}