数字三角形问题

问题描述：

有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数。

从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？

如下图：

1

3   2

4  10  1

4   3   2   20

思考：把当前的位置（i，j)看成一个状态，然后定义状态（i,j）的指示函数d(i,j)为从格子(i,j)出发时能得到的最大和(包括格子(i,j)本身的值）。在这个状态定义下，原问题的解释d(1,1)。

状态状态转移：从格子(i,j)出发有两种决策。如果往左走，则走到(i+1,j)后需要求”从(i+1,j)出发后能得到的最大和”这一问题，即d(i+1,j)。类似的，往右走之后需要求解d(i+1,j+1)。

所以状态转移方程就是d(i,j)=max{d(i+1,j)，d(i+1,j+1)}+a(i,j);

方法一：递推计算 （时间复杂度为O(n^2))

inti,j;

for(i=1; i<=n; ++i)//下标从1开始

d[n][i]=a[n][i];

for(i=n-1; i>=1; --i)

{

for(j=1; j<=i; ++j)

d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);

}

因为i是枚举的，因此在计算 d[i][j] 前，它所需要的d[i+1][j]和d[i+1][j+1]一定已经计算出来了

方法二：记忆化搜索(时间复杂度O(n^2)  首先memset(d,-1,sizeof(d))  将d全部初始化为-1

intsolve(inti,intj){

if(d[i][j]>0)returnd[i][j];

returnd[i][j] = a[i][j] + ( i==n ? 0 : max(solve(i+1, j), solve(i+1, j+1) ) );

}

题目中各个数都是非负的，这样只需要把d初始化为-1，即可通过判断是否d[i][j]>=0得知它是否已经被计算过。

来自http://blog.csdn.net/eagle_or_snail/article/details/51019088