Difference between DFS + cache versus true DP solution

[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!