能采用動態(tài)規(guī)劃求解的問題的一般要具有 3 個性質(zhì)：

最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。

無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關(guān)。

有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）

解題步驟：

1.  拆分問題

2.  定義狀態(tài) (并找出初狀態(tài))

3.  狀態(tài)轉(zhuǎn)移方程

題目講解：

C 題數(shù)塔問題

有如下所示的數(shù)塔，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點，則經(jīng)過的結(jié)點的數(shù)字之和最大是多少？ 

我們知道，從定點開始每次只有兩個方向，左下和右下，要想知道如何走才能得到最大值，我們只需要知道它的兩個子節(jié)點的如何走才能得到最大值，相同的情況我們又可以問它的子節(jié)點的子節(jié)點，這樣重復(fù)下去一直都愛最后一行。

故最后的狀態(tài)轉(zhuǎn)移方程式   dp [i][j] = num [i][j] + max (dp [i+1][j], dp [i+1][j+1]); 注意這是倒推的，就好像我們只有知道了地 i+1 個才能知道第 i 個。仔細想一想為什么遞推完成后 dp [1][1] 就是最大值呢？（從循環(huán)條件中找答案）

#include

using namespace std;

const int MAXN = 100+10;

int num[MAXN][MAXN];

int dp[MAXN][MAXN];

int main()

{

    int t;

    scanf("%d", &t);

    while( t-- )

    {

        memset(dp, 0, sizeof(dp));

        int n;

        scanf("%d", &n);

        for( int i=1; i<=n; i++ )

        {

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

                scanf("%d", &num[i][j]);

        }

        for( int j=1; j<=n; j++ )

            dp[n][j] = num[n][j];

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

        {

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

             {

                 dp[i][j] = num[i][j] + max(dp[i+1][j], dp[i+1][j+1]);

             }

        }

        printf("%d\n", dp[1][1] );

    }

    return 0;

}