一、动态规划的认识
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
1、已知问题规模为(i-1)的解，可以推导出问题规模为i的解，即：f(i) = F[f(i-1)]
这样我们就可以一直向前推导，得到问题规模为0的状态，这种规模的解一般是显而易见的。这种方法也就是我们经常使用的数学归纳法。
对于f(i), 我们只需要知道它的上一个状态f(i-1)就可以完成的推理过程，而不需要更前序的状态，我们将这个模型称为马尔科夫模型，对应的推理过程叫做“贪心法”。
2、如果我们要求解问题规模为i的解，需要知道所有的前序状态，即：f(i) = F[f(0), f(1), ..., f(i-1)], 这种求解方法也叫第二数学归纳法。
对于f(i)，我们需要知道这个状态之前的所有前序状态，才能完成的推理模型叫做高阶马尔科夫模型，对应的推理过程叫做“动态规划法”。
二、基本思想
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
动态规划算法：它通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
分治法：若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。
注：不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
三、适用情况
能采用动态规划求解的问题的一般要具有3个性质：
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
四、求解基本步骤
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
图1 动态规划决策过程示意图
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
（4）根据计算最优值时得到的信息，构造问题的最优解
五、算法基本框架
```
for(j=1; j<=m; j=j+1) // 第一个阶段
xn[j] = 初始值;
for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案
print(x1[j1]);
for(i=2; i<=n-1; i=i+1）
{
t = t-xi-1[ji];
for(j=1; j>=f(i); j=j+1)
if(t=xi[ji])
break;
}
```
六、例解
leetcode: 516. 最长回文子序列
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入:"bbbab"
输出:4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:"cbbd"
输出:2
一个可能的最长回文子序列为 "bb"。
分析：这个问题很显然是要求一个最优解的问题，考虑使用动态规划，动态规划问题求解的关键在于如何划分状态（即找出最优子结构，并且保证无后序性），也就是需要划分清楚当前状态和前一状态，然后列出状态之间的转移方程和边界条件。
对于这个问题，需要寻找字符串的最长回文子序列（子序列可以不连续），动态规划的思想是要将问题规模减小，用小规模的状态解表示大规模的状态解，直到边界。那么分析回文序列的性质，两个不同长度字符串的回文长度有什么关系呢？
首先很显然单个字符的回文长度为1，这个就可能是个边界条件。基于这个边界条件进行规模扩展，由于回文是对称的，所以考虑向两边各加一个字符，那个这个更大规模的字符串的最长回文长度就可以表示为：
```
if (a == b):
f(i) = f(i-2) + 2
else:
f(i) = max(前f(i-1)， 后f(i-1))
```
所以可以用f[i][j]表示字符串中子串i->j的最长回文长度，那么状态转移方程为：
如果 s 的第 i 个字符和第 j 个字符相同的话
```f[i][j] = f[i + 1][j - 1] + 2```
如果 s 的第 i 个字符和第 j 个字符不同的话
```f[i][j] = max(f[i + 1][j], f[i][j - 1])```
代码如下：
```
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] f = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
f[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1] + 2;
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
return f[0][n - 1];
}
}
```
记住，一般动态规划中会用一个二维数组记录之前状态的结果，便于后面直接使用。其实这样空间消耗是比较大的o(n^2)，如果我们仅仅只需要知道前一个状态的结果就可以，那么就不必将之前所有状态结果保留，从而减少空间复杂度。
