GESP 七级 · GESP 七级样题（C++ 组） 第 10 题

下面函数尝试使用动态规划方法求出如下递推公式的函数，则横线处填写下列哪段代码可以完成预期功能？ 

这道题考的是二维 DP 循环顺序与依赖方向。拿到题先画依赖图：dp[i][j] 需要 dp[i-1][j] 和 dp[i][j-1]，所以必须保证计算当前格子时，这两个值已经算好。

最容易错在只记‘列优先’或‘行优先’的口诀，却忘了看依赖项是谁。比如选 D 时，外层 j 正序、内层 i 倒序，算 dp[i][j] 时 dp[i-1][j] 还没算（因为 i 是从 n 往下走的），结果就会漏掉关键状态。

考点与命题视角

GESP 七级动态规划模块专卡‘依赖方向与循环顺序匹配’。命题人故意把四个选项做成‘看起来都合理’的循环嵌套，其实只有 C 能同时满足两个依赖项：dp[i-1][j]（上一行同列）和 dp[i][j-1]（同行前一列）。其他选项要么行序反了，要么列序反了，要么内外层颠倒，都会导致某个依赖项尚未计算。

解题心法（拿到题先想什么）

1. 写出递推式：dp[i][j] = dp[i-1][j] + dp[i][j-1]（题目图中就是这个形式）。 2. 标记依赖：dp[i][j] 依赖‘上’和‘左’。 3. 问自己：要算上，必须保证上一行同列已经算完；要算左，必须保证同行前一个已经算完。 4. 转化为循环顺序：外层先扫完‘上’，内层再扫‘左’。也就是外层 j 从 1→m（保证列顺序），内层 i 从 1→n（保证行顺序）。 5. 验证：按这个顺序走到 dp[i][j] 时，dp[i-1][j] 是上一轮 j 循环算的，dp[i][j-1] 是刚才 i 循环算的，都✅。