数字三角形（数塔问题）
其实动态规划本身并不是一个特定的算法，是一种用途广泛的问题求解方法，一种思想，一种手段。
1.1问题描述与状态定义
有一个有非负整数组成的三角形，第一行一个数字，下面各行除了最后一行外，每行的每个数字下面左右各一个数字。
如图示：
从第一行数字开始，每次只能走左下或右下一格，直到走到最后一行，把沿途的走过的所有数字加起来。
如何能使这个和最大？
【问题复杂度分析】如果熟悉回溯法，就会立即发现这是一个动态的决策问题：每次两个选择----左下或右下。
但是如果选择用回溯法解决此问题，惯常的问题就是效率太低：一格n层的数字三角形的完整路线有2^n条，所以当n很大时完全不能靠此方法。
因此为了提高效率，需要把此问题抽象：把所有的位置（i，j）抽象为一个个不同的状态，然后定义状态（i，j）的指标函数d（i，j）为从格子（i，j）出发时能得到的最大的和（包括此格子本身）。在这个定义下，原问题的解是d（1,1）。
如下图：
【状态转移分析】从格子（i,j）出发有两种决策。若往左走，则走到（i+1,j）后续要求“从（i+1,j）出发后能得到的最大和“这一问题，即是d（i+1,j）。类似的，往右做之后要求解d（i，j+1）。由于这两个选择自由可选，所以，应该选择较大的。即得到了所谓的状态转移方程：
d(i,j) = a(i,j) + max { d(i+1, j), d(i, j+1) }
最优子结构：如果往左走，最好的情况是(i,j)格子里面的值a(i,j) 与”从（i+1,j）出发后能得到的最大和"之和， 注意"最大"两个字,如果从(i，j)出发到底部这部分都不是最大的话，加上a(i,j)也必然不是最大的。这就是最优子结构。或描述全局最优解包含局部最优解。
【总结】动态规划的核心是状态和状态转移方程。
1.2 解决方法：记忆化搜索与递推
方法一：递归计算
代码如下：（注意边界）
int d(int i, int j)
{
return a[i][j] +( i == n ? 0 : d(i+1, j) >? d(i, j+1) ) ;
}
如此计算正确只是效率依然不高，问题在于重复计算。就是一些格子被两个父节点所共有，所以，在递归的时候，便会被重复计算。
方法二： 递推计算
代码如下：
（注意此时重复边界的处理）
int i, j;
for (j=1; j<=n; j++)
d[n][j] = a[n][j] ;
for (i=n-1; i>=1; i--)
for (j=1; j<=i; j++)
{
d[i][j] = a [i][j] + d[i+1][j] >? d[i][j+1] ;
}
时间复杂度显然是O(n^2),
可以如此计算的原因在于：
i是逆序枚举的，因此在计算d[i] [j] 之前，他所需要的d[i+1][j] 和 d[i][j+1] 已经计算出来了。
提示：在多数情况下，可以采用递推法计算状态转移方程。递推的关键在于边界和计算顺序。多数情况下，递推法的时间复杂度是：状态转移方程X每个状态的决策数X决策时间。
方法三：记忆化搜索
程序分为两部分。首先用数组函数memset（）;将数组整体置为-1，然后写递归函数：
int d(int i, int j)
{
if(d[i][j >= 0) return d[i][j] ;
return d[i][j] = a[i][j] +( i == n ? 0 : d(i+1, j) >? d(i, j+1) ) ;
}
依然是递归函数，同时把计算结果存在数组d中。题目说各个数字均为非负数，因此如已经计算过某个d[i][j],那么期应该是非负数。 这样只需要把所有的数组元素初始化为负数，如-1，就可以知道是否计算过d[i][j].
注意：不要忘记把结果存在数组d[i][j]中。根绝c语言的”赋值语句本身有返回值“的规定，可以把保存d[i][j]的工作整合在函数的返回语句中。
上述的方法三称为记忆化，虽然不像地推算法那样显示的指明了计算的顺序，但是任然可以保证每个节点只访问了一次。
由于i和j都在1~n之间，所以所有的不同的节点之间一共有O(n^2)个。即是时间复杂度。
提示：可以用记忆化搜索的方法计算状态转移方程。采用记忆化搜索时，不必事先确定个状态的计算顺序，但需要记住每个状态是否计算过。
1.3程序实战练手
HDOJ--2084
未完待续...................
下一节：DAG上的（DP）