CSP-J 入门级 · CSP 2024 入门级第一轮 第 17 题

第 2 题

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

int compute(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n+1, 0);
    dp[1] = cost[0];
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1];
    }
    return min(dp[n], dp[n-1]);
}

int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    cout << compute(cost) << endl;
    return 0;
}

判断题

1. 当输入的 cost 数组为 $\{10, 15, 20\}$ 时，程序的输出为 $15$。（ ） 2. 如果将 dp[i-1] 改为 dp[i-3]，程序可能会产生编译错误。（ ） 3. （2 分）程序总是输出 cost 数组中最小的元素。（ ）

单选题

1. 当输入的 cost 数组为 $\{1, 100, 1, 1, 1, 100, 1, 1, 100, 1\}$ 时，程序的输出为（ ）。 2. （4 分）如果输入的 cost 数组为 $\{10, 15, 30, 5, 5, 10, 20\}$，程序的输出为（ ）。 3. 若将代码中的 min(dp[i-1], dp[i-2]) + cost[i-1] 修改为 dp[i-1] + cost[i-2]，输入 cost 数组为 $\{5, 10, 15\}$ 时，程序

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题是经典的爬楼梯最小花费，核心是递推公式 dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]，最后别忘了取 min(dp[n], dp[n-1])。

最易错的是误以为程序输出数组最小值，其实它输出的是动态规划后的最优解；二是计算时忘记最终要比较 dp[n] 和 dp[n-1]；三是改代码时混淆下标，比如把 dp[i-1] 改成 dp[i-3] 不会报错，只是越界访问导致未定义行为，并非编译错误。

一、这题考什么

代码实现的是最小花费爬楼梯问题。dp[i] 表示爬到第 i 级台阶（从 1 开始计数）的最小花费。递推公式：

dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]

意思是：要上第 i 级，要么从 i-1 走一步，要么从 i-2 走两步，取两者中花费较小的再加上当前台阶的代价。最终答案不是 dp[n]，而是 min(dp[n], dp[n-1])，因为题目允许从倒数第二级直接跳到最顶端（相当于多跳一级），所以两种结束方式都要考虑。

二、逐题推演

判断题 1：cost={10,15,20} 输出 15？

按公式算：

• dp[1] = 10
• dp[2] = min(10,0)+15 = 25
• dp[3] = min(25,10)+20 = 30
• 最终 = min(30,25) = 25

显然 25≠15，错误。