dynamic programming talk - try to understand the tips shared in the Chinese blog.

Dynamic programming talk

Dynamic programming tips:

http://blog.csdn.net/uestclr/article/details/50760563


动态规划的关键点：

1、最优化原理，也就是最有子结构性质。这指的是一个最优化策略具有这样的性质，无论过去状态和决策如何，对前面的
决策所形成的状态而言，余下的决策必须构成最优策略，简单来说就是一个最优化策略的子策略总是最优的，如果一个问题
满足最优化原理，就称其有最优子结构性质。

2、无后效性，指的是某个状态下的决策的收益，只与状态和决策相关，与达到该状态的方式无关。

3、子问题的重叠性，动态规划将原来指数级的暴力搜索算法改进到了具有多项式时间复杂度的算法，其中的关键在于解决了
荣誉，重复计算的问题，这是动态规划算法的根本目的。

4、总体来说，动态规划算法就是一系列以空间换取时间的算法。