區間dp學習筆記

例題1：洛谷 P1775

我們可以設 dp[l][r] 為將區間 [l,r] 區間內的所有石子都合併成一堆時造成的最小代價。

如何求出 dp[l][r] 呢？此時我們可以枚舉一個斷點 k，把 [l,r] 區間分成兩個區間：$[l,k]$ 和 [k+1,r]，很明顯，k  ∈ [l,r-1]

現在就很容易推出狀態轉移方程了。也就是把 [l,k] 合成一堆石子花費的代價加上 [k+1][r] 合成一堆石子花費的代價加上 [l,r] 區間石子個數的總和（也就是把這兩個區間各自合成一堆後再合成產生的代價）

此時我們可以使用一個首碼和數組 sum[i]，來表示區間石子的總和。 

轉移方程：dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1])

#include<iostream>
#include<string.h>
using namespace std;
int n;
int a[310];
int sum[310];
int dp[310][310];
int main (){
    memset(dp, 0x3f, sizeof(dp));
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        dp[i][i] = 0;//只有一堆不需要代價
    }
    for(int len = 2; len <= n; len ++){
        for(int l = 1; l + len - 1 <= n; l ++){
            int r = l + len - 1;
            for(int k = 1; k <= r - 1; k ++){//斷點
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + (sum[r] - sum[l - 1]));
            }
        }
    }
    cout << dp[1][n];
    return 0;
}