How to solve DP: part 2
It was a sunny day in November 2019. It should be either Tuesday or Friday as I am teaching during those two days. When I was taking ferry and subway from my home to school, the 2-hour traveling time makes a perfect time slot to think about how to teach dynamic programming by using a relatively easy way.
After summarizing several DP problems, I came up with two general strategies:
- TCP-DP
- NCtoDP
I will explain them one by one.
TCP-DP
Find Transitions between subproblems
Using Cache to memorize solutions of overlapped subproblems if necessary.
Prune infeasible branches as soon as possible.
Use three parts mentioned above the solve DP problems.
This is a basic explanation of TCP-DP strategy. I use C (short for Cache) instead of M (short for Memorization) as TCP will be easier to memorize if you in case know the TCP/IP protocol in computer networks. You can also call this strategy as TMP-DP.
NCtoDP
From Naive Complete Search to DP.
Think about a naive solution firstly is always a good strategy to solve coding problems. Same for DP problems. As DP problems are always trying to find an optimal solution, so the naive approach will be a complete search.
Of course, the complete search is too computationally expensive, however, it will be very natural to come up with a naive solution. Then think about how to improve by using DP. What is the complexity of naive complete search? What is the complexity of improved DP? Usually, the DP can speed up an exponential algorithm to the polynomial (such as Fibonacci sequence and Number of Ways to Stay in the Same Place After Some Steps )or from factorial to exponential (such as traveling salesman problem). Keep on thinking in this way will be super helpful to improve your efficiency in solving DP problems.
This is my quick summary, hope it is helpful.
12/02/2019
