Hi Han Qi. Thanks for reading! Great questions. I’ll answer them soon and will probably add them at the end of the article to help others as well.

Also, thanks for catching that typo in the function names. You’re right, it should be f_rec instead of f.

EDIT

Hi Han Qi. Apologize for keeping you waiting. I’ve answered your questions below!

Is there typo in dp_top_down.txt? The recursive call was typed as f rather than f_rec.

Nice catch. Fixed it!

How do you decide the order of calling multiple recursive splits? In this example you placed i+2 before i+1 in max(). Is it because i+2 reaches base cases earlier which helps i+1 calls return faster? Or order has no effect on runtime since every memoized function must and will only be calculated once no matter which recursive call calculated it?

Honestly, it doesn’t really matter. In fact, most programming languages don’t promise a fixed order of evaluating the arguments in something like function(arg1, arg2). But, assuming that is fixed, I don’t see any significant performance improvements. Regardless of which sub-tree you attempt first, you have to solve each sub-problem once (pre-computed values will be used in the future), so you end up doing the same work, albeit in a different order.

For DP, is the time complexity always simply the size of the array used to memoize? (eg. n for 1D, nxm for 2D). I frequently see the same argument of time complexity being time to fill up the memoization table

The time complexity for a top-down approach is a little harder to compute, and since both top-down and bottom-up approaches have the same complexity, its easier to calculate the latter’s. Since in bottom-up, we iterate over each element in our dp array and perform a constant time operation in each iteration, the time complexity is proportional to the number of iterations, which equals the size of our array.

In top-down + memoize you checked base case before checking memoization table. What if you swapped these order, would the code run faster because the memoize table can short-circuit and less base case checks are done?

You can do it either way if you can ensure that you won’t access something out of bounds. I did it this way to make it clear that we’re returning 0 when the current index is beyond our array. One way to do this could be to have a bigger dp array, say n+ 1 elements instead of n for our example. You can see that the largest index we’ll reach is equal to the size of our input array, so dp[index] would still be valid when index = size of input array, and you can return 0. It won’t make too much of a difference in terms of performance either way, since array access happens in constant time.

Is the constant space optimization only possible for bottom-up DP solutions and not top-down? Why yes/no?

I don’t think that’s possible. We’re able to optimize the bottom-up approach only because we noticed that to populate a particular element, we didn’t need every other element. In a top-down approach, though we technically only use the same elements in the bottom-up approach in a particular iteration, we need to recursively keep track of everything till we reach the base case and then solve everything on our way back up. We could store things on our way up, but that's exactly what the bottom-up approach does.

Does the solution also work if you DP the other direction through the array? Or more generally can DP always work in both directions? (at least i seen Multistage Graph forward/backward giving same answer)

Generally, yes. It doesn’t really matter which way you store the values, as long as you solve your sub-problems in the right order. Say you wanted to find the shortest path between source and destination. You could return dp[0][0] as the final answer, where dp[i][j] tells you how far the point (i, j) is from the destination. Conversely, you could return dp[m-1][n-1], the size of the grid being m x n, where dp[i][j] represents the distance from (i, j) and source. Regarding the direction of approach, that depends on the problem. For example, the example discussed in the article can be solved in either direction.

Let me know if you need further clarification or if you have any other questions. Thanks for your interest!