some tips for dynamic programming

1.如何来定义子问题。确定状态。

2.子问题的选取是否使得该问题具备最优子结构。能否利用cut and paste技术进行证明。母问题拆解时分成的若干子问题是否相互独立(significiant)。是否具备重叠的子问题。

3.写递归方程（状态转移方程）。求解最优解的值。（1）自下而上的迭代求解；（2）自上而下的备忘录方法----记忆化搜索。

4.如何在求解最优值的同时记录最优解的相关信息。如何利用相应的数据结构呈现最优解的结构。

5.dp用于最优化问题，最优化条件其实就是一种搜索的剪枝条件。