5 - 区间DP

非常哈人动态规划，使我脑子旋转。

概念

定义的状态集合是区间。区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

例题

石子合并

282. 石子合并 - AcWing题库

首先分析 状态表示：

f[i, j]表示 所有将第i堆石子到第j堆石子合并成一堆石子的合并方式。我们要求合并方式所消耗体力的最小值。

然后分析 状态计算：

f[i, j]可以被拆分为（在区间中找一截取点k，划分为两个区间。其中k = i ~ j - 1）：

• 区间[i, k]，代价为f[i, k]。
• 区间[k + 1, j]，代价为f[k + 1, j]。

那么f[i, j] = min(f[i, k] + f[k + 1, j] + s[j] - s[i - 1])，其中s[]是前缀和数组。最终答案为f[1, n]。

const int INF = 1e9;
int main()
{
    int n;
    cin >> n;
    
    // 处理输入, 顺便求前缀和
    vector<int> stones(n + 5, 0), preSum(n + 5, 0);
    for (int i = 1; i <= n; ++i)
    {
        cin >> stones[i];
        preSum[i] = preSum[i - 1] + stones[i];
    }
    
    // dp
    vector<vector<int>> dp(n + 5, vector<int>(n + 5, 0));
    // 枚举所有区间长度
    for (int len = 2; len <= n; ++len)
        // 枚举该长度内的所有区间
        for (int i = 1; i + len - 1 <= n; ++i)
        {
            // 获得要划分的区间, 注意先将该区间初始化为INF
            int l = i, r = i + len - 1;
            dp[l][r] = INF;
            // 枚举区间的所有划分点
            for (int k = l; k < r; ++k)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + preSum[r] - preSum[l - 1]);
        }
    
    cout << dp[1][n];
}

练习题