Cracking the coding interview 6: Recursion and DP | Earlysun's rising
After this chapter, you should be able to come up with a recursion way to solve problem very quickly. Be clear about the base case and when to return.
For the dynamic programming:
1. Is it a optimal problem?
2. Does the subproblems share solutions?
If so, you may consider to solve it with dynamic programming. There are two ways to design a dynamic programming algorithm:
1. From the top to bottom.
2. From the bottom to top.
The previous one is easier to consider and write, the cons is it normally use a recursive way, which has higher space use.
The latter one is to build the answer from the bottom and access to target gradually. It needs to calculate every result of subproblems while the former one only solves part of them.
For dynamic programming solution, according to CLRS, we usually store it when we made a decision and then recursively call function to output the result.
Read full article from Cracking the coding interview 6: Recursion and DP | Earlysun's rising
No comments:
Post a Comment