java - 为什么最长回文子序列需要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

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

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

没有内存的算法的时间复杂度是指数级的。