环形 DP

概念讲解

什么是环形 DP？

环形 DP 是将环形问题转化为线性问题的技巧。

核心思想

破环为链：将环复制一倍，转化为长度为 2n 的链。

经典问题

1. 环形石子合并

问题： n 堆石子围成一圈，每次合并相邻两堆，求最小代价。

解答：

1234567891011121314151617181920212223242526272829303132333435363738394041int circularStoneMerge(vector<int>& stones) {
    int n = stones.size();
    vector<int> a(2 * n);
    
    // 破环为链
    for (int i = 0; i < n; i++) {
        a[i] = a[i + n] = stones[i];
    }
    
    // 计算前缀和
    vector<int> prefix(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n; i++) {
        prefix[i] = prefix[i - 1] + a[i - 1];
    }
    
    // 区间 DP
    vector<vector<int>> dp(2 * n, vector<int>(2 * n, 1e9));
    
    for (int i = 0; i < 2 * n; i++) {
        dp[i][i] = 0;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < 2 * n; i++) {
            int j = i + len - 1;
            int sum = prefix[j + 1] - prefix[i];
            
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum);
            }
        }
    }
    
    // 在所有长度为 n 的区间中找最小值
    int result = 1e9;
    for (int i = 0; i < n; i++) {
        result = min(result, dp[i][i + n - 1]);
    }
    
    return result;
}

考点分析

初赛考查方式

  1. 选择题： 环形 DP 的概念
  2. 程序阅读： 理解环形 DP
  3. 编程题： 环形 DP 应用

常见题型

  • 环形石子合并
  • 环形背包
  • 环形涂色

例题精讲

例题 1：环形石子合并

题目： n 堆石子围成一圈，求合并成一堆的最小代价。

解答：

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> stones(n);
    for (int i = 0; i < n; i++) {
        cin >> stones[i];
    }
    
    // 破环为链
    vector<int> a(2 * n);
    for (int i = 0; i < n; i++) {
        a[i] = a[i + n] = stones[i];
    }
    
    // 计算前缀和
    vector<int> prefix(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n; i++) {
        prefix[i] = prefix[i - 1] + a[i - 1];
    }
    
    // 区间 DP
    vector<vector<int>> dp(2 * n, vector<int>(2 * n, 1e9));
    
    for (int i = 0; i < 2 * n; i++) {
        dp[i][i] = 0;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < 2 * n; i++) {
            int j = i + len - 1;
            int sum = prefix[j + 1] - prefix[i];
            
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum);
            }
        }
    }
    
    int result = 1e9;
    for (int i = 0; i < n; i++) {
        result = min(result, dp[i][i + n - 1]);
    }
    
    cout << result << endl;
    
    return 0;
}

练习题

  1. 洛谷 P1880 石子合并
查看答案

思路：环形石子合并，破环为链后做区间 DP。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int a[2 * n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    
    int prefix[2 * n + 1] = {0};
    for (int i = 1; i <= 2 * n; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    int dpMin[2 * n + 1][2 * n + 1], dpMax[2 * n + 1][2 * n + 1];
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * n; j++) {
            dpMin[i][j] = 1e9;
            dpMax[i][j] = 0;
        }
        dpMin[i][i] = 0;
        dpMax[i][i] = 0;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= 2 * n; i++) {
            int j = i + len - 1;
            int sum = prefix[j] - prefix[i - 1];
            for (int k = i; k < j; k++) {
                dpMin[i][j] = min(dpMin[i][j], dpMin[i][k] + dpMin[k + 1][j] + sum);
                dpMax[i][j] = max(dpMax[i][j], dpMax[i][k] + dpMax[k + 1][j] + sum);
            }
        }
    }
    
    int minAns = 1e9, maxAns = 0;
    for (int i = 1; i <= n; i++) {
        minAns = min(minAns, dpMin[i][i + n - 1]);
        maxAns = max(maxAns, dpMax[i][i + n - 1]);
    }
    
    cout << minAns << endl << maxAns << endl;
    return 0;
}
  1. 洛谷 P1005 矩阵取数游戏
查看答案

思路：每行独立，对每行做区间 DP。

123456789101112131415161718192021222324252627282930313233#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    long long ans = 0;
    
    for (int row = 0; row < n; row++) {
        vector<int> a(m);
        for (int i = 0; i < m; i++) cin >> a[i];
        
        vector<vector<long long>> dp(m + 1, vector<long long>(m + 1, 0));
        
        for (int len = 1; len <= m; len++) {
            for (int i = 0; i + len - 1 < m; i++) {
                int j = i + len - 1;
                int power = m - len + 1;
                dp[i][j] = max(
                    (i <= j - 1 ? dp[i][j - 1] : 0) + (long long)a[j] * power,
                    (i + 1 <= j ? dp[i + 1][j] : 0) + (long long)a[i] * power
                );
            }
        }
        
        ans += dp[0][m - 1];
    }
    
    cout << ans << endl;
    return 0;
}
  1. 洛谷 P3146 248
查看答案

思路：区间 DP，合并相邻相同值。

12345678910111213141516171819202122232425262728293031323334#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int dp[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = 0;
        }
        dp[i][i] = a[i];
    }
    
    int ans = 0;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                if (dp[i][k] == dp[k + 1][j] && dp[i][k] != 0) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + 1);
                }
            }
            ans = max(ans, dp[i][j]);
        }
    }
    
    cout << ans << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. 环形 DP 要破环为链
  2. 复制一倍后要找所有长度为 n 的区间
  3. 环形 DP 是区间 DP 的变种
  4. 注意边界条件