动态规划算法

动态规划过程：每一次决策依赖于当前的状态，即下一状态的产生取决于当前状态。一个决策序列就是在变化的状态中产生的，这种多阶段最优化问题的求解过程就是动态规则过程。

基本思想原理

与分而治之原理类似，将待求解的问题划分成若干个子问题（阶段）求解，顺序求解各个子问题（阶段），前一子问题（阶段）为后一子问题（阶段）的求解提供有用的信息。通过各个子问题（阶段）的求解，依次递进，最终得到初始问题的解。一般情况下，能够通过动态规划求解的问题也可通过递归求解。

动态规划求解的问题多数有重叠子问题的特点，为了减少重复计算，对每个子问题只求解一次，将不同子问题（阶段）的解保存在数组中。

与分而治之的区别：分而治之得到的若干子问题（阶段）一般彼此独立，各个子问题（阶段）之间没有顺序要求。而动态规划中各子问题（阶段）求解有顺序要求，具有重叠子问题（阶段），后一子问题（阶段）求解取决于前一子问题（阶段）的解。

与递归区别：与递归求解区别不大，都是划分成各个子问题（阶段），后一子问题（阶段）取决于前一子问题（阶段），但递归需要反复求解同一个子问题（阶段），相较于动态规划做了很多重复性工作。

适用解决问题

采用动态规划求解的问题一般具有如下性质：

1. 最优化原理：求解问题包含最优子结构，即，可由前一子问题（阶段）最优推导得出后一子问题（阶段）最优解，递进得到初始问题的最优解。
2. 无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。
3. 有重叠子问题：子问题（阶段）之间不是独立的，一个子问题（阶段）的解在下一子问题（阶段）中被用到。（不是必需的条件，但是动态规划优于其他方法的基础）

求解步骤