初識DP動态規劃

一、多階段決策過程的最優化問題

在現實生活中,有類活 動的過程，由于 它的特殊性，可将過程分成若幹個互相階段。在它的每一階段都需要作出決策,進而使整個過程達到最好的活動效果。當階段決策的選取不是任意确定的，它依賴于目前面臨的狀态,又影響以後的發展，當段決策确定後，就組成一個決策序列,因而也就确定了整個過程的一條活動路線,這個問題看作是個前後關聯具有鍊狀結構的 多階段過程就稱為多階段決策過程，這就稱為多階段決策問題。

多階段決策過程,是指這樣的一類特殊的活動過程,問題可以按時間順序分解互聯系的階段，在每-個階段都要作出決策,全部過程的決策是-個決策序列。

二、能采用動态規劃求解的問題的一般要具有3個性質：

最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

無後效性：即某階段狀态一旦确定，就不受這個狀态以後決策的影響。也就是說，某狀态以後的過程不會影響以前的狀态，隻 與目前狀态有關。

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

1. 拆分問題
2. 定義狀态(并找出初狀态)
3. 狀态轉移方程

#include <bits/stdc++.h>
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;
}