Reference: LeetCode
Difficulty: Medium

My Post: [Java] DP Solutions with Graphs!

## Problem

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:

## Analysis

### Brute-Force

Find the recurrence.

Time: $O(2^N)$ in the worst case when $T(N) = 2T(N - 1)$. In the best case, it is $O(N)$.
Space: $O(N)$

### DP (memoization)

Based on the brute-force solution, we found repeated calculation. We can use memoization to optimize the time complexity.

Time: $O(N^2)$
Space: $O(N^2)$

### DP (2D)

Define: We denote dp[i][j] as the longest palindromic subsequence’s length in the substring s(i, j).

Recurrence:

• If s[i] == s[j], then dp[i][j] = dp[i + 1][j - 1] + 2.
• Else, then dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).

Initialization: Check out the base cases in the brute-force solution.

Note: Determining ranges of i and j would be easy if you pick a starting point in the graph to get some intuition. For example, in this case j starts from i + 1.

Time: $O(N^2)$
Space: $O(N^2)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.