20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。

在现实生活中，有类问题可将过程划分成多个互相联系的子阶段，我们需要对每一个子阶段作出角色，以使得整个问题得到最好的解。注意这里的子阶段之间并不是相互独立的，而是后面的一个子问题的解决依赖前一个子问题的解决。我们通过一个例子，理解下这个过程：

问题：我想要在中央谋个职位，可我一个平头老百姓无法直接找中央帮我安排，咋办？

这样的一个大的问题，我们将其划分成多个相互联系的子问题，解决一个一个的子问题，整个问题得以解决，过程如下：

1. 找邻居，邻居认识村长，给村长送礼，请村长喝酒，搞定村长；
2. 找村长，村长认识镇长，给镇长送礼，请镇长喝酒，搞定镇长；
3. 找镇长，镇长认识县长，给县长送礼，请县长喝酒，搞定县长；
4. 找县长，县长认识市长，给市长送礼，请市长喝酒，搞定市长；
5. 找市长，市长认识省长，给省长送礼，请省长喝酒，搞定省长；
6. 找省长，省长认识中央，给中央送礼，请中央喝酒，搞定中央，问题解决。

具有多个阶段，并且多个阶段相互联系的问题，叫做多阶段决策问题。在多阶段决策问题中，将一个大问题分解为多个子问题，然后解决相互联系的子问题来从而解决整个问题的思想就是动态规划。

这里需要提到一点，动态规划和分治思想不同，虽然两者都会将一个大问题分解成多个子问题，但是分治法的若干子问题之间都是相互独立的，而动态规划分解出的多个子问题之间是相互关联的。

动态规划是一种重要的算法思想，并不是一种具体的算法。动态规划并没有固定的模式，也并不适用于所有的问题，只有问题满足以下因素才适用于动态规划：

最优化原理：是解决多阶段决策问题的理论。假设为了解决某一优化问题，需要依次作出 n 个决策 \(D_{1}、D_{2} … D_{n}\)，如果这个决策序列是最优的，对于任何一个整数k（1<k<n），决策 \(D_{k+1}、D_{k+2} … D_{n}\) 也是最优的。用上面的例子来描述的话，对于找工作这个问题，其解可能并不是唯一的，但是我们找到了最优解。此时，其一个子问题的解也是最优的，比如：如果你不再是一个老百姓，而是一个镇长，想在省政府某个职位这个问题，其最优决策序列为：

1. 找县长，县长认识市长，给市长送礼，请市长喝酒，搞定市长；
2. 找市长，市长认识省长，给省长送礼，请省长喝酒，搞定省长，问题解决。

子问题该最优决策序列为原来最优序列的子序列。

无后效性：一个多阶段的决策问题，每一个阶段的决策只取决于前一个阶段的决策。每一个阶段的决策都是对过去历史阶段的一个完整总结。此时，当前阶段之后的决策还未产生，所以与其更没有关系。简言之：你当前的决策只与上一个阶段的决策有关。例如：前面的 第 4 阶段决策，只与第 3 阶段的决策有关，即：第4阶段能不能找到市长，只与第3阶段能不能搞定县长有关，与更早阶段的搞定村长、搞定镇长没有关系。第 3 阶段搞定县长是对前面搞定村长、搞定镇长的历史总结。

子问题的重叠性：这个概念应该这三个概念最绕的理论了。我们结合 Dijkstra 最短路径算法来理解子问题的重叠性，先看下我们在讲解该算法时用到的图：

我们要找到 1->3 的最短路径，这个子问题是计算从起始顶点到其他所有顶点的最短路径问题的一个子问题。当我们计算 1->4 阶段的最短路径子问题时，我们会发现 1->4 问题的解决必须要先计算 1->3 的最短路径。此时，我们发现两个阶段的的子问题，就会有重叠部分。

1. 1->3 问题解决；
2. 1->4 问题的解决覆盖了 1->3 问题的解决。

所以，重叠子问题就是指各个子问题之间相互联系，具有公共部分。如果子问题之间没有公共部分，那么使用分治思想来解决比较好。就像归并排序算法一样，其将问题分解为 N 个 子问题，子问题之间相互独立，安静的解决各个独立的子问题就可以了。

所以在动态规划中，我们一般会将阶段的结果存储到表里，后面如果用到了直接查表就可以。比如：当我们解决了 1->3 的最短路径时，我们就将其存储到表中，下次解决 1->4 时，需要知道 1->3 的路径长度，直接从表里取出即可，不需要再重复计算 1->3 的路径距离。

动态规划解决问题时，需要具体问题具体分析。