Why is DP solution needed for longest palindromic subsequence?

Question

For the longest palindromic subsequence problem, the most efficient way is known to be the dynamic programming approach. Here is a recursive DP solution from the LeetCode user tankztc:

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];
    }
}

And here is the simplest solution with no 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)));
            }
        }
    }
}

I don't understand why we need DP, because I feel like the non-DP solution above does not call the longestPalindromeSubseq() function on the same substring more than once. When would memo[i][j] != null check in the DP solution return true?

Answer 1

In the absence of memoization, you will compute this function many times with the same argument, because different paths in the recursion tree can lead you to the same string parameter. For example:

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

The time complexity of the algorithm without memoization is exponential.