dynamic programming（决策），decision research，是对传统递归的一种优化，它将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。一个问题是否能用动态规划来解决取决于这些”小问题“会不会被重复调用。
性质
无后效性：“未来与过去无关”。严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。
最优子结构性质：大问题的最优解可以由小问题的最优解推出。
判断一个问题能否使用DP解决：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
DP的典型应用：DAG最短路
代码实现：拓扑排序
DP的核心思想：尽量缩小可能解空间
DP三连：我是谁？我从哪里来？我要到哪里去？
DP 问题思路
主要就是确定「DP 状态」与「DP 转移方程」
DP状态：n->i 确定「DP 状态」
符合「最优子结构」原则：DP 状态最优值由更小规模的 DP 状态最优值推出
符合「无后效性」原则：状态的得到方式，不会影响后续其它 DP 状态取值
确定「DP 转移方程」
注：分类讨论，细心枚举
步骤
1.建立状态转移方程：当作已经知道f(1)~f(n-1)的值，利用它们求得f(n)。
2.缓存并复用以往结果：从f(1)~f(n-1)
3.按顺序从小往大算：从f(1)~f(n)依次计算
三种情况使用动态规划：（90%使用)
- 求最大/最小值
- 求可不可行
- 求方案总数
动态规划可以分为如下四大类：
线性动规，区域动规，树形动规，背包动规。
例题
给出一个数字三角形，从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
示例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
示例输出
27
代码（java）import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int a[][] = new int[200][200];//存储各个数字的大小
int c[][] = new int[200][200];//存储到各个数字的最大路径
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
a[i][j] = scan.nextInt();
c[1][1]=a[1][1];//第一步
//按顺序求到每个数的最大路径
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
c[i][j]=a[i][j]+Math.max(c[i-1][j],c[i-1][j-1]);
//输出最后一行最中间的那个数的最大路径
System.out.println(Math.max(c[n][(n+1)/2],c[n][(n+2)/2]));
}
}
