How to solve DP: part 1

DP and Recursion

As a brave programmer, we should be brave enough to solve Dynamic Problem and also we should bravely admit the close connection between DP and recursion. Also, we should believe that recursion is a hard topic and also a critical part to distinguish professional and non-professional programmers or computer scientists.

In my knowledge base, recursion contains two cases:

case A: recursion without encountering duplicated subproblems

case B: recursion with encountering duplicated subproblems.

For case A, we call recursion. For case B, we can cache the subproblems and when the second time we encounter the same subproblem, directly return the cached result with complexity of O(1). We call cache as memorization. We also call the second approach as Dynamic Programming.

Recursion problems have two ways to solve: bottom-up and top-down. Usually, we call a bottom-up approach as an iterative way and a top-down approach as a recursive way to solve problems.

Since DP is a special recursion, we also have bottom-up and top-down two approaches for DP. Bottom-up solve sub-problems in topological sort order with all results of subproblems needed to solve the next subproblem already saved somewhere. The top-down approach has to explicitly cache the results of subproblems to avoid duplicated computation.

The Fibonacci number is a classical dp problem, and we can use the bottom-up and top-down approach to solve this problem and have a better understanding of what I summarized before. Code is provided here:

https://github.com/liketheflower/leet_code_jimmy/blob/master/dp/FibonacciSequence/fib.py

Regarding the time complexity, usually, DP can speed up the naive complect search solution (if we have one) from O(n!) to polynomial. Or DP can improve the complexity of naive one from exponential to polynomial. The reason is not only using DP (memorization) can avoid the unnecessary computation of the same subproblem but also DP can prune the unnecessary searching branches which complete search will explore. Hence, the complexity can be improved.

For example, the Fibonacci number problem, without DP, the solution is O(2^n) with DP, it is only O(n).

Thanks for reading. In the future, I will keep on summarizing DP problems in terms of building approaches (find the subproblems or state and their transitions, bottom-up and top-down approaches)and time complexities (compared with the naive one).