[Algo] Dynamic programming 动态规划

https://en.wikipedia.org/wiki/Dynamic_programming

The same as divide and conquer, firstly we divide the problem, than we do the decision depends on the last result we got : this need us to stock the result somewhere to avoid recalculations. This is the most different from Divide : we need to stock the result and this result can be used in next steps.

when to use :

1. optimization principle : if the problem is about find optimized solution, the sub problems should be about find optimized solutions, too.
2. when this stat is done, the stats after this is not influenced by this stat.
3. sub problems are not independent, they have overlapping (重叠)

How :
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

1. divide the stages (阶段) in term of  time or space for the problem, and all these stages can be sorted
2. decide stat value and stats
3. from "how to do decision" to "how the stat transforms"
4. find boundary conditions 
5. recursive program   

Applications :

1. Fibonaci polynomial 
2. Knapsack Problem
3. 最长公共子序列
4. Floyd-Warshall算法
5. Viterbi算法