After more detail read, this time I start to realize the core of this chapter. It is actually not that important to understand 1000 algorithms which is based on DP. Rather it is important to understand why a problem is a DP and why it is not. So, the heart of this chapter is actually Chapter 15.3 and I found the examples about unweighted shortest simple path and unweighted longest simple path are the most illuminating.
The key of knowing when you can applying DP (which I frankly feel blurry sometimes) is that you want to know whether there is relationship between a problem and its subproblem. You also want to know whether the subproblem is being repeatedly solved. Both can be observed by looking at how a big problem is solved in the first place.
It's also important to understand when will a problem will become intractable polynomially.
I think I am good for this read. All of the examples are interesting and currently I have a feel on the rod cutting problem as well as matrix multiplication problem. The key of these types of problem is to think through the solution yourself and try to come up with the solution. I guess what I will add now is to always think through the problem dependency tree as well as the structure of the subproblems.
No comments:
Post a Comment