數字三角形 

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

                   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]中。