[LeetCode] 516. Longest Palindromic Subsequence

😎풀이

1. s[i] ~ s[j]로 가능한 팰린드롬 최대 길이를 저장하는 DP 배열 생성
2. s[i]를 위해 s[i + 1]을 활용해야 하므로 역순회구조
3. 두 포인트의 문자가 동일한 경우, 이전 문자열에서 양쪽을 더한 값이 최대 팰린드롬 길이
4. 두 포인트 문자가 상이한 경우, 이전 문자 중 더 긴 팰린드롬을 갖는 문자열의 길이
5. s의 모든 문자를 활용해 만들 수 있는 최대 팰린드롬 부분문자열의 길이

function longestPalindromeSubseq(s: string): number {
    const n = s.length
    const dp = Array.from({ length: n }, () => Array(n).fill(0))
    for(let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1
        for(let j = i + 1; j < n; j++) {
            if(s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[0][n - 1]
};