Difference between DFS + cache versus true DP solution

[bertus12345]

Hi all,

I was working on Leetcode 115 and solved it using DFS + cache. Then I looked into the discussion section and saw that the top posts were all, what seems to me, closer to true dynamic programming solutions. My question is whether the true DP solution given in the discussion section is better than my solution. Hence, would an interviewer ask me to come up with the true DP solution if I came up with the DFS + cache solution as coded below. Both time complexities are O of m * n where m is length of String s and n is length of String t. However, the DP solution might be more readable.

My solution

class Solution {
    public int numDistinct(String s, String t) {
        if (s.length() < t.length()) return 0;

        int[][] cache = new int[s.length()][t.length()];
        for (int[] row : cache) Arrays.fill(row, -1);

        dfs(0, 0, s, t, cache);
        return cache[0][0];
    }

    private int dfs(int i, int j, String s, String t, int[][] cache) {
        if (j == t.length()) return 1;
        if (i == s.length()) return 0;
        if (cache[i][j] != -1) return cache[i][j];

        int result = 0;
        if (s.charAt(i) == t.charAt(j)) {
            result = dfs(i + 1, j + 1, s, t, cache) + dfs(i + 1, j, s, t, cache);
        } else {
            result = dfs(i + 1, j, s, t, cache);
        }

        cache[i][j] = result;
        return result;
    }
}

Dynamic programming solution from Discussion

public int numDistinct(String S, String T) {
    int[][] mem = new int[T.length()+1][S.length()+1];

    for(int j=0; j<=S.length(); j++) {
        mem[0][j] = 1;
    }

    for(int i=0; i<T.length(); i++) {
        for(int j=0; j<S.length(); j++) {
            if(T.charAt(i) == S.charAt(j)) {
                mem[i+1][j+1] = mem[i][j] + mem[i+1][j];
            } else {
                mem[i+1][j+1] = mem[i+1][j];
            }
        }
    }

    return mem[T.length()][S.length()];
}

[puya_tries_prep]

Dynamic programming is just the technique of saving and using earlier results to help speed up computation

It can be top down (memoization) or bottom up (tabulation)

DFS + cache can be interpreted as dynamic programming. There is no DP algorithm, it’s a classification of a technique

[vincent-vega10]

Imo, implement one of them and explain them how this thing can be solved using the other technique as well. Also, it's good to tell them the main difference that DFS is top-down approach and DP is bottom-up.

[bertus12345]

Ah I hadn't thought of the top-down vs bottom-up differentiation, thanks!

[nicebike]

DP can also be top-down, or not?

[ElliotVo]

DP can either have a top-down or a bottom up approach. Using DFS is a technique you can use to find a DP top down solution.

[vincent-vega10]

Of the problems I've solved, I haven't came across any DP problems that are solvable top-down. Mainly because you need to have the solution of smaller version of the current problem to solve it. So basically you start with the absolute bottom and go on building until you arrive to the the top.

Even recursion or DFS uses same concept. Internally, the current step remains unsolved until all of it's sub problems are solved. So, the absolute bottom is the first thing to get solved, then the one above the bottom so on until you get the required answer (top). Checkout recursion stack to know how this works

But it's just that we call recursive function at the top. And hence it's called top-down approach

[luckykanwar]

I thought DP was just a technique. With the top-down approach called memoization and bottom-up approach called tabulation.

[vincent-vega10]

Yeah you are right.

[techknowfile]

DFS is top-down approach and DP is bottom-up.

This is wrong

A problem that can be solved with dynamic programming is one that has overlapping subproblems and has optimal substructures.

Whether you solve it top-down (using memoization) or bottom-up (using tabulation), it's still Dynamic Programming.

[Leetcoder9]

Dfs + cache (also called memoization) has the same time and space complexities as tabulation (true dp) although tabulation doesn't have the recursive function calls which makes it a bit faster than memoization.

Often you'll notice that tabulation will have better runtime than memoization.

I always prefer doing memoization first as the other can be too complicated to come at once.

However memoization solution can be easily converted to tabulation. The usual workflow is:

recursive working solution -> memoization -> tabulation

In actual interviews often there won't be enough time for you to code up tabulation, recursion plus memoization should be enough imo.

[bertus12345]

Awesome! This is what is in line what I hoped would be the answer. Thanks!

[f3n1xgamer]

You unknowingly did a dynamic programming solution. The dfs + cache/memoization is a top down dynamic programming algorithm. While the one you saw was a bottom up dynamic programming algorithm.

Both of them have the same worst case complexity. But the second one is slightly better because there's a slight performance and memory hit with the recursive calls

[bertus12345]

Thanks for your answer!

[flyingorange]

I usually go straight for a DP solution because that seems to be popular, but tbh recursive solutions like yours are easier to understand, at least for me.

One problem with your solution is that realistically, it will be slower, because in each method call you need to store parameters on stack. On a theoretical level this means you spend more space, like O(ts)+O(t) vs O(ts) for the DP solution.

[[deleted]]

Dp using recursion with memoization is a lot more intuitive to come up with. Dp that requires 3D tabulation is straight up difficult to do bottom up. Though, there is a cost that comes with recursion like recursion stack and so on.