數(shù)字三角形 

有一個(gè)由非負(fù)整數(shù)組成的三角形，第一行只有一個(gè)數(shù)，除了最下行之外每個(gè)數(shù)的左下方和右下方各有一個(gè)數(shù)。

                   1

                2     3

           4       5       6

     7         8      9        10

從第一行數(shù)開(kāi)始，每次可以往左下或右下走一格，直到走到最下行，把沿途經(jīng)過(guò)的數(shù)全部加起來(lái)。如何才能使得這個(gè)和盡量大？

一個(gè)n層數(shù)字三角形的完整路線有2^(n-1)條，當(dāng)n很大時(shí)再一個(gè)個(gè)去求會(huì)很麻煩，為了得到高效的算法，需要用抽象的方法思考問(wèn)題：把當(dāng)前的位置(i,j)看做一個(gè)狀態(tài)，然后定義狀態(tài)(i,j)的指標(biāo)函數(shù)d(i,j)為從格子(i,j)出發(fā)時(shí)能得到的最大和(包括(i,j)本身的值)，在這個(gè)狀態(tài)定義下，原問(wèn)題的解是d(0,0)。

于是得到狀態(tài)轉(zhuǎn)移方程

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

動(dòng)態(tài)規(guī)劃的核心是狀態(tài)和狀態(tài)轉(zhuǎn)移方程。

記憶化搜索和遞推

方法一：遞歸計(jì)算

int solve(int i,int j)

{

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

}

這樣做是正確的，但是時(shí)間效率太低，其原因在于重復(fù)計(jì)算。

方法二：遞推計(jì)算。

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]);

程序的時(shí)間復(fù)雜度為 O(n^2)，但為什么可以這樣計(jì)算呢？，原因在于i是逆序枚舉的，在計(jì)算d[i][j]時(shí)它所需要的d[i+1][j],d[i+1][j+1]已經(jīng)計(jì)算出來(lái)了。

方法三：記憶化搜索。

程序分為兩部分，首先用“memset”把d全部初始化為-1，然后編寫(xiě)遞歸函數(shù)：

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) );

上述程序依然是遞歸的，但同時(shí)也把計(jì)算結(jié)果保存在數(shù)組d中。題目中說(shuō)各個(gè)數(shù)都是肺腑的，因此如果已經(jīng)計(jì)算過(guò)某個(gè)d[i][j]，則它應(yīng)是非負(fù)的。這樣，只需要把所有d初始化為-1，即可通過(guò)判斷是否d[i][j]>=0得知它是否已經(jīng)被計(jì)算過(guò)。最后把它保存在d[i][j]中。