理解动态规划
直到现在个人还是觉得动态规划是挺难理解和做题的，所以这一篇文章不去引用很多的概念，就仅仅谈一谈自己对于动态规划的理解，以及做题的思路
动态规划
我们小时候上学的时候，从家到学校的方案应该有多种，假如某一天你想知道走哪一条路最快到学校，走哪一条路最慢，走哪一条路风景最好，该怎么办呢？
路线图如下，A是家，H是学校。其中BCDEFG属于超市，池塘等地方。假设我们现在想知道哪条路线最快到学校，防止以后起床晚了不知道走哪条路。
D----E----
/ \ \
/ \ \
A---->B----F----H
\ / / /
\ / / /
C----G-----其实知道哪个最快，最简单的方案就是都走一遍就知道了，一共要走的路线方案如下:
方案一：A->D->E->H
方案二：A->D->E->F->H
方案三：A->B->F->H
方案四：A->C->G->F->H
方案五：A->C->B->F->H
方案六：A->C->G->H如果我们每次都是在A开始计时，到H结束计时，那么各个路线哪个时间短，哪个就最快，也就达到我们的目标。这种方案我们叫做穷举法。
但是各位看官，我们审视一下上面的路线，A->C我们是不是走了三次，A->D走了两次，D->E走了两次，C->G走了两次，F-H走了三次。作为了一个懒人，如果我们在上面方案二走过F->H之后，你测试方案三/方案四的时候，你走到F，你还想走到H吗？肯定不想啊，刚走过，又要走， 我们就是为了偷懒才找最短路线的，现在找最短路线竟然不偷懒，这怎么说的过去。
所以，懒人的我们改变了策略，计时不从头到尾，每到一个地方我就结束计时，这样我第一次走过F->H就知道F->H要耗时，那么我在走方案三的时候 F->H就不走了，因为我已经记录F->H需要多久。这种方案我理解就是动态规划，把已经走过的地方存储下来，然后找到相应的规律就可以推导出最优的方案。
看完这，我们看看动态规划的专业解释
基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多， 有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算， 节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式
状态转移方程
状态转移方程，是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第K阶段的状态Sk以及决策uk(Sk)，则第K+1阶段的状态Sk+1也就完全确定， 一般来说，状态转移方程是我们实现动态规划最难的一步。
适用条件
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言， 余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3.子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中， 不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
看完这些我们来看一个例子，学习一下动态规划解决实际问题
数字三角形
1 第一层
2 3 第二层
11 10 12 第三层
9 7 15 24 第四层 在上面的数字三角形中寻找一条从顶部(第一层)到底边的路径，使得路径上所经过的数字之和最小。
个人有两种方案一种从第一层到第四层寻找最优解，一种是第四层往第一层最优解。
方案一:
路径上的每一步都只能往左下或 右下走也就是 2 只能到11和10，3只能到10和12。
这跟我们第一部分找最省时的例子相似，可以采用穷举法去搞定，但是有很多无效的路程(已经走过)。
这里我们使用dp[i][j]表明某i+1层，第j+1位数到达底部的之和(案例中的计时)。
那么我们看
d[0][0]=1
d[1][0] = 2 d[1][1] =3
d[2][0] = 13 d[2][1]=(d[1][0] 和 d[1][1]最小值) +d[2][1]
......
我们会发现，后面每一个位置对应的最小值，都是上一层中可到达该位置的最小值加上该位置大小本身，于是得到状态转移方程
d[i][j] = d[i][j]; i=0,j=0 d[i][j] = d[i-1][j]+d[i][j]; i!=0,j=0 d[i][j] = d[i-1][j-1]+d[i][j]; i=j d[i][j] = min{d[i-1][j-1],d[i-1][j]}+d[i][j];i>1,j>1
方案二：
我们初始化第四层，然后从第三层依次往上取:
d[3][0] = 9 d[3][1] = 7 d[3][2] =15 d[3][3] = 24
d[2][0] = min{d[3][0],d[3][1]}+d[2][0]
......
得到状态转移方程为:
d[i][j] = min{d[i+1][j],d[i+1][j+1]}+d[i][j]
看完公式，我们写代码就简单了。
实现代码(C++)
//
// main.cpp
// TheTriangle
//
// Created by 陈龙
// Copyright © 2019 陈龙. All rights reserved.
//
#include <iostream>
using namespace std;
bool cmp(int a,int b){
return a<b;
}
int main(int argc, const char * argv[]) {
// insert code here...
int N;
cin>>N;
int dp[N][N];
for (int i=0; i<N; i++) {
for (int j=0; j<=i; j++) {
cin>>dp[i][j];
// cout<<" "<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
}
for (int i=1; i<N; i++) {
for (int j=0; j<=i; j++) {
if (j==0) {
dp[i][j] = dp[i-1][j]+dp[i][j];
}else if(i==j){
dp[i][j] = dp[i-1][j-1]+dp[i][j];
}else{
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j],cmp)+dp[i][j];
}
}
}
for (int i=0; i<N; i++) {
for (int j=0; j<=i; j++) {
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
/*
4
1
2 3
11 10 12
9 7 15 24
*/