發表新討論
#49995: 區間dp


BensonDC (python戰士)

學校 : 不指定學校
編號 : 240921
來源 : [42.75.77.11]
最後登入時間 ：
2025-09-09 07:58:17
m934. 4. 合併成本 -- 2024年1月 APCS
| From: [114.39.10.251] | 發表日期: 2025-08-01 20:27

區間dp

                                                                                                                                                                                                                                    

題意:

給定長度為n的序列，每次可以將相鄰兩元素合併，所需代價為兩數合併的差值(絕對值)，合併後的數為兩數相加

解法: 

典型的區間 dp 問題

類似於這種 合併、分割、刪除或重新排列一段連續子區間的最小/最大代價 類型的題目都是區間dp問題

最常使用的解題策略就是 遞迴分治+記憶化搜索 ，大範圍問題拆分成若干小範圍進行求解

 

首先 思考遞迴狀態要怎麼定義

我們可以令f(l, r)表示將區間 l 到 r 合併成 1 個數字所需的最小花費

接著 定出邊界條件

當 l==r 時: 無須合併，所需代價為 0

當 l+1==r 時: 兩數合併，所需代價為兩數之差

最後 找出問題與子問題之間的(遞迴)關係

對於長度為 n 的序列，可以將它劃分為兩個區間 左區間與右區間

所需代價就是 sum(左區間)和sum(右區間)的絕對值差 + 左右區間合併的成本

為了求得最優解，我們對區間每個劃分點都嘗試將他分割求解

既然知道了這些，我們就不難列出他的轉移方程式

f(l, r) = min( abs(區間和左 - 區間和右) + f(l, i) + f(i+1, r) ) i 從 l 枚舉到 r-1

以上就是遞迴求解的作法了，最後掛個二維陣列dp做記憶化搜索

定義dp[ l ][ r ]表示區間 l 到 r 的合併代價，陣列全部初始化為-1表示還沒訪問，陣列會在遞迴過程中紀錄答案

最後區間和的部分，事先處理前綴和陣列即可輕鬆搞定

 

複雜度

枚舉每個區間 l, r 的答案，需要 O(n2)

對f(l , r)每個劃分點求解，需要 O(n)
合計 O(n3)

 

關鍵代碼

function<int(int, int)> dfs = [&](int l, int r)
    {
        if (dp[l][r] != -1)
            return dp[l][r];
        if (l == r)
        {
            dp[l][r] = 0;
            return dp[l][r];
        }
        if (l + 1 == r)
        {
            dp[l][r] = abs(A[l] - A[r]);
            return dp[l][r];
        }
        else
        {
            int ans = INF;
            for (int i = l; i < r; i++)
            {
                ans = min(ans, abs((pA[i] - pA[l - 1]) - (pA[r] - pA[i])) + dfs(l, i) + dfs(i + 1, r));
            }
            dp[l][r] = ans;
            return dp[l][r];
        }
        return dp[l][r] = 0; // Fallback return, should not be reached
    };

 

 

 

ZeroJudge Forum