516. Longest Palindromic Subsequence

TC: O(n^2)
SC: O(n^2)

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
}
/*

Longest Palindromic Subsequence


dp[i][j]: Longest Palindromic Subsequence for s[i:j]

i xxxxxx 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])


s[i] != s[j] so we can't have i, j at the same time
[       ]
i xxxxxx j
  [      ]
  
base case, if i == j , value is 1 (only one character)
if (i < j ) value is all 0

[i, j-1]   [i,j]
[i+1, j-1] [i+1, j]

      j
      -> ->
   1  x. x  ^
i  0  1  x  |
   0  0  1   for right buttom to exe

TC: O(n^2)
SC: O(n^2)

*/

DFS + MEMO

```java
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        Integer[][] memo = new Integer[n][n];
        return dfs(0, n-1, s, memo);
    }
    private int dfs(int i, int j, String s, Integer[][] memo) {
        if (i > j) {
            return 0;
        }
        if (i == j) { // when s = "a"
            return 1;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (s.charAt(i) == s.charAt(j)) {
            return memo[i][j] = dfs(i+1, j-1, s, memo) + 2;
        } else {
            return memo[i][j] = Math.max(dfs(i+1, j, s, memo), dfs(i, j-1, s, memo));
        }
    }
}

/*
begin and end same -> 

b bba b

dfs(bbbab)
same -> dfs(bba) + 2 ...

dfs(cbbd)
not same  -> max(dfs(bbd), dfs(cbb)) ...

if s[0] == s[n] -> dfs(i+1, j-1) + 2
if s[0] != s[n] -> max(dfs(i+1, j) , dfs(i, j-1))

T: O(n^2)
T: O(n^2)
*/
```