为什么最长的回文子序列需要DP解决方案？

Question

对于最长的回文子序列问题，已知最有效的方法是动态编程方法。这是来自LeetCode用户tankztc的递归DP解决方案：

public class Solution {
    public int longestPalindromeSubseq(String s) {
        return helper(s, 0, s.length() - 1, new Integer[s.length()][s.length()]);
    }

    private int helper(String s, int i, int j, Integer[][] memo) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (i > j)      return 0;
        if (i == j)     return 1;

        if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = helper(s, i + 1, j - 1, memo) + 2;
        } else {
            memo[i][j] = Math.max(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
        }
        return memo[i][j];
    }
}

这是没有DP的最简单的解决方案：

class Solution {
    public int longestPalindromeSubseq(String s) {
        if(s.length() == 0 || s.length() == 1) {
            return s.length(); 
        } else {
            if (s.charAt(0) == s.charAt(s.length()-1)) {
                return longestPalindromeSubseq(s.substring(1, s.length()-1))+2;
            } else {
                return Math.max(longestPalindromeSubseq(s.substring(1, s.length())), 
                                longestPalindromeSubseq(s.substring(0, s.length()-1)));
            }
        }
    }
}

我不明白为什么我们需要DP，因为我觉得上面的非DP解决方案不会在同一个子串上多次调用longestPalindromeSubseq()函数。什么时候memo[i][j] != null检查DP解决方案返回true？

Answer 1

在没有memoization的情况下，您将使用相同的参数多次计算此函数，因为递归树中的不同路径可以引导您使用相同的字符串参数。例如：

abcd -> abc -> bc
abcd -> bcd -> bc

没有记忆的算法的时间复杂度是指数的。