参考: 五大常用算法之二：动态规划算法

Concept:动态规划: 多阶段最优化决策解决问题的过程.

每次决策依赖于当前状态,又随即引起状态迁移,一个决策序列就在变化的过程中产生出来.

Mechanism:

分阶段解决子问题,按顺序求解子问题,前一子问题的解为后一子问题提供信息.

在求解任一问题时,列出可能的局部解, 保留能到达最优解的局部解, 丢弃其他局部解.

依次解决各个子问题, 最后一个子问题就是初始问题的最优解.

动态规划解决的问题多有子问题重叠的特点

二维数组: 存储重叠的子问题的解(状态)

与分治法的差别

动态规划学习