动态规划前两篇大概讲了几个例子，这一篇有点偏向于理论，和说明下动态规划中的概念。
这一篇是个笔记和总结。
一 什么问题适合用动态规划
关于这个问题，王争老师总结位一个模型三个特征。我们一般是用动态规划来解决最优的问题。而解题过程中，要经过很多决策阶段，每个阶段对应一组状态。我们要做的就是寻找一组决策序列，通过这组决策序列可以达到最优的解。
这就是多阶段求最优解的模型。
三个特征：最优子结构，无后效性和重复子问题。
1. 最优子结构
最优子问题结构可以理解为问题最优解可以通过前面的子问题最优解来推导。也就是说我们的最优解是前面最优解来推导出来的。
这个我隐约觉得有点问题，比如最终的最优解也许是整体的最优解，而不是每步都是最优解，回头再仔细研究下。
2. 无后效性
无后效性比较好理解，就是推导后面阶段的状态中，我们只关心当前的状态；而且前面状态确认后，就不会变了。
3. 重复子问题
重复子问题的意思是经过多个阶段到最终完成中，存在着多个重复的状态问题。
4. 举例说明
给一个n*n的矩阵，从（0，0）开始走到（n-1,n-1)的坐标位置，每次只能向下和向右走。
走的过程中经过的方格里面的数字，表示路径的长短，问怎么走，最终的路径最短。
一个模型：每步行走我们可以看作一种状态，走的办法是通过多个阶段的选择到底到(n-1,n-1)位置，阶段划分的理解图如下：
说明，阶段0是未开始走，阶段一是迈出第一步的可能选择，只能有两个位置，下面的阶段依次类推。
最优子结构：
我们从位置（0，0）到达位置：（i,j)的最小路径，记作min_dist(i,j)，这个路径必然从（i,j-1)或（i-1，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_dist(i-1, j))
无后效性:
这个我们每次选择一步后，后面的选择不会影响前面的状态。
重复子问题：
即在相同的阶段，路径的值相同，但是是不同的路径。
下面的小图没看出有这个，不过确实存在的：
第一阶段： 1
第二阶段： 1+2 ，1+3
第三阶段：1+2+5 ，1+3+1，1+2+1，1+3+5
每个阶段如果有重复的值就代表是重复的子问题，值不重复的话，如果位置重复，那么我们值用取到此位置路径最小的即可。
二 动态规划解题思路
动态规划可以有两种方法来解答，一种是状态转移表方法，另外一种是状态转移方程，一般来说状态转移表的方法更适合简单的情况。
状态转移表
前两次介绍动态规划说过，动态规划的问题都可以用回溯的算法暴力搜索得到，然后我们根据回溯算法定义状态，从而画出递归树，通过递归树可以看是否存在重复子问题，以及重复子问题是如何产生的，以此来找规律，用动态规划的方法解决。
回溯算法+备忘录，这种性能上已经和动态规划算法没什么区别；用动态规划算法可以用转移表方法。
我们先画一个状态表，状态表一般是二维的，所以你可以把它想象成二维数组。其中每个状态包含三个变量，行，列，数组值，我们根据状态变化的步骤，从前到后依次类推，填充状态表的每个值，翻译成代码，就是动态规划。
说实话，我对这种方式理解起来还觉得有些困难，二维数组的行，列，值已经比较复杂了，有的还涉及到三维，四维，脑袋要想炸了。
回到开头的问题，看看如何用状态表的办法进行解答：
暴力回溯算法和以前一样：
private int minDist = Integer.MAX_VALUE;
// 调用方式：minDistBacktracing(0, 0, 0, w, n);
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
if (i == n && j == n) {
if (dist < minDist) minDist = 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);
}
}
有了代码，下面就可以画下递归树，递归树的一个状态包含三个变量(i,j,dist)其中i表示行，
j表示列，dist表示从起点到（i，j）的路径长度，图中我们看到同一层，dist没有重复的，
但是(i,j)有重复的，也就是到一个位置有多个不同的dist，按道理，我们只要取最小的分解即可，前提的节点可以丢弃。
画一个二维状态表，行和列表示棋子所在的位置，表中数值从起点到这个位置的最短路径。
从第一行和第一列计算好了之后，后面的都根据前面的来推算，具体过程如下表：
表很容易看懂，那么我们来看下代码：
public 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) {
//这一步本身的值加上两个可能走到这个位置的最小值
//取最小值就去掉了重复的子问题，都走到同样的位置
//matrix[i][j] 表示原始值不是计算后的值
states[i][j] = matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
}
}
return states[n-1][n-1];
}
状态转移方程
给我感觉状态转移方程类似于递归的解题思路。某个问题如何通过子问题来递归求解。这里面的子问题就是上面说的最优子结构，写出递归的公式，就是状态转移方程了。
代码实现上，一种是递归+备忘录；一种是迭代递推，这个也是和第一种方法有些类似了。
上面已经分析出状态转移方程了：
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
递归的方式代码：
private 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];
// 调用 minDist(n-1, n-1);
public int minDist(int i, int j) {
//递归结束条件
if (i == 0 && j == 0) return matrix[0][0];
//重复位置直接返回
//只保留最小的
if (mem[i][j] > 0) return mem[i][j];
int minLeft = Integer.MAX_VALUE;
if (j-1 >= 0) {
minLeft = minDist(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 状态转移表：回溯算法实现-->定义状态-->画递归树-->找出重复子问题-->画状态转移表-->根据递推公式天表-->将填表过程翻译成代码。
2 状态转移方程： 找最优子结构-->写状态转移方程-->将状态转移方程翻译成代码。
贪心，回溯，分治和动态规划是四种算法思想，其中贪心，回溯，动态规划可以分为一类，这三种算法都是求解多阶段最优解的模型的。
回溯算法，应用很广泛，用动态规划算法和贪心算法可以解决的问题，用回溯算法也可以解决。我的理解回溯算法相当于穷举搜索了，穷举过程中，对比是不是最优解，回溯算法的时间复杂度很高，指数级别，不过可以通过备忘录来简化。
动态规划算法，适用于满足一个模型和三个特征的问题，三个特征为，最优子结构，无后效性和重复子问题。
分治算法，要求问题可以分为多个子问题，不能有重复的子问题，而动态规划算法恰恰相反反，动态规划算法就是规避了回溯算法中的重复子问题的。
贪心算法，是动态规划算法的一种特殊情况，解决问题更加高效，代码实现简洁，但是又时候求出来的不是最优解。它能解决的问题也要满足三个条件，最优子结构，无后效性和贪心选择。其中最优子结构和无后效性和动态规划算法一样，贪心的选择行，是可以通过局部最优解来求全局最优解的。每个阶段，我们只选择当前的最优策略，最终达到全局的最优解。
