一个模型三个特征
多阶段决策最优解模型
一般用动态规划解决最优问题。解决问题的过程需要经历多个决策阶段，每个决策阶段都对应着一组状态。寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。最优子结构
问题的最优解包含子问题的最优解。同样，可以通过子问题的最优解，推导出问题的最优解。对应动态规划问题模型，后面阶段的装填可以通过前面阶段状的状态推导出来。无后效性
两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。重复子问题
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
实例解析：
一个n乘以n的矩阵w[n][n]。矩阵存储的都是正整数，棋子起始位置在左上角，终止位置在右下角。将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。把每条路径经过的数字加起来看做路径的长度。求从左上角移动到右下角的最短路径长度。
从(0,0)走到(n-1.n-1),总共需要走2*(n-1)步，也就对应着2*(n-1)个阶段。每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。把状态定义为min_dist(i,j)，其中i表示行，j表示列。min_dist表达式的值表示从(0,0)到达(i,j)的最短路径长度。这个问题是一个多阶段决策最优解问题，符合“动态规划的模型”。
可以用回溯算法解决问题。递归树中有重复的节点，重复的节点表示，从左上角到节点对应的位置，有多种路线，说明这个问题存在“重复子问题”。
走到(i,j)这个位置，只能通过(i-1,j)，(i,j-1)这两个位置移动过来。所以计算(i,j)位置对应的状态，只需要关心(i-1,j)，(i,j-1)两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，仅仅允许往下和往右移动，不允许后退，前面阶段的状态确定之后，不会被后面阶段的决策所改变，符合“无后效性”。
定义状态的时候，把从起始位置(0,0)到(i,j)的最小路径，记作min_dist(i,j)。因为只能往右或往下移动，所以只有可能从(i-1,j)或者(i,j-1)两个位置到达(i,j)。到达(i,j)的最短路径肯定包含到达这两个位置的最短路径之一。min_dist(i,j)可以通过min_dist(i,j-1)和min_dist(i-1,j)这两个状态推导出来，这个问题符合“最优子结构”。
min_dist(i,j) = w[i][j] + min(min_dist(i,j-1),min(i-1,j))
动态规划解题思路
一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。
状态转移表法&状态转移方程法
状态转移表法
思路：回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树。从递归树中，可以看出来是否存才重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是够能用动态规划解决。
找到重复子问题之后，一种是直接使用回溯加备忘录的方法，来避免重复子问题，提高执行效率。一种是使用动态规划的解决方法，状态转移表法。矩阵最短路径 回溯算法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16private int minDist = Integer.MAX_VALUE;
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
//到达(n-1,n-1)这个位置
if(i == n && j == n) {
if(dist < minDist) midDist = dist;
return;
}
if(i < n) {
//往下走，更新i=i+1,j=j
minDistBT(i+1, j, dist+w[i][j], w, n);
}
if(j < n) {
//往右走，更新i=i,j=j+1
minDistBT(i, j+1, dist+w[i][j], w, n);
}
}先画出一个状态表，状态表一般是二维的，类似二维数组。其中每个状态包含三个变量，行、列、数组值。根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后将这个递推填表的过程，翻译成代码，就是动态规划代码。
矩阵最短路径 状态转移表1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public int minDistDP(int[][] matrix, int n) {
int[][] states = new int[n][n];
int sum = 0;
//初始化states的第一行数据
for(int j = 0; j < n; ++j) {
sum += matrix[0][j];
states[0][j] = sum;
}
sum = 0;
//初始化states的第一列数据
for(int i = 0; i < n; ++i) {
sum += matrix[i][0];
states[i][0] = sum;
}
for(int i = 1; i < n; ++i) {
for(int j = 1; j < n; ++j) {
states[i][j] + Math.min(states[i][j-1], states[i-1][j]);
}
}
return states[n-1][n-1];
}大部分状态表都是二维的，如果状态比较复杂，需要很多变量来表示，那对应的状态表可能是高维的，不适合用状态转移表法解决，
状态转移方程法
思路：找最优子结构-写状态转移方程-将状态转移方程翻译成代码状态转移方程法类似递归的解题思路。分析某个问题如何通过子问题来递归求解，即最优子结构。根据最优子结构，写出递归公式，即状态转移方程。状态转移方程式解决动态规划的关键。
有了状态转移方程，一种是递归加备忘录，一种是迭代递推。矩阵最短路径 递归+备忘录1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18private int[][] matrix = {{1,3,5,9},{2,1,3,4},{5,2,6,7},{6,8,4,3}};
private int n = 4;
private int[][] mem = new int[4][4];
public int minDist(int i, int j) {
if(i == 0 && j == 0) return matrix[0][0];
if(men[i][j] > 0) return matrix[0][0];
int minLeft = Integer.MAX_VALUE;
if(j-1 >= 0) {
minLeft = minDeft(i, j-1);
}
int minUp = Integer.MAX_VALUE;
if(i-1 >= 0) {
minUp = minDist(i-1,j);
}
int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);//状态转移方程
mem[i][j] = currMinDist;
return currMinDist;
}矩阵最短路径 迭代递推1
参考状态转移表法代码。（代码相同，只是思路不同）
贪心、分治、回溯、动态规划对比
分治算法
贪心、回溯、动态规划可以归为一类，解决问题的模型都可以抽象成多阶段决策最优解模型；分治算法解决问题大部分是最优解问题，但是大部分都不能抽象成多阶段决策模型（各阶段情况相同，类似二分查找），不能有重复子问题。回溯算法
回溯算法是个万金油。基本上能用动态规划、贪心算法解决的问题，都可以用回溯算法解决。回溯算法相当于穷举(暴力)搜索，穷举所有的情况，然后对比得到最优解。回溯算法的时间复杂度 非常高，是指数级别的，只能用来解决小规模数据的问题。动态规划
尽管动态规划比回溯算法高效，但是并不是所有问题都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性、重复子问题。多阶段最优解模型。
在重复子问题上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。贪心算法
贪心算法实际上是一种特殊的动态规划。它解决问题起来更加高效，代码实现也更加简洁，可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性、贪心选择性（不强调重复子问题）。
贪心选择性指，通过局部最优的选择，能产生全局的最优选择。每一个阶段，都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。（贪心算法的解不一定是全局最优解）