[Leetcode] DP-- 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:

One possible longest palindromic subsequence is "bbbb".

Example 2:
Input:

"cbbd"

Output:

One possible longest palindromic subsequence is "bb".

Solution:

Similar to question 5. longest palindromic subtring

but the difference is here it is subsequences.

1. use DP:

denote longest palindromic subtring as LPS

(1) Define the subproblem

dp[i][j] is the LPS length from index i to j in input string s

(2) Find the recursion (state transition function)

$dp[i][j] = left{egin{matrix}

dp[i+1][j-1] + 2 & if hspace{0.2cm} s[i] == s[j]\

max(dp[i+1][j], dp[i][j-1]) & if hspace{0.2cm} s[i] !=s[j]

end{matrix} ight.$

dp[i + 1][j - 1] + 2 if (s[i] == s[j])

dp[i][j] =

max(dp[i + 1][j], dp[i][j - 1]) if (s[i] != s[j])

(3) Get the base case

dp[i][i] = 1 for i from 0 to n-1

the first iteration should be traversed from back to first

 1  n = len(s)
 2         dp = [[0]*n for i in range(n)]
 3         
 4         #print ("dp: ", dp)
 5         
 6         for i in range(n-1, -1, -1):
 7             dp[i][i] = 1
 8             for j in range(i+1, n, 1):
 9                 if s[i] == s[j]:
10                     dp[i][j] = dp[i+1][j-1] + 2
11                 else:
12                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 
13         return dp[0][n-1]

TLE problem for two dimension. why?

further tranferred to one dimension of space. time complexity is still the same. but space complexity is reduce to o(n) now. Why it does not have TLE?

#2. transferrred to one dimension
        n = len(s)
        dp = [1] * n
        
        #print ("dp: ", dp)
        
        for i in range(n-1, -1, -1):
            dpLen = 0
            for j in range(i+1, n, 1):
                if s[i] == s[j]:
                    dp[j] = dpLen + 2
                else:
                    dpLen = max(dp[j], dpLen)
        return max(dp)