Skip to content
RSS feed tkhwang on GitHub tkhwang on Twitter

Dynamic Programming in javascript

✨ Fatures

Overlapping subproblems

  • The problem can be broken down into overlapping subproblems
  • smaller versions of the original problem that are re-used multiple times.

Optimal substructure

  • The problem has an optimal substructure
  • an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem.

💡 When to Use DP

First hint

The problem will ask for the optimum value (maximum or minimum) of something, or the number of ways there are to do something. For example:

  • What is the minimum cost of doing...
  • What is the maximum profit from...
  • How many ways are there to do...
  • What is the longest possible...
  • Is it possible to reach a certain point...

Second hint 

That future "decisions" depend on earlier decisions.
  • Deciding to do something at one step may affect the ability to do something in a later step.
  • This characteristic is what makes a greedy algorithm invalid for a DP problem - we need to factor in results from previous decisions. Admittedly, this characteristic is not as well defined as the first one, and the best way to identify it is to go through some examples.a

🍀 Framework for DP Problems

  • A function or data structure that will compute/contain the answer to the problem for every given state
    • dp() for top-down solution
    • dp[] for bottom-up solution
  • A recurrence relation to transition between states.
  • Base cases, so that our recurrence relation doesn't go on infinitely.

💡 Bottom-up solution [object Object]

  • Usually, it shows better performance.

💡 Top-down solution [object Object]

  • Usually, memoization is necessary.
  • For memoization, dp() should return value, not to use the global variable.
  • For calculation the number of cases
    • For good case, return 1.
    • For wrong case, return 0.

🏷️ Related tags

📚 References