一、基本概念与定义
1、动态规划的概念
对于某些问题，我们可以将其分成若干个互相联系的阶段，并在每个阶段做出决策，从而达到最优解。
这种通过状态来影响决策，在经由决策引起状态转移的动态过程被称作动态规划（简称DP）
动态规划（DP）不是某种具体算法，而是一种思想。
核心在于：把大问题转化为小问题，利用小问题的解，推断出大问题的解。
2、状态
当我们把大问题化成小问题时，只有大问题和小问题拥有相同的形式，才能考虑拆分子问题。
如果满足这个要求，那么我们遇到的每个子问题，都可以通过某种简洁的形式来 表达。
我们把可能遇到的每种“局面”称为状态。
设计完状态之后，只要能利用小状态的解求出大状态的解，就可以动手把题目做 出来！
3、转移
当我们设计好状态，我们需要用小状态推出大状态。
从一个状态的解，得知另一个状态的解，我们称之为“状态转移”。这个转移式子 称为“状态转移方程”。
4、Dp的基本原则
（1）最优子结构：大问题的最优解，一定是从小问题的最优解推出来的。
（2）无后效性：无后效性 现在的决策，只与过去的结果有关，而与过去的决策无关。
5、DP与记忆化搜索
(1)记忆化搜索
在经$dfs$搜索过程中，会产生许许多多的子序列，对于每个序列，可能会产生重复的元素。
例如：
求99！，100！，101！
一般思路，分别从1开始乘
但显然，对于这道题我们只需要算出99！，就不需要再从头计算了，因为100！即是99！ * 100，而101 ! 即是 100 ！ * 101 ！
所以说，我们只需要在阶乘的过程中将 99 ! 的得数存到数组a[99]中，等到下次再调到用时，就可以直接访问a[99]，从而省去不必要的时间。
一般情况下，可以将O($2^n$)的时间复杂度优化为O($n^2$)的复杂度。
(2)DP
对于同样的问题，我们并不考虑如何直接去求 99 ! ,而去考虑如何可以将 99 ！ 分成若干个子问题。
显然 99 ！ = 98 ！ * 99；
而 98 ! = 97! * 98;
以此类推，我们可以等到： 1 ！ = 1
可以看出，对于所有的阶乘问题，我们都可以从 2的阶乘开始计算，最后一步步到达想要的结果，这就是DP。
同时，对于这道题，状态转移方程为：a[N] = a[N - 1] * N;且a[0]=1
6、DP与递推
从上面我们的探究可以看出，对于同一个问题，DP的做法是，从最初结点开始遍历，在过程中，我们不考虑之前的值是否存在，也不考虑当决策是否对之后产生影响，只是根据状态转移方程，一步步选择，从而得到结果。
我们可发现，DP其实运用了递推的思想。
我们可以把状态转移方程看成递推公式，把初始值看做递推边界。
对于上题，我们同样可以写成递推公式
$F_n=F_{n-1}*n$；$F_0=1$
同时，我们可以把记忆化搜索看成递归的思想
在搜索过程中沿着某一个答案前进，在过程中调用之前所储存的答案。
所以，记忆化搜索和递推也常被当做DP的一种实现方式。
二、DP程序的设计
1、转移方式
（1）backward 型转移：我从哪里来?
这是一种常见的思路：对于一个没有求出解的状态，利用能走到它的状态，来得出它的解。
同时它也是记忆化搜索的方式
（2）forward 型转移:考虑我到哪里去
对于一个已经求好了解的状态，拿去更新它能走 到的状态。
2、DP三连
我是谁? (设计状态)
我从哪里来 (backward 型转移)
我到那里去 (forward 型转移)
(两种转移方式中，只需要选择一个来设计转移即可。)
