ZeroToHero123's blog

By ZeroToHero123, history, 5 weeks ago, In English

I have a problem in understanding and imagining the bottom up approach in dynamic programming, for a long time I have been solving the dp problems using the memomization method and every thing was going well, but last days I faced a problems that needs an iterative approach in order to avoid the stack overflow exception, so I tried to implement the top down approach ( just like how the recursion works) and after sometime I became good in it. Now the problem is with some hard problems that I wasn't able to solve them using the top-down approach, so my friends advised me to use the bottom up one, after reading about it I was unable to imagine how it will work at all, so I read a lot of tutorials without any benefit. Can you please offer me some tutorials or videos to learn how to imagine this approach from them, because this topic made me hate the competitive programming.

  • Vote: I like it
  • +8
  • Vote: I do not like it

5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ZeroToHero123 (previous revision, new revision, compare).

5 weeks ago, # |
Rev. 2   Vote: I like it +59 Vote: I do not like it

When I first learnt DP, I learnt it the bottom-up way, so I'll explain what helped for me (might not work for others).

What you should realize is that DP is nothing but memoized recursion, as you have already mentioned, AND the fact that the way you prove recursion is via mathematical induction.

Induction is fundamentally top-down -- you have a base case, and an inductive step which depends on some cases that come "before" it. Think about how you would unroll the proof. More precisely, think about which cases the current case depends upon by expanding the statements upon whose truth your current statement depends.

Similarly in top-down DP, since you want to implement a recursion iteratively, the only constraint is that if state $$$S$$$ is dependent on state $$$T$$$, then we should have computed the answer for state $$$T$$$ before we compute the answer for state $$$S$$$.

For instance, suppose you want to compute the longest common subsequence of two strings $$$a$$$, $$$b$$$ using a DP in $$$O(nm)$$$ where $$$|a| = n$$$ and $$$|b| = m$$$.

The way you would solve it would be to make subproblems: consider the last characters of $$$a$$$ and $$$b$$$ and based on your answers to those subproblems, you solve this problem. In particular, to speed this up, you must have changed the problem you're solving to the problem where you consider the first $$$i$$$ characters of $$$a$$$ and the first $$$j$$$ characters of $$$b$$$. That is, for given $$$a$$$ and $$$b$$$, your state is completely determined by the pair $$$(i, j)$$$.

If you look at the recursion, the answer for state $$$(i, j)$$$ potentially depends upon the answers for $$$(i, j - 1)$$$, $$$(i - 1, j)$$$, $$$(i - 1, j - 1)$$$. The set of all states is $$${{ (i, j) \mid 1 \le i \le n \text{ and } 1 \le j \le m }}$$$. So, it suffices to order these states such that the dependents (i.e., $$$(i, j - 1)$$$, $$$(i - 1, j)$$$, $$$(i - 1, j - 1)$$$) are computed before $$$(i, j)$$$.

One such order is the lexicographical order: $$$(i, j)$$$ comes before $$$(i', j')$$$ if and only if either $$$i < i'$$$ or $$$i = i' \text{ and } j < j'$$$. So iterating over these states in lexicographical order works out for this problem (and that's exactly what we do when we iterate from $$$i = 1$$$ to $$$i = n$$$ and in a nested loop from $$$j = 1$$$ to $$$j = m$$$). This order works for most problems that you'll encounter in DP. Note that there can be more orders that work for this problem as well, for instance, switch the nested loops for $$$i$$$ and $$$j$$$.

As another example, sometimes you need to iterate over intervals, such that an interval $$$[l, r]$$$ depends on the intervals $$$[l + 1, r]$$$ and $$$[l, r - 1]$$$. I'll leave this as an exercise for you to figure out the order of the DP you will use.

The key point is that while the thought process while thinking about the correctness of DP remains the same, lots of things can be done by just thinking about the order in which you compute the states. Optimizing knapsack in terms of space is another example of this.