What to memoize in Dynamic programming questions?

Question

How do you know what to memoize in top-down Dynamic Programming problems?

I understand it is to do with capturing the permutations of state. E.g. in the Fibonacci numbers question, it’s memoizing the Fibonacci sequence fib(8) = 21. I understand that; it’s a pure function and input results to output.

However, with more difficult Dynamic Programming problems, what to memoize isn’t that obvious, because it seems to me that it usually requires the previous state.

For example, for 474. Ones and Zeros:

https://leetcode.com/problems/ones-and-zeroes/description/

You should memoize the m and n and current index.

But surely at any given index and m and n, it would be different depending on the previous values (it gets all added together)? Say you are on index 300, with m being 50 and n being 20, the memoized answer will really depend on the previous value

To me it’s like saying I want to get to Starbucks, but oh, you are facing left, so you should turn right and go forward. This is not true, as you’d need to know your accumulated current position

Please advise.

Answer 1

Memoization is an optimization, not a solution.

what to memoize isn’t that obvious

Write the solution first, and then memoize whatever you redundantly compute more than once. Trying to skip the naive recursion and go straight to the memoized version is probably a false economy.

---

For your linked problem, write a naive recursive solution first, (without @lru_cache or whatever) and just see what argument->result pairs recur, and could have been memoized. Print them out and watch it go. Then apply optimizations after you understand what is being computed and how it works.

Answer 2

For the ones and zeros problem, the original problem has one answer. There is a one size of the largest subset of strs using at most m 0's and n 1's.

The memoized results are for the same problem, only with smaller values for each parameter. It's like asking what if we had fewer 0's, or fewer 1's to use.

Smaller values of strs here would be if we could couldn't use the last element, or last two elements and so on. So the memoized value of (currentIndex, m, n) would be the size of the largest subset of strs using any elements from index 0 to currentIndex, and at most m 0's and n 1's. This includes the previous values by being the largest possible subset using any of the previous values.