GESP 七级 · GESP 202312 C++ 七级 第 2 题

对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为（ ）。

int s[MAX_N], f[MAX_N][MAX_N];
int stone_merge(int n, int a[]) {
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                f[i][j] = 0;
            else
                f[i][j] = MAX_F;
    for (int l = 1; l < n; l++)
        for (int i = 1; i <= n - l; i++) {
            int j = i + l;
            for (int k = i; k < j; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }
    return f[1][n];
}

这题是经典的区间 DP 模型，核心在于识别出合并代价与区间和的关系，以及分裂点 k 的正确范围。拿到题先别急着套公式，盯着代码里 f[i][j] 的更新过程，你会发现那个 s[j]-s[i-1] 其实是个常数，完全可以提出来，剩下的就是看 k 到底取什么值能把区间合法地切成两半。

最容易栽跟头的地方有两个：一是把求和项直接塞进 min 函数里，写成 min(..., f(i,k)+f(k+1,j)+sum)，这虽然数值上没错，但作为状态转移函数的数学表达是不规范的，命题人专门喜欢考这个细节；二是分裂点 k 的取值范围，很多考生会下意识觉得 k 可以取到 j，或者漏掉 i 这个起点，导致区间切分不合法（比如出现空区间）。记住，合并操作必须把区间分成两个非空子区间，所以 k 只能从 i 取到 j-1，绝对不能等于 j。

【考点与命题视角】 这道题考查的是区间 DP 的状态转移函数表达。命题人挖坑很隐蔽，代码里把 s[j] - s[i - 1] 直接写在 min 的括号里，看着挺顺眼，但作为数学公式选项时，这种写法是不规范的。GESP 七级要求考生不仅会写代码，还要能准确描述算法逻辑，特别是区分“代码实现时的临时变量”和“状态转移方程的数学定义”。

【概念拆解：前缀和与区间和】 先看代码第一层循环：s[i] = s[i - 1] + a[i]。这是标准的前缀和预处理，s[i] 存的是 a[1] 到 a[i] 的和。那么 s[j] - s[i - 1] 是什么？根据前缀和性质，它正好等于区间 [i, j] 内所有元素的和，即 sum(a[i]...a[j])。这个值只跟区间的起止点 i 和 j 有关，跟中间怎么切分（也就是跟 k）毫无关系。既然跟 k 无关，在写状态转移方程时，把它放在 min 外面作为系数乘进去，或者单独加在后面，逻辑上都更清晰。

【思考心法：从代码到公式】 拿到这段代码，我们脑子里要过一遍： 1. 外层循环 l 枚举区间长度，内层 i 枚举起点，j = i + l 就是终点。这是区间 DP 的标准枚举顺序，保证子问题先算好。 2. 最内层 k 从 i 遍历到 j-1。为什么是 j-1？因为我们要把区间 [i, j] 切成 [i, k] 和 [k+1, j] 两段。如果 k 取到 j，那么后半段 [k+1, j] 就变成了 [j+1, j]，这是个空区间，没有意义，DP 状态通常定义为非空区间。所以 k 的上限必须是 j-1，下限是 i（保证前半段非空）。这就是分裂点 k 的范围：i <= k < j。 3. 状态转移的核心是：合并 [i, j] 的代价 = 合并左半边的代价 + 合并右半边的代价 + 当前合并整个区间的代价。代码里 f[i][k] + f[k+1][j] + s[j] - s[i-1] 完美对应了这个逻辑。

【逐项分析选项】 现在对照选项，看哪个能准确表达这个逻辑：

• A 项：min(f(i,j), f(i,k) + f(k+1,j) + s(j) - s(i-1))。这里有个致命问题，f(i,j) 本身是我们要计算的值，不能出现在 min 的比较项里。这就像说“我要算 x，然后跟 x 比大小取最小”，逻辑上是废话。而且它把求和项放在 min 里，虽然代码里确实是这样写的，但作为状态转移函数的数学表达，通常要求把常数项（与 k 无关的项）提取出来，写成 f(i,j) = min(...) + sum 的形式，这样更体现 DP 的递推本质。命题人考的就是这个“形式规范”。
• B 项：求和符号里的下标 k 和分裂点 k 重名了，导致表达式 sum_{k=i}^{j} a(k) 里的 k 含义混乱，数学上不严谨，直接排除。
• C 项：分裂点范围写的是 i <= k <= j。注意那个等号，允许 k=j。一旦 k=j，右半段 [k+1, j] 就是 [j+1, j]，空区间了，DP 状态定义失效。这是区间 DP 里最经典的“越界”坑，C 项就是踩了这个雷。
• D 项：f(i,j) = min_{i <= k < j} (f(i,k) + f(k+1,j)) + sum_{k=i}^{j} a(k)。这个写法太漂亮了。首先，min 的下标范围是 i <= k < j，严格小于，保证了左右两段都非空，逻辑严密。其次，求和项 sum_{k=i}^{j} a(k) 用 k 做哑变量（dummy variable），与分裂点 k 无关，完全符合前缀和的性质。最重要的是，它把常数项 sum 提到了 min 外面，这正是状态转移方程的标准数学表达形式，清晰地揭示了“先算子问题，再加当前合并代价”的递推过程。

【避坑指南】 做题时千万别被代码里的 if (i==j) f[i][j]=0; else f[i][j]=MAX_F; 这种初始化细节带偏，那是为了处理长度为 1 的区间（不需要合并，代价为 0），跟状态转移方程的形式无关。真正的坑在于： 1. 形式陷阱：看到代码里 min 括号里塞了一大坨，就想当然选那个。要记住，数学表达式要简洁、规范，常数项外置。 2. 边界陷阱：k 的上限。区间 DP 里，分裂点永远不能取到区间的右端点，否则右边就空了。k < j 是铁律。

【考频与趋势】 回顾数据，动态规划在题库里是绝对的常青树，120 题覆盖 9 个级别，2023 年考了 14 题，2024 年更是飙到 24 题，2025 年 25 题，2026 年 30 题，呈现逐年递增的强劲势头。具体到“简单动态规划”这个细分考点，94 题的体量，2023-2026 年每年都在 13-25 题之间，说明命题组对这个知识点的考察力度非常大且稳定。在七级考试中，DP 占比也高达 29 题（共 120 题），是七级的核心中的核心。

【预测】 基于 2023-2026 年 DP 题目数量持续攀升（14 -> 24 -> 25 -> 30）的趋势，以及七级 DP 考点的高频度，可以明确预测：未来 GESP 七级乃至更高级别的考试中，区间 DP 依然是必考题型，而且命题难度可能会进一步细化。既然这道题专门考了“状态转移函数的数学表达”和“常数项外置”这种细节，以后很可能还会出类似的“代码转数学公式”或者“公式转代码逻辑”的变种题，甚至可能考察更复杂的二维区间 DP 或者带权重的区间 DP。考生必须把区间 DP 的模型（枚举长度、枚举起点、枚举分裂点）刻在脑子里，并且要能熟练地在代码实现和数学表达之间切换视角，这才是应对未来考题的硬实力。