算法可视化 连接
动态规划
定义
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。在面试笔试中动态规划也是经常作为考题出现，其中较为简单的 DP 题目我们应该有百分之百的把握顺利解决才可以。
动态规划实际上是一类题目的总称，并不是指某个固定的算法。动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。动态规划的核心思想是巧妙的将问题 拆分 成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似 递推 迭代的方法解决要求的问题。
求解步骤
第一步：状态的定义
第二步：状态转移方程的定义
在这里，我们为了避免混淆用「状态」这个词来替代「问题」这个词。「问题」表示的含义类似：题目、要求解的内容、题干中的疑问句这样的概念。「状态」表示我们在求解问题之中对问题的分析转化
状态定义
有的问题过于抽象，或者过于啰嗦干扰我们解题的思路，我们要做的就是将题干中的问题进行转化（换一种说法，含义不变）。转化成一系列同类问题的某个解的情况，比如说：
题目：求一个数列中最大连续子序列的和
我们要将这个原问题转化为：
状态定义：Fk 是第 k 项前的最大序列和，求 F1～Fn 中最大值。
通过换一种表述方式，我们清晰的发现了解决问题的思路，如何求出 F1～Fn 中的最大值是解决原问题的关键部分。上述将原问题转化成另一种表述方式的过程叫做：状态的定义。这样的状态定义给出了一种类似通解的思路，把一个原来毫无头绪的问题转换成了可以求解的问题。
状态转移
在进行了状态的定义后，自然而然的想到去求解 F1～Fn 中最大值。这也是状态定义的作用，让我们把一个总体的问题转化成一系列问题，而第二步：状态转移方程的定义则告诉我们如何去求解一个问题，对于上述已经转换成一系列问题我们要关注的点就在于：如何能够用前一项或者前几项的信息得到下一项，这种从最优子状态转换为下一个最优状态的思路就是动态规划的核心。 对于上面的例子题目来说，状态转移方程的定义应该是：
Fk = max{Fk-1+Ak, Ak}
Fk 是前 k 项的和，Ak 是第 k 项的值
仔细思考一番，我们能够得到这样的结论，对于前 k 个项的最大子序列和是前 k-1 项的最大子序列和 Fk 与第 k 项的和、或者第k项两者中较大的。