Dynamic Programming
题目列表
- house robber
- flip game
- word break
- paint fence
题目思想
如果在分解问题变成sub-problem的过程中，发现了一些overlapping subproblems, 那么这是一个hint说明你应该用DP了。
The optimal solutions to the subproblems contribute to the optimal solution of the given problem.
想出DP解法的一般步骤： (其实是记忆化搜索)
- 先想出一个recursive的方法来解决问题(比较直观)
- 将
P(X)表达成P(Y)的表达式，（Y < X)
- 将
- write the recursive code
- save the results for every function run so avoid recomputing
- 分析space和time complexity, 看是否能够improve
Dynamic Programming
与"divide and conquer"有些类似，都是将问题分为子问题，然后利用子问题的解来 获得整个问题的解。与'divide and conquer'的不同之处在于，对于一个相同的子问题 不会重复计算，而是将结果存在一个表里方便查询。
记忆化搜索 memorization search
常见的DP，一般都是一步接着