動態規劃 (DP) 經典題目狀態轉移方程總結

前言

動態規劃沒有通用的「萬能公式」，核心在於**定義狀態**與**推導狀態轉移方程**本文整理 5 道 POJ 經典題目，展示從問題建模到方程推導的完整思路，幫助建立 DP 直覺。

題目 1：POJ 1160 - 郵局

問題

直線上有 V 個村莊，座標遞增。需建立 P 個郵局，使所有村莊到最近郵局的**距離總和最小**。

狀態定義

• dis[i][j]：在第 i~j 村莊間建**一個**郵局的最小距離和。最優位置在中位數村莊。
• dp[v][p]：前 v 個村莊建 p 個郵局的最小距離和。

轉移方程

dp[v][p] = min_{p-1 ≤ i < v} ( dp[i][p-1] + dis[i+1][v] )

枚舉第 p 個郵局服務的起始村莊 i+1，前 i 個村莊由 p-1 個郵局服務。

複雜度

預處理 dis 為 O(V^2)，DP 為 O(V^2 P)。可用四邊形不等式優化至 O(V P)。

題目 2：POJ 1260 - 珠寶購買

問題

C 種珠寶，品質遞增。第 i 種需購 n_i 顆，單價 p_i。購買第 i 種實際花費 (n_i + 10) * p_i。高品質可替代低品質。求最小總花費。

狀態定義

• num[i]：前 i 種珠寶總需求量 Σ n_k。
• dp[i]：購買前 i 種珠寶的最小花費。

轉移方程

dp[i] = (num[i] + 10) * p_i                          // 全買第 i 種
dp[i] = min(dp[i], dp[j] + (num[i] - num[j] + 10) * p_i)  // j < i，前 j 種自買，其餘用 i 種替代

關鍵洞察

「高品質替代低品質」意味著決策點只需決定**最後一種自購的珠寶**，之前的或自購或被替代。

題目 3：POJ 1276 - 現金支付

問題

有 n 張鈔票，面值 d_i，張數 a_i。湊出最接近 M 且不超過的總值。

轉化

多重背包 → 二進制拆分或單調隊列優化 → 01 背包。

狀態與方程

bool dp[M+1] = {false}; dp[0] = true;
for each 拆分後的物品 value v:
    for k = M down to v:
        dp[k] = dp[k] || dp[k-v];

最後從 M 向下掃描第一個 true 即答案。

題目 4：POJ 1745 - 可除性

問題

數列 a[1..N]，相鄰兩數間可放 + 或 -。問是否能使最終結果能被 K 整除。

狀態定義

dp[i][r]：前 i 個數運算後，模 K 餘數為 r 是否可達成。

轉移方程

dp[i][r] = dp[i-1][(r - a[i]) mod K]  // 放 +
        || dp[i-1][(r + a[i]) mod K];  // 放 -

注意負數取模修正：(x%K + K) % K。

初始/答案

dp[1][a[1]%K] = true；檢查 dp[N][0]。

題目 5：POJ 1837 - 天平平衡

問題

G 個砝碼，重量 g[i]；C 個掛鉤，位置 c[j] (左負右正)。將每個砝碼掛在一個鉤上，使力矩總和為 0。求方案數。

狀態定義

dp[i][torque]：掛前 i 個砝碼後，力矩為 torque 的方案數。

偏移技巧

力矩可負，最大絕對值 MAX = max(g) * max(|c|) * G。陣列索引偏移 SHIFT = MAX，實際索引 torque + SHIFT。

轉移方程

for i = 1..G:
    for j = 1..C:
        for t = -MAX..MAX:
            if dp[i-1][t+SHIFT] > 0:
                dp[i][t + g[i]*c[j] + SHIFT] += dp[i-1][t+SHIFT];

答案

dp[G][SHIFT] (力矩 0 的方案數)。

總結：DP 解題三步曲

1. 定義狀態：用最少參數描述子問題，「前 i 個」、「容量 j」、「餘數 r」、「力矩 t」等。
2. 推導轉移：考慮最後一步決策（選/不選、放哪、掛哪），從子問題構建當前問題。
3. 確定邊界與順序：初始狀態、迴圈順序（正向/逆向）、空間優化（滾動陣列）。

多練習、多總結，DP 直覺自然養成。建議在 OJ 上親手實作上述 5 題，體會狀態定義的藝術。