动态规划之数字三角形

数字三角形 

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

                   1

                2     3

           4       5       6

     7         8      9        10

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

一个n层数字三角形的完整路线有2^(n-1)条，当n很大时再一个个去求会很麻烦，为了得到高效的算法，需要用抽象的方法思考问题：把当前的位置(i,j)看做一个状态，然后定义状态(i,j)的指标函数d(i,j)为从格子(i,j)出发时能得到的最大和(包括(i,j)本身的值)，在这个状态定义下，原问题的解是d(0,0)。

于是得到状态转移方程

d(i,j)=a(i.j)+max{d(i+1,j),d(i+1,j+1)}

动态规划的核心是状态和状态转移方程。

记忆化搜索和递推

方法一：递归计算

int solve(int i,int j)

{

    return  a[i][j] + (i==n ? : max( solve(i+1,j),solve(i+1,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]+ max(d[i+1][j],d[i+1][j+1]);

程序的时间复杂度为 O(n^2)，但为什么可以这样计算呢？，原因在于i是逆序枚举的，在计算d[i][j]时它所需要的d[i+1][j],d[i+1][j+1]已经计算出来了。

方法三：记忆化搜索。

程序分为两部分，首先用“memset”把d全部初始化为-1，然后编写递归函数：

int solve(int i,int j)

{

      if(d[i][j]>=0)   return d[i][j];

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

上述程序依然是递归的，但同时也把计算结果保存在数组d中。题目中说各个数都是肺腑的，因此如果已经计算过某个d[i][j]，则它应是非负的。这样，只需要把所有d初始化为-1，即可通过判断是否d[i][j]>=0得知它是否已经被计算过。最后把它保存在d[i][j]中。