Question 26
修改转移式后的输出
若把 `min(dp[i-1], dp[i-2]) + cost[i-1]` 改为 `dp[i-1] + cost[i-2]`,输入 `cost = {5, 10, 15}` 时,输出为多少?
正确答案
A. 10
一句话考点
改动后的转移式已经不再比较两条路径,而是强制从前一阶来。
Shared Context
阅读程序(2)最小花费爬楼梯
这一组程序本质上是 `min cost climbing stairs` 的动态规划模型。
状态定义
`dp[i]` 不是数组前 i 项的最小值,而是“到达第 i 阶”的最小代价。
边界条件
`dp[0] = 0`、`dp[1] = cost[0]` 这两个初始化决定了后面的转移是否正确。
常考变化
改错题通常围绕下标偏移、取 min 的位置和返回值三处展开。
cpp
共享程序片段#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;
}题组阅读提醒
数组 `dp[i]` 表示到达第 i 级台阶时的最小花费,状态转移来自前一阶和前两阶的较小值。
返回 `min(dp[n], dp[n - 1])` 代表最后可以从倒数第一阶或倒数第二阶跨到楼顶,因此不必一定踩在最后一级。
Prompt
题目与选项
若把 `min(dp[i-1], dp[i-2]) + cost[i-1]` 改为 `dp[i-1] + cost[i-2]`,输入 `cost = {5, 10, 15}` 时,输出为多少?
A. "10"
B. "15"
C. "20"
D. "25"
Quick Check
做题抓手
先判断题型
先定位知识点,再决定是公式套用、手推样例还是结构重建。
再核对边界
第一轮很爱在闭区间、下标偏移、递归终止条件和布尔返回值上设陷阱。
最后看输出层次
尤其是阅读程序题,要分清函数返回值、变量值和最终打印值是不是同一件事。
Explanation
详细讲解
Step 1
新公式下:`dp[1] = 5`。当 `i = 2` 时,`dp[2] = dp[1] + cost[0] = 5 + 5 = 10`。
Step 2
当 `i = 3` 时,`dp[3] = dp[2] + cost[1] = 10 + 10 = 20`。
Step 3
程序最后仍然返回 `min(dp[3], dp[2]) = min(20, 10) = 10`,所以答案是 A。
Pitfalls
易错点
- 继续套用原转移式的思路,忘了这里已经没有 `min` 了。
- 把 `cost[i-2]` 下标算错成 `cost[i-1]`。
Extend
拓展补充
- 一旦状态转移式改变,就要重新解释 `dp[i]` 的含义,不能拿原题结论直接套。
返回总览
回到整套试卷
返回题目总览页,继续从目录、知识图谱或其他分区进入。
所属分区
返回 阅读程序
回到首页对应分区,继续顺序刷题或查看同类知识点。
上一题
第 25 题
样例 {10,15,30,5,5,10,20} 的输出
下一题
第 27 题
输入 2 3 时返回值判断