3.4. Dynamic Programming


Two equivalent approaches to implement dynamic programming are top-down with memoization and bottom-up. Top-down with memoization is like a cached recursive function call, and it is more natural to implement. The speed is sometimes faster than bottom-up approach.

As for the bottom-up approach, the most crucial part is to get the recurrence equation. It tests the math modeling ability of candidates.

DP is normally to resolve optimization problem. For instance, in the following cases, we can consider using dynamic programming?

  1. Input cannot sort

  2. Find minimum/maximum result

  3. Check the feasibility

  4. Count all possible solutions