Question 26

修改转移式后的输出

若把 `min(dp[i-1], dp[i-2]) + cost[i-1]` 改为 `dp[i-1] + cost[i-2]`,输入 `cost = {5, 10, 15}` 时,输出为多少?

单项选择阅读程序3难度 中等

正确答案

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])` 代表最后可以从倒数第一阶或倒数第二阶跨到楼顶,因此不必一定踩在最后一级。

本题属于第 阅读程序 分区,题组覆盖题号: 21、22、23、24、25、26

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

详细讲解

  1. Step 1

    新公式下:`dp[1] = 5`。当 `i = 2` 时,`dp[2] = dp[1] + cost[0] = 5 + 5 = 10`。

  2. Step 2

    当 `i = 3` 时,`dp[3] = dp[2] + cost[1] = 10 + 10 = 20`。

  3. 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 时返回值判断