动态规划 例题一、数字三角形(POJ1163)
1、问题描述
在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于1小于等于100，数字为 0 - 99。
- 输入格式：
2、解题思路
有输入结构可以使用一个二维数组去存放数字三角形。
而解题思路也很容易想到使用递归。（如下）
数字三角形的递归程序:
递归程序实现存在的问题：
题目中数字三角形最多是100层，那么采用上述递归程序的时间复杂度是 2^100, 严重超时。
原因如下图：
重复计算。
如图，计算第一层数字(0,0)时, 只需计算第二层(1,0)/(1,1),取最大值 + (0,0) 但是，计算第二层最大值时，分别计算（1，0）和 （1，1）时，同时都会计算一次（2，1）的最大值。也就是计算了两次。 依次，计算（2，0）会调用一次(3，1),而上面（2，1）被计算了两次，所以（3，1）又会被计算2次，一共计算3次。 。。。。。 一次重复计算的次数不断增加。 从上递加 1 + 2 + 4 + 8 。。。。 = 2^100
递归程序改进：
将每次计算出的（i，j）的最大值保存起来，避免重复计算。
这样一个数组，叫做记忆数组。这样的递归叫做 记忆性递归。
仍然可能的问题：
递归栈的溢出，100层的栈。
3、 不使用递归的实现思路： 动态规划方法
首先看一下思路：
如图，不使用递归的实现方式。
定义一个最大值的数组，(i,j)上定义的就是从（i,j）到底部的最大值。
那么最后一行本身就是最大值本身。
而第二行的取值则是前面一行的最大值 + 自身的值。
以此类推直至最顶一行。
所以，可以从最低一行开始计算，不断更新上一层的最大值，最后递推到最顶一行。
这样的实现方式并没有使用到递归。
实现思路：
如上图， 叫 人人为我 的递推思路。
什么是人人为我？ 以本例来说，求(i,j)点的最大路径值的时候，是要先计算(i+1, j) 和 （i+1， j+1）的最大值，也就是
就算这两个点就是为(i,j)服务的，这就是人人为我。
优化思路：
空间优化：
- 上面用的是一个二维数组，存放的每个点的最大路径值。
其实，上一层的最大路径值只依赖于下一层的最大路径值，第i层求出之后，第i+1层就没用了。
所以可以只定义一个一位数组， 每次按index刷新最大值。
也就是 (i,j)点的最大值会替换掉(i+1,j)点的最大值，存放在a[i]处。
如图，不断去刷新数组的最大值，最终顶点的最大值就是a[0];
- 空间再优化：
一维数组也没必要用，因为一维数组的初始值就是三角形的最后一行。
所以直接覆盖三角形的最后一行即可。
4、总结
- 递归转换为动态规划的方法：
1、递归有n个参数，就定义一个n维数组；
本例递归参数（i,j）,所以定义一个二维数组， 实际意义是坐标值。
2、数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值。
本例数组下标的范围是坐标的范围，数组元素的值是函数返回的最大路径值。
3、数组的填充方式
从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。
总结（我的大白话）：
1、动态规划的实现就是先找到一个正确的数组。 仅限于能够用递归实现的动态规划；
2、如本例，知道了数组元素的意义，是每个对应坐标的最大路径值。
但是还是得有填充方式，就是从已知的条件填充数组，知道填满找到所求的值。
3、说递归式动态的逆过程，其实递归最终还是压栈之后按照动归的顺序计算的。
- 什么样的问题可以考虑动态规划的解法？
两个条件同时满足：
1、 问题具有最优子结构性质。
本例，(i,j)的最大值是取(i+1,j)和（i+1, j+1）的最大值的最大值。
也就是问题、子问题都是取得最优的，叫做最优子结构。
2、 无后效性。
当前的若干个状态值一旦确定，
则此后过程的演变就只和这若干个状态的值有关，
和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
无后效性,也就是所谓的“未来与过去无关”。
本例，(4,3)点的最大路径求出之后，(3,3)点肯定会用，但是(3,3)点用(4,3)的结果时不会考虑这个点的结果是通过哪个方式得到的，
递推还是递归，也就是那已经是过去式了，不影响现在的结果。
- 动规解题的一般思路
1. 将原问题分解为子问题 (重点是子问题求出之后会被保存)
把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。
子问题都解决，原问题即解决(数字三角形例）。
子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。
2. 确定状态
在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。
一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。
所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。
在数字三角形的例子里，一共有N×(N+1)/2个数字，所以这个 问题的状态空间里一共就有N×(N+1)/2个状态。
整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。
在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。
（所以这里所说的状态是不是可以理解为是一个子问题的解，或者在本例中(i,j)就是一个状态，即每一个坐标点就是一个状态）
重点（结合本例就是二维数组，这个数组的值就是一个子问题的解）：
用动态规划解题，经常碰到的情况是，K个整型变量能构成一个状态（如数字三角形中的行号和列号这两个变量构成“状态”）。
如果这K个整型变量的取值范围分别是 N1, N2, ……Nk，那么，我们就可以用一个K维的数组 array[N1] [N2]……[Nk]来存储各个状态的“值”。
这个 “值”未必就是一个整数或浮点数，可能是需要一个结构 才能表示的，那么array就可以是一个结构数组。一个 “状态”下的“值”通常会是一个或多个子问题的解
3. 确定一些初始状态（边界状态）的值 （重点： 就是根据已知条件来填充数组）
以“数字三角形”为例，初始状态就是底边数字，值就是底边数字值
4. 确定状态转移方程 （重点：还有我为人人）
定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”(“人人为我”递推型)。
状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。
数字三角形的状态转移方程: array[i][j] = max(array[i+1][j], array[i+1][j+1]) + (i,j)
其中，array[i][j]就是(i，j)的状态，这是状态是计算得到然后填充到数值中的， (i,j)是坐标本身的值。
