Leetcode - Longest Palindromic Subsequence

質問元:https://leetcode.com/problems/longest-palindromic-subsequence/

問題の説明

Given a string s, find the longest palindromic subsequence's length 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.

問題を解く

class Solution {
    
    static Integer [][] cache;
    public int longestPalindromeSubseq(String s) {
        
        cache = new Integer [s.length()][s.length()];
        int answer = findPalindrome(s, s.length() - 1, 0);
        return answer;
        
    }
    
    public static int findPalindrome(String s, int right, int left) {
        
        if(right == left)
            return 1;
        else if(right < left)
            return 0;
        
        if(cache[left][right] == null) {
        
            if(s.charAt(left) == s.charAt(right)) {
                cache[left][right] =  2 + findPalindrome(s, right - 1, left + 1);
            } else {
                cache[left][right] = Math.max(findPalindrome(s, right - 1 , left), findPalindrome(s, right, left + 1));
            }
        }
        return cache[left][right];
    }
}

解答方法
まず,文字列の前後インデックスにポインタを再帰的に作成して増減し,パリン症候群のアルゴリズムであるかどうかを確認することを考慮する.ただし,再帰関数のみを用いて実現すると,同様の演算が繰り返されるため,重複演算を除去するために注釈を再分割する必要があるため,結果は動的プランニング法を用いて解くべきである.
参考資料:https://ssminji.github.io/2020/02/05/the-cake-thief/