【动态规划1】入门问题 数塔
动态规划（DP）问世以来，在工农业生产、经济、军事、工程技 术等许多方面都得到了广泛的应用，取得了显著的效果。是信息学领域的一个很大的分支，学的时候一开始会觉得完全没头绪，但是在接触的不同类型题目多了以后，丰富的经验能起到很大作用。同时动态规划可以与许多算法结合，从基础到难度较高的水平是一个长期的经验积累过程。
01.
写在正式讲解之前
先回答这道题：
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=？
你会掰着指头告诉我等于15.
然后回答这道题：
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=？
你会告诉我等于16.
为什么这回快多了？
★因为前面的已经算过了啊★
事实上有个东西和动态规划很像，或者可以说是动态规划的简化版，就是递推。
【爬楼梯问题】
有一个n阶的楼梯，每次可以一步跨1阶或者2阶，那么从1阶跨到n阶总共有几种方案？（详细见文章数楼梯问题）。
接下来，我们以一道树塔问题展开讲解动态规划问题。
02.
树塔问题
要求从数塔顶层出发，每个结点可以选择向左走或向右走，要求一直走到塔底，使得走过的路径上的数值和最大，如下图所示，最大一条路径的权值为86（题目只要求输出最大权值，不要求输出路径）。
【题目背景】
本题来源是国际信息学奥林匹克竞赛1994年原题，作为动态规划题，本题是“麻雀虽小五脏俱全”，加上简单易懂的背景，往往是许多初学者接触动态规划的第一题。
【初步分析】
首先，从上往下走时每次有两种选择，初学者可能会想到利用“贪心法”解决，也就是每次选择更大的一个值，但也显然这种做法是错的，如图中的例子，采取贪心法就会被误导到错误的答案。
【“递推”算法】
为了方便讲解，我们将三角形编码成一个矩阵，其中节点13代表上往下数的第1行第1个，节点11代表第2行第1个，节点8代表第2行第2个……（全部编码如下图所示，第x行第y个的点我们用（x，y）表示，并且矩阵用二维数组a[][]进行存储）
我们是自顶向下走的路径，为了方便思维，我们先将问题反过来考虑，变为自底向上，走出一条最大的权值和。
现在，我们假设当前的路径已经走到了最上面的一层，显然，这一步应该是从左边的（2，1）或者右边的（2，2）走上来的。
我们令F[x][y]表示走到（x，y）时，已经得到的最大权值，则F[1][1]表示走到（1，1）点时的最大权值，那么结合上一段话，我们得出一个公式：
F[1][1] = MAX(F[2][1]+F[2][2]) + 13
解释：（1，1）点的最大值，由（2，1）点或（2，2）中较大的一个走上来，再加上自身的权值13得到。
这是整个算法最为核心的地方。这一步想通了，后面就好办了。
我们可以根据这个公式推出所有点的公式，即：
F[x][y] = MAX(F[x+1][y]+F[x+1][y+1]) + a[x][y]
这颇像递推的一步，其实就是动态规划的本质。
【递推→动态规划】
上面这个公式：
F[x][y] = MAX(F[x+1][y]+F[x+1][y+1]) + a[x][y]
叫做状态转移方程，对于F[x][y]，我们称之为状态，而更前面点的F[x+1][y]和F[x+1][y+1]，我们称之为子状态。这是动态规划的最核心要素，其本质就是一个递推式，当然区别还是有的，递推式往往没有诸如“MAX”这类函数，换言之，没有选择，而动态规划却往往需要在多个子状态之间选择一个最优的子状态。
【动态规划的实现】
第二个关键点：如何实现代码？
我们想知道F[1][1]，就必须知道F[2][1]和F[2][2]，但是F[2][1]和F[2][2]并不知道啊，所以要知道F[2][1]，又必须知道F[3][1]和F[3][2]，要知道F[2][2]必须知道F[3][2]和F[3][3]……如图所示。
这看似套娃的过程，就是动态规划的迭代过程，那么什么时候是个头呢？
显然，当来到最底层（第5层）的时候，所有的F[x][y]其实就是对应的格子中的数字，因为我们已经将问题修改为从底层出发，那么底层的权值自然只有一个数字了。
前面的分析中，已经涉及了动态规划的另外两个要素：迭代方式和初始状态。
应该能发现，在求第x层时，第x+1层的所有状态我们必须都求出来，所以在循环到x层时，x+1层的所有状态一定要先被循环处理，这样一来循环的顺序就理出来了吧，x应该从最后一层倒着循环上来。
那么y的循环顺序呢？也就是说在同一行的循环顺序，大家稍微思考一下会发现，无所谓的，从左往右和从右往左都可以，因为互相之间并没有什么利用关系，在这一行的计算只与下面一行有关，与同一行的状态相互独立。
这种情况，我们的循环顺序主要取决于x，每一个x我们称之为一个阶段，只有当前阶段的所有状态都迭代出来了，才能进入下一个阶段。
最后是初始值，递推总得有个开始，由初始状态一层一层迭代得到答案，那么初始状态下的F是什么呢？容易想到初始时是在最底层，也就是F[5][1]，F[5][2]，F[5][3]，F[5][4]，F[5][5]，而这些值刚好就是对应的a数组的值。
其实这道题的初始状态不用做任何处理，为0就可以了，只要阶段从最底层开始。因为在最底层时，所有的F[5][y]都可以由第6层的元素得到，而第6层的F数组实际上是空的，不会影响到答案，只会加上当前第5层的a数组，刚好省去了手动初始化的过程。
03.
代码
a = [[0]*7 for i in range(7)]f = [[0]*7 for i in range(7)]a = [[0, 0, 0, 0, 0, 0, 0],[],[],[],[],[],[],]for x in range(5, 0, -1): //层数要倒着来for y in range(1, 6):f[x][y] = max(f[x+1][y], f[x+1][y+1])+a[x][y]print(f[1][1])
04.
小结
所以对于动态规划，我们可以理一下解决思路：
1.找到合适的状态，例题中就以F[x][y]作为状态，表示最优值
2.根据状态找出状态转移方程，一旦到这步问题基本已经解决了
3.确定循环的阶段，明确迭代过程
4.确定循环前的状态初始值
这就是动态规划的4个基本要素。
动态规划的学习的是一个漫长的过程，其分类较多（当然在真正的高手眼中只有几种，而事实也是如此，说明动态规划的学习更多的不一定是大量的刷题，而是主动分析不同题目之间的联系寻找规律进行整理）。