区间DP

区间DP：把大问题切成小段，像吃面包一样简单

想象你有一根很长的法棍面包，想吃掉它。最方便的办法不是一口吞，而是先在中间掰开，分成两段，然后每段再掰开，直到变成一口能吃下的小块。这就是区间DP的核心思想：把一个大区间（比如数组的一段）分成两个小区间，分别解决，再把结果合并起来。它专门用来解决“在一个连续区间上做选择，最终要得到整个区间的最优解”的问题。

核心思想：为什么要把大区间切成小区间？

普通动态规划通常按顺序走（比如从左到右选物品），而区间DP是按区间长度从小到大处理。先算长度为1的区间（只有1个元素），再算长度为2的，慢慢扩大，直到算出整个区间。就像搭积木：先搭好最小的积木块，再用它们拼成更大的结构。

关键步骤只有两个：

枚举分割点：在区间 [l, r] 中选一个位置 k（l <= k < r），把区间切成 [l, k] 和 [k+1, r] 两段。
合并结果：两段各自的最优解加起来，再加上“合并这两段”需要的代价，就是当前区间的候选解。取所有分割点中的最小值。

这种套路能解决很多问题：合并石子、括号匹配、最优二叉搜索树……而且代码长得特别像。

生活例子：合并石子（现场推演）

你有一排石子堆，每堆有若干个石子。每次只能合并相邻的两堆，消耗的体力等于这两堆石子的总数。问把所有石子合并成一堆，最少需要多少体力？

比如三堆：1、2、3。

方案1：先合并1和2，得到3，消耗3；现在有三堆：3、3，再合并得到6，消耗6，总消耗9。
方案2：先合并2和3，得到5，消耗5；现在有两堆：1、5，再合并得到6，消耗6，总消耗11。

显然方案1更省力。区间DP能自动算出这个最小值。

推广到更一般的情况

假设有4堆：4、1、3、2。手动模拟会有点复杂，但计算机可以用区间DP轻松算出来。我们只需要定义好状态和转移方程。

状态定义：dp[l][r] 表示合并第 l 堆到第 r 堆（这些堆是连续的）成一堆所需的最小体力。
边界条件：dp[i][i] = 0，因为一堆石子不需要合并。
转移方程：在 [l, r] 中找一个分割点 k（l <= k < r），先合并左区间 [l, k]，再合并右区间 [k+1, r]，最后把左右两堆（即整个区间）合并在一起，消耗 sum[l][r]（区间内石子总数）。所以：

dp[l][r] = min( dp[l][r] , dp[l][k] + dp[k+1][r] + sum[l][r] )
其中 sum[l][r] 可以用前缀和快速得到：sum[l][r] = sum[r] - sum[l-1]（sum[i] 表示前i堆的总数）。

新手常犯的3个错误

忘记初始化 dp 数组
- 如果不把 dp 设为很大的数（比如 0x3f3f3f3f），min 比较时会出错。
- 正确做法：用 memset(dp, 0x3f, sizeof(dp)) 初始化为一个足够大的数，再把 dp[i][i] 设为0。
循环顺序搞反
- 必须先枚举区间长度，再枚举左端点，最后枚举分割点。
- 如果反过来（先枚举左端点再枚举长度），大区间在计算时，它依赖的小区间可能还没算好。原因：区间DP要求“小区间先算完”，只有按长度从小到大才能保证这一点。
分割点漏掉边界
- 分割点 k 必须从 l 到 r-1，不能等于 r（否则右区间为空）。
- 同样，左区间不能为空，所以 k 不能小于 l。

完整代码：合并石子（附详细注释）

#include <iostream>
#include <algorithm>   // 为了用 min()
#include <cstring>     // 为了用 memset()
using namespace std;

int main() {
    // ---------- 输入 ----------
    int n;              // 石子堆数
    cin >> n;
    int stones[105];    // 每堆石子数量，索引从1开始
    for (int i = 1; i <= n; i++) {
        cin >> stones[i];
    }

    // ---------- 前缀和 ----------
    int prefix_sum[105] = {0};       // prefix_sum[i] = 前i堆石子总数
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i-1] + stones[i];
    }

    // ---------- DP数组 ----------
    int dp[105][105];                // dp[l][r]：合并[l,r]的最小体力
    memset(dp, 0x3f, sizeof(dp));    // 初始化为一个很大的数（约10^9）
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;                // 一堆石子不需要消耗体力
    }

    // ---------- 核心DP：枚举区间长度 ----------
    for (int len = 2; len <= n; len++) {           // 区间长度从2开始
        for (int left = 1; left + len - 1 <= n; left++) {   // 左端点
            int right = left + len - 1;            // 右端点
            // 尝试所有分割点 k
            for (int k = left; k < right; k++) {
                // 左区间 [left, k] 的体力 + 右区间 [k+1, right] 的体力
                // + 本次合并这两大堆的体力（区间内石子总数）
                int cost = dp[left][k] + dp[k+1][right] 
                         + (prefix_sum[right] - prefix_sum[left-1]);
                dp[left][right] = min(dp[left][right], cost);
            }
        }
    }

    // ---------- 输出结果 ----------
    cout << dp[1][n] << endl;   // 把第1堆到第n堆合并成一堆的最小体力
    return 0;
}

运行示例：
输入：

4
4 1 3 2

计算过程：

长度2： (4,1) 合并需要5， (1,3) 合并需要4， (3,2) 合并需要5
长度3： (4,1,3) 最小是 min( 0+4+8, 5+0+8 ) = 12， (1,3,2) 最小是 min(0+5+6, 4+0+6)=10
长度4： (4,1,3,2) 枚举k=1: 0+10+10=20；k=2: 5+5+10=20；k=3: 12+0+10=22 → 最小20
输出：