DP贪心 · 考纲词条练习

第 1 题单选未作答

贪心法的核心思想是（）。

（2 分）

A

把问题分成两半递归

B

随机选择

C

每一步都选择当前最优（局部最优），期望最终得到全局最优

D

穷举所有可能

原创 2026 · 单选第1题｜知识点 KJ-31a

第 2 题单选未作答

贪心算法能够得到全局最优解的必要条件是（）。

（2 分）

A

问题是树形结构

B

问题具有贪心选择性质——全局最优解可以由局部最优选择构造出来

C

数据规模足够小

D

没有条件

原创 2026 · 单选第2题｜知识点 KJ-31a

第 3 题单选未作答

最优子结构是指（）。

（2 分）

A

子问题的解是唯一的

B

每个子问题都是最优的排列

C

子问题互相独立

D

问题的最优解包含子问题的最优解

原创 2026 · 单选第3题｜知识点 KJ-31a

第 4 题单选未作答

贪心算法（）保证得到全局最优解。

（2 分）

A

一定

B

不一定——只有满足贪心选择性质的问题才能

C

一定不

D

只在数据有序时

原创 2026 · 单选第4题｜知识点 KJ-31a

第 5 题单选未作答

证明贪心正确性的常用方法是（）。

（2 分）

A

交换论证——假设最优解与贪心解不同，交换后不变得更差，推出贪心解也是最优

B

目测

C

随机测试

D

无法证明

原创 2026 · 单选第5题｜知识点 KJ-31a

第 6 题单选未作答

很多贪心算法的第一步是排序，目的是（）。

（2 分）

A

按贪心策略的优先级重新排列候选——让"应该先选的"排在前面

B

没有目的

C

让输出更美观

D

减少数据量

原创 2026 · 单选第6题｜知识点 KJ-31a

第 7 题单选未作答

面值 $\{1, 3, 4\}$ 的硬币找 $6$ 元：贪心（每次取最大）先取 $4$ 再取 $1+1$ 共 $3$ 枚。但最优解是（）。

（2 分）

A

没有更优解

B

$4 + 1 + 1$ ，共 $3$ 枚

C

$1 \times 6$ ，共 $6$ 枚

D

$3 + 3$ ，共 $2$ 枚——贪心不一定最优的经典反例

原创 2026 · 单选第7题｜知识点 KJ-31a

第 8 题单选未作答

验证贪心策略是否正确，最可靠的方法是（）。

（2 分）

A

试几个例子

B

看时间复杂度

C

数学证明（交换论证/归纳法）或与已知正确算法对比

D

凭直觉

原创 2026 · 单选第8题｜知识点 KJ-31a

第 9 题单选未作答

选择贪心还是 DP 的主要依据是（）。

（2 分）

A

DP 总是更好

B

贪心要求贪心选择性质（当前最优可推出全局最优）；DP 只要求最优子结构（更宽松）——不满足贪心性质的必须用 DP

C

随便选

D

贪心总是更好

原创 2026 · 单选第9题｜知识点 KJ-31a

第 10 题单选未作答

贪心算法（排序后一次扫描）的典型时间复杂度是（）。

（2 分）

A

$O(2^n)$

B

$O(n^2)$

C

$O(n \log n)$ （排序主导）或 $O(n)$ （已排序时一次扫描）

D

$O(n!)$

原创 2026 · 单选第10题｜知识点 KJ-31a

第 11 题单选未作答

关于贪心算法，正确的是（）。

（2 分）

A

贪心每步做出局部最优选择、不可回退

B

贪心一定比 DP 快

C

贪心就是暴力搜索

D

贪心可以回退

原创 2026 · 单选第11题｜知识点 KJ-31a

第 12 题单选未作答

关于贪心，错误的是（）。

（2 分）

A

贪心不一定全局最优

B

贪心需要排序预处理

C

贪心总能得到最优解

D

贪心不回退

原创 2026 · 单选第12题｜知识点 KJ-31a

第 13 题单选未作答

区间调度问题：给定 $n$ 个区间，选出最多的互不重叠的区间。贪心策略是（）。

（2 分）

A

按左端点从小到大选

B

随机选

C

按右端点从小到大选——最先结束的优先，给后面留最多空间

D

按区间长度从小到大选

原创 2026 · 单选第13题｜知识点 KJ-31a

第 14 题单选未作答

活动选择： $n$ 个活动各有起止时间，一人最多参加几个不冲突的活动？贪心按（）排序。

（2 分）

A

结束时间从早到晚

B

活动时长从短到长

C

开始时间从早到晚

D

活动名称字典序

原创 2026 · 单选第14题｜知识点 KJ-31a

第 15 题单选未作答

面值 $\{1, 2, 5, 10\}$ 找 $18$ 元，贪心（每次取最大可用面值）需（）枚硬币。

（2 分）

A

$6$

B

$4$

C

$5$ （ $10+5+2+1$ ，共 $4$ 枚）

D

$5$

原创 2026 · 单选第15题｜知识点 KJ-31a

第 16 题单选未作答

面值 $\{1, 3, 4\}$ 找 $6$ 元，贪心先取最大面值 $4$ ，剩余 $2$ 元只能 $1+1$ 。贪心结果共 $3$ 枚，最优解是（）枚。

（2 分）

A

$6$

B

$3$

C

$4$

D

$2$

原创 2026 · 单选第16题｜知识点 KJ-31a

第 17 题单选未作答

Kruskal 最小生成树算法的贪心策略是（）。

（2 分）

A

按顶点编号

B

随机选边

C

按边权从小到大依次加入，不构成环就选——直到 $n-1$ 条边

D

按边权从大到小

原创 2026 · 单选第17题｜知识点 KJ-31a

第 18 题单选未作答

Dijkstra 单源最短路的贪心策略是（）。

（2 分）

A

按编号从小到大

B

随机选结点

C

每次从未确定的结点中选距离最小的确定为最终最短路

D

每次选最远的结点

原创 2026 · 单选第18题｜知识点 KJ-31a

第 19 题单选未作答

区间覆盖：用最少的区间覆盖 $[0, m]$ ，贪心策略是（）。

（2 分）

A

随机选

B

按左端点排序，每次选左端点在覆盖范围内且右端点最远的区间

C

按右端点排序

D

按区间长度排序

原创 2026 · 单选第19题｜知识点 KJ-31a

第 20 题单选未作答

排队打水： $n$ 个人打水时间各不同，如何安排顺序使总等待时间最少？贪心按（）。

（2 分）

A

打水时间从小到大——短的先打，后面等的人少

B

打水时间从大到小

C

随机

D

编号从小到大

原创 2026 · 单选第20题｜知识点 KJ-31a

第 21 题单选未作答

田忌赛马的贪心策略核心是（）。

（2 分）

A

随机出马

B

全部认输

C

用最好的马对齐王最好的马

D

用最差的马对齐王最好的马（消耗对方最好），其余尽量赢

原创 2026 · 单选第21题｜知识点 KJ-31a

第 22 题单选未作答

0-1 背包问题不能用贪心（按单位价值排序）得到最优解，原因是（）。

（2 分）

A

没有排序算法

B

物品不可分割——单位价值最高的物品可能因容量不足而无法放入，贪心选择会导致次优

C

贪心太慢

D

数据量太大

原创 2026 · 单选第22题｜知识点 KJ-31a

第 23 题单选未作答

哈夫曼树构造的贪心策略是（）。

（2 分）

A

每次合并权重最小的两个

B

每次合并最大的两个

C

按编号合并

D

随机合并

原创 2026 · 单选第23题｜知识点 KJ-31a

第 24 题单选未作答

跳跃游戏：从位置 $0$ 出发，每步最多跳 a[i] 格，能否到达最后一个位置？贪心维护（）。

（2 分）

A

跳跃次数

B

步数

C

当前位置

D

当前能到达的最远位置——遍历时若 $i$ 超过最远位置则失败

原创 2026 · 单选第24题｜知识点 KJ-31a

第 25 题单选未作答

活动 $[1,4), [2,3), [3,5), [4,6)$ ，按结束时间贪心（最早结束优先），最多选（）个不冲突活动。

（2 分）

A

$1$

B

$4$

C

$2$

D

$3$ （选 $[2,3), [3,5), [4,6)$ ——但 $[3,5)$ 与 $[4,6)$ 重叠，实际选 $[2,3), [3,5)$ 或 $[2,3), [4,6)$ 共 $2$ 个不对……重算：排序后 $[2,3), [1,4), [3,5), [4,6)$ ，选 $[2,3)$ ，跳过 $[1,4)$ （冲突），选 $[3,5)$ ，跳过 $[4,6)$ （冲突 $3<5$ ），共 $2$ 个）

原创 2026 · 单选第25题｜知识点 KJ-31a

第 26 题单选未作答

下列问题中不能用标准贪心得到最优解的是（）。

（2 分）

A

0-1 背包

B

最小生成树（Kruskal）

C

哈夫曼编码

D

区间调度（按右端点排序）

原创 2026 · 单选第26题｜知识点 KJ-31a

第 27 题单选未作答

动态规划的核心思想是（）。

（2 分）

A

每步选当前最优

B

随机搜索

C

分治但不合并

D

把问题分解为重叠子问题，每个子问题只算一次、结果存表复用

原创 2026 · 单选第27题｜知识点 KJ-37b

第 28 题单选未作答

DP 设计的第一步是（）。

（2 分）

A

找贪心策略

B

排序

C

定义状态—— $f[i]$ 或 $f[i][j]$ 表示什么含义

D

写代码

原创 2026 · 单选第28题｜知识点 KJ-37b

第 29 题单选未作答

DP 的转移方程描述的是（）。

（2 分）

A

当前状态如何由之前的状态推导—— $f[i]$ 与 $f[i-1]$ （或更早）的关系

B

最终答案

C

初始值

D

输出格式

原创 2026 · 单选第29题｜知识点 KJ-37b

第 30 题单选未作答

DP 的初始条件（边界值）的作用是（）。

（2 分）

A

没有作用

B

加速

C

减小空间

D

递推的起点——没有初始值，转移方程无法启动

原创 2026 · 单选第30题｜知识点 KJ-37b

第 31 题单选未作答

DP 要求状态具有无后效性，含义是（）。

（2 分）

A

不能有副作用

B

不能修改数组

C

不能递归

D

某状态一旦确定，之后的决策不影响该状态的值——只与之前的状态有关

原创 2026 · 单选第31题｜知识点 KJ-37b

第 32 题单选未作答

DP 要求问题具有最优子结构，含义是（）。

（2 分）

A

问题的最优解由子问题的最优解构成

B

子问题必须独立

C

结构是树形的

D

每个子问题只有唯一解

原创 2026 · 单选第32题｜知识点 KJ-37b

第 33 题单选未作答

DP 与递推的关系是（）。

（2 分）

A

DP 是递推的推广——线性递推是最简单的 DP（ $f[i] = f[i-1] + f[i-2]$ 即 DP 的转移方程）

B

完全无关

C

DP 不能用递推实现

D

递推比 DP 快

原创 2026 · 单选第33题｜知识点 KJ-37b

第 34 题单选未作答

DP 与分治的主要区别是（）。

（2 分）

A

DP 用递归，分治用循环

B

分治的子问题独立（不重复）；DP 的子问题重叠（重复计算，存表避免）

C

没有区别

D

DP 更慢

原创 2026 · 单选第34题｜知识点 KJ-37b

第 35 题单选未作答

DP 利用重叠子问题的性质来（）。

（2 分）

A

把指数级重复计算降为多项式级——每个子问题只算一次

B

节省排序

C

没有利用

D

增加计算量

原创 2026 · 单选第35题｜知识点 KJ-37b

第 36 题单选未作答

记忆化搜索与 DP 的关系是（）。

（2 分）

A

完全不同

B

记忆化更慢

C

记忆化是自顶向下的 DP（递归+缓存），递推是自底向上的 DP（循环填表）——本质等价

D

只能选一种

原创 2026 · 单选第36题｜知识点 KJ-37b

第 37 题单选未作答

DP 问题的设计步骤依次是（）。

（2 分）

A

找贪心→验证→修改

B

写代码→调试→提交

C

排序→扫描→输出

D

定义状态→推导转移方程→确定初始条件→确定枚举顺序→实现

原创 2026 · 单选第37题｜知识点 KJ-37b

第 38 题单选未作答

DP 的自顶向下实现（记忆化搜索）使用（）。

（2 分）

A

循环填表

B

分治

C

递归+缓存数组——从大问题向下拆，遇到已算过的直接返回

D

贪心

原创 2026 · 单选第38题｜知识点 KJ-37b

第 39 题单选未作答

DP 的自底向上实现（递推填表）使用（）。

（2 分）

A

随机化

B

排序

C

循环——从小问题填到大问题，不需要递归

D

递归

原创 2026 · 单选第39题｜知识点 KJ-37b

第 40 题单选未作答

关于 DP，错误的是（）。

（2 分）

A

DP 需要无后效性

B

所有问题都可以用 DP 高效解决

C

DP 利用重叠子问题

D

DP 需要最优子结构

原创 2026 · 单选第40题｜知识点 KJ-37b

第 41 题单选未作答

最长上升子序列（LIS）是指（）。

（2 分）

A

最大的元素值

B

序列中选出最多的元素保持相对顺序且严格递增——不要求连续

C

最长的连续递增段

D

排序后的长度

原创 2026 · 单选第41题｜知识点 KJ-37b、KS-62f、KS-62e

第 42 题单选未作答

LIS 的 $O(n^2)$ 转移方程是（）。

（2 分）

A

f[i] = max(a[i], f[i-1])

B

f[i] = a[i] - a[i-1]

C

f[i] = max(f[j] + 1)（ $j < i$ 且 $a[j] < a[i]$ ）——以 $a[i]$ 结尾的 LIS 长度

D

f[i] = f[i-1] + 1

原创 2026 · 单选第42题｜知识点 KJ-37b、KS-62f、KS-62e

第 43 题单选未作答

序列 $\{3, 1, 2, 5, 4\}$ 的 LIS 长度是（）。

（2 分）

A

$3$

B

$3$ （如 $\{1,2,5\}$ 或 $\{1,2,4\}$ ）

C

$2$

D

$5$

原创 2026 · 单选第43题｜知识点 KJ-37b、KS-62f、KS-62e

第 44 题单选未作答

LIS 的 $O(n^2)$ DP 和 $O(n \log n)$ 贪心+二分的区别是（）。

（2 分）

A

$O(n \log n)$ 不能得到正确答案

B

$O(n^2)$ 更快

C

没有区别

D

$O(n^2)$ 枚举所有 $j < i$ ； $O(n \log n)$ 维护一个单调数组，每次二分插入

原创 2026 · 单选第44题｜知识点 KJ-37b、KS-62f、KS-62e

第 45 题单选未作答

最长公共子序列（LCS）是指（）。

（2 分）

A

两个串共有的最长子序列（保持相对顺序，不要求连续）

B

两个串拼接后的长度

C

两个串的公共前缀

D

两个串的公共后缀

原创 2026 · 单选第45题｜知识点 KJ-37b、KS-62f、KS-62e

第 46 题单选未作答

LCS 的转移方程：若 $a[i] == b[j]$ 则 $f[i][j] = f[i-1][j-1] + 1$ ；否则（）。

（2 分）

A

$f[i][j] = f[i][j-1] + 1$

B

$f[i][j] = f[i-1][j-1]$

C

$f[i][j] = 0$

D

$f[i][j] = \max(f[i-1][j], f[i][j-1])$

原创 2026 · 单选第46题｜知识点 KJ-37b、KS-62f、KS-62e

第 47 题单选未作答

"ABCBDAB" 与 "BDCABA" 的 LCS 长度是（）。

（2 分）

A

$4$ （如 BCAB 或 BCBA）

B

$3$

C

$7$

D

$5$

原创 2026 · 单选第47题｜知识点 KJ-37b、KS-62f、KS-62e

第 48 题单选未作答

最大子段和：序列中连续一段的和的最大值。允许全负时答案为（）。

（2 分）

A

$0$ （可以不选）

B

没有答案

C

最大的那个负数（必须选至少一个元素）

D

$-1$

原创 2026 · 单选第48题｜知识点 KJ-37b、KS-62f、KS-62e

第 49 题单选未作答

最大子段和的转移方程 $f[i] = \max(a[i], f[i-1] + a[i])$ 的含义是（）。

（2 分）

A

没有含义

B

$f[i]$ 表示以 $a[i]$ 结尾的最大子段和——要么独立开始（ $a[i]$ ），要么接上前面的（ $f[i-1]+a[i]$ ）

C

$f[i]$ 是全序列和

D

$f[i]$ 表示前 $i$ 个的最大子段和

原创 2026 · 单选第49题｜知识点 KJ-37b、KS-62f、KS-62e

第 50 题单选未作答

序列 $\{-2, 1, -3, 4, -1, 2, 1, -5, 4\}$ 的最大子段和是（）。

（2 分）

A

$6$ （子段 $4, -1, 2, 1$ ）

B

$5$

C

$4$

D

$11$

原创 2026 · 单选第50题｜知识点 KJ-37b、KS-62f、KS-62e

第 51 题单选未作答

每次上 $1$ 或 $2$ 阶台阶，从第 $0$ 阶到第 $5$ 阶的方法数是（）。

（2 分）

A

$6$

B

$8$

C

$13$

D

$5$

原创 2026 · 单选第51题｜知识点 KJ-37b、KS-62f、KS-62e

第 52 题单选未作答

数字三角形从顶到底的最大路径和：状态 $f[i][j]$ 表示（）。

（2 分）

A

$(i,j)$ 的值

B

从顶到 $(i,j)$ 的最大路径和

C

第 $i$ 行的和

D

从 $(i,j)$ 到底的最大路径和

原创 2026 · 单选第52题｜知识点 KJ-37b、KS-62f、KS-62e

第 53 题单选未作答

LIS 的 $O(n^2)$ DP 代码核心双重循环是（）。

（2 分）

A

只需一层循环

B

两层都从 $1$ 到 $n$

C

外层 $i$ 从 $1$ 到 $n$ ，内层 $j$ 从 $0$ 到 $i-1$ ，若 $a[j] < a[i]$ 则 $f[i] = \max(f[i], f[j]+1)$

D

用 DFS

原创 2026 · 单选第53题｜知识点 KJ-37b、KS-62f、KS-62e

第 54 题单选未作答

关于线性 DP，错误的是（）。

（2 分）

A

LIS 的最优复杂度是 $O(n^2)$ （无法优化）

B

最大子段和是线性 DP

C

爬楼梯是线性 DP

D

LIS 和 LCS 都是线性 DP

原创 2026 · 单选第54题｜知识点 KJ-37b、KS-62f、KS-62e

第 55 题单选未作答

0-1 背包： $n$ 个物品各有重量 $w_i$ 和价值 $v_i$ ，背包容量 $W$ ，每件物品最多选一次，求最大价值。状态 $f[i][j]$ 表示（）。

（2 分）

A

第 $i$ 件物品的价值

B

前 $i$ 件物品的总价值

C

剩余容量

D

考虑前 $i$ 件物品、容量为 $j$ 时的最大价值

原创 2026 · 单选第55题｜知识点 KJ-37c

第 56 题单选未作答

0-1 背包的转移方程（ $j \ge w_i$ 时）是（）。

（2 分）

A

$f[i][j] = \max(f[i][j], f[i-1][j-w_i])$

B

$f[i][j] = f[i][j - w_i] + v_i$

C

$f[i][j] = f[i-1][j] + v_i$

D

$f[i][j] = \max(f[i-1][j],\; f[i-1][j - w_i] + v_i)$

原创 2026 · 单选第56题｜知识点 KJ-37c

第 57 题单选未作答

物品 $\{(w=1,v=1), (w=2,v=3), (w=3,v=4)\}$ ，容量 $W=4$ 。0-1 背包最大价值是（）。

（2 分）

A

$4$

B

$7$

C

$5$ （选第 1、2 件： $w=3 \le 4$ ， $v=1+3=4$ ；或选第 2、3 件： $w=5 > 4$ 不行；选第 2 件+第 1 件最优 $v=4$ ？重算：选 2+3 不行 $w=5>4$ ；选 1+2 得 $v=4$ ；选 1+3 得 $v=5$ ， $w=4 \le 4$ ✓；所以最优是 $5$ ）

D

$5$

原创 2026 · 单选第57题｜知识点 KJ-37c

第 58 题单选未作答

0-1 背包一维优化后内层循环倒序（ $j$ 从 $W$ 到 $w_i$ ），原因是（）。

（2 分）

A

习惯写法

B

倒序保证 $f[j - w_i]$ 是上一行（ $i-1$ 层）的值——正序会用本行新值，物品被重复选取

C

没有原因

D

倒序更快

原创 2026 · 单选第58题｜知识点 KJ-37c

第 59 题单选未作答

完全背包与 0-1 背包的区别是（）。

（2 分）

A

没有区别

B

完全背包每件物品可以选无限次

C

完全背包没有容量限制

D

完全背包更难

原创 2026 · 单选第59题｜知识点 KJ-37c

第 60 题单选未作答

完全背包的转移方程（ $j \ge w_i$ 时）是（）。

（2 分）

A

$f[i][j] = \max(f[i-1][j], f[i][j - w_i] + v_i)$ ——第二项用本行（允许重复选）

B

$f[i][j] = f[i-1][j]$

C

$f[i][j] = \max(f[i-1][j], f[i-1][j-w_i] + v_i)$

D

$f[i][j] = f[i][j-w_i] + v_i$

原创 2026 · 单选第60题｜知识点 KJ-37c

第 61 题单选未作答

完全背包一维优化后内层循环正序（ $j$ 从 $w_i$ 到 $W$ ），原因是（）。

（2 分）

A

没有原因

B

习惯写法

C

正序更快

D

正序使 $f[j - w_i]$ 用本行新值——同一件物品可以被多次选取，这正是完全背包的要求

原创 2026 · 单选第61题｜知识点 KJ-37c

第 62 题单选未作答

多重背包与 0-1/完全背包的区别是（）。

（2 分）

A

每件物品有数量上限 $c_i$ （ $1 \le$ 选取次数 $\le c_i$ ）

B

没有区别

C

每件必须选

D

没有重量

原创 2026 · 单选第62题｜知识点 KJ-37c

第 63 题单选未作答

背包从 $f[n][W]$ 二维优化为 $f[W]$ 一维，空间从 $O(nW)$ 降为（）。

（2 分）

A

$O(n + W)$

B

$O(1)$

C

$O(W)$ ——只需一行滚动

D

$O(n)$

原创 2026 · 单选第63题｜知识点 KJ-37c

第 64 题单选未作答

"恰好装满"的背包方案数： $f[j]$ 初始 $f[0] = 1$ （空方案），转移 $f[j] += f[j - w_i]$ 。 $f[j]$ 含义是（）。

（2 分）

A

不可能装满

B

物品数

C

恰好用容量 $j$ 的选取方案数

D

容量 $j$ 的最大价值

原创 2026 · 单选第64题｜知识点 KJ-37c

第 65 题单选未作答

求"恰好装满"的最大价值时， $f[0] = 0$ 其余 $f[j] = -\infty$ ，目的是（）。

（2 分）

A

没有目的

B

标记"非零容量初始不可达"——只有从 $f[0]$ 出发转移过的才是合法状态

C

节省内存

D

让答案更大

原创 2026 · 单选第65题｜知识点 KJ-37c

第 66 题单选未作答

0-1 背包物品 $\{(w=1,v=2), (w=2,v=3)\}$ ，容量 $W=2$ 。处理第 1 件后 $f[1]=?$ 、 $f[2]=?$ （）。

（2 分）

A

$0, 0$

B

$2, 3$

C

$0, 2$

D

$2, 2$

原创 2026 · 单选第66题｜知识点 KJ-37c

第 67 题单选未作答

0-1 背包的时间复杂度是（）。

（2 分）

A

$O(n)$

B

$O(n \times W)$ ——物品数乘容量

C

$O(2^n)$

D

$O(W)$

原创 2026 · 单选第67题｜知识点 KJ-37c

第 68 题单选未作答

关于背包 DP，错误的是（）。

（2 分）

A

0-1 背包倒序枚举

B

完全背包正序枚举

C

一维优化空间 $O(W)$

D

0-1 背包可以用贪心得到最优解

原创 2026 · 单选第68题｜知识点 KJ-37c

第 69 题单选未作答

区间 DP 的状态 $f[l][r]$ 通常表示（）。

（2 分）

A

区间长度

B

点 $l$ 到点 $r$ 的距离

C

前 $l$ 个和后 $r$ 个的和

D

区间 $[l, r]$ 上问题的最优解

原创 2026 · 单选第69题｜知识点 KJ-37d

第 70 题单选未作答

区间 DP 的枚举顺序是（）。

（2 分）

A

$l$ 从小到大、 $r$ 从小到大即可

B

区间长度从短到长——先算短区间，再由短区间合并出长区间

C

从长到短

D

任意顺序

原创 2026 · 单选第70题｜知识点 KJ-37d

第 71 题单选未作答

石子合并： $n$ 堆石子排成一行，每次合并相邻两堆代价为两堆之和，求全部合并的最小总代价。这是（）。

（2 分）

A

贪心问题

B

线性 DP

C

图论问题

D

区间 DP—— $f[l][r]$ 表示合并 $[l,r]$ 的最小代价

原创 2026 · 单选第71题｜知识点 KJ-37d

第 72 题单选未作答

石子合并转移 $f[l][r] = \min_{l \le k < r}(f[l][k] + f[k+1][r]) + \text{sum}(l, r)$ 。 $\text{sum}(l,r)$ 是（）。

（2 分）

A

区间长度

B

最大值

C

区间 $[l, r]$ 的石子总和（前缀和预处理 $O(1)$ 查询）

D

最小值

原创 2026 · 单选第72题｜知识点 KJ-37d

第 73 题单选未作答

石子 $\{1, 2, 3\}$ （相邻合并，代价=两堆之和）。先合并 $\{1,2\}$ 代价 $3$ 得 $\{3, 3\}$ ，再合并代价 $6$ 。总代价（）。

（2 分）

A

$9$

B

$6$

C

$5$

D

$10$

原创 2026 · 单选第73题｜知识点 KJ-37d

第 74 题单选未作答

区间 DP 必须按长度从短到长枚举，原因是（）。

（2 分）

A

代码更短

B

转移方程要用到更短的区间的解——长区间的解由短区间合并而来，必须先算短的

C

没有原因

D

排序需要

原创 2026 · 单选第74题｜知识点 KJ-37d

第 75 题单选未作答

区间 DP 与线性 DP 的主要区别是（）。

（2 分）

A

区间 DP 不能用循环

B

线性 DP 状态是一维的 $f[i]$ （前 $i$ 个）；区间 DP 状态是二维的 $f[l][r]$ （区间 $[l,r]$ ）

C

没有区别

D

区间 DP 更快

原创 2026 · 单选第75题｜知识点 KJ-37d

第 76 题单选未作答

区间 DP 代码的标准三重循环结构是（）。

（2 分）

A

外层枚举区间长度 len，中层枚举左端点 $l$ ，内层枚举分割点 $k$

B

两层循环

C

递归

D

一层循环

原创 2026 · 单选第76题｜知识点 KJ-37d

第 77 题单选未作答

石子合并 $\{4, 1, 1, 4\}$ 的最优合并代价是（）。

（2 分）

A

$22$

B

$16$

C

$18$

D

$20$

原创 2026 · 单选第77题｜知识点 KJ-37d

第 78 题单选未作答

关于区间 DP，错误的是（）。

（2 分）

A

石子合并是经典应用

B

按长度从短到长枚举

C

区间 DP 可以用贪心替代

D

状态是二维 $f[l][r]$

原创 2026 · 单选第78题｜知识点 KJ-37d

第 79 题单选未作答

树形 DP 是指（）。

（2 分）

A

状态定义在树的结点上， $f[u]$ 表示以 $u$ 为根的子树的最优解——从叶向根递推

B

在图上做 DP

C

排序后再 DP

D

在树上做贪心

原创 2026 · 单选第79题｜知识点 KS-62b、KS-62c

第 80 题单选未作答

树形 DP 的实现通常使用（）。

（2 分）

A

DFS 后序遍历——先算完所有孩子的 $f[v]$ ，再算 $f[u]$

B

不需要遍历

C

BFS

D

拓扑排序

原创 2026 · 单选第80题｜知识点 KS-62b、KS-62c

第 81 题单选未作答

树形 DP 求树上最大独立集： $f[u][0]$ 表示不选 $u$ 、 $f[u][1]$ 表示选 $u$ 。转移 $f[u][0] = ?$ （）。

（2 分）

A

$f[\text{parent}][1]$

B

$\sum_{v \in \text{children}(u)} \max(f[v][0], f[v][1])$ ——孩子可选可不选

C

$f[u][1]$

D

$0$

原创 2026 · 单选第81题｜知识点 KS-62b、KS-62c

第 82 题单选未作答

状态压缩 DP 是指（）。

（2 分）

A

用哈希表

B

减少 DP 维度

C

用一个二进制数的每一位表示一个元素选/不选—— $n$ 个元素的状态压缩为 $[0, 2^n)$ 的整数

D

压缩文件后再 DP

原创 2026 · 单选第82题｜知识点 KS-62b、KS-62c

第 83 题单选未作答

状压 DP 中状态 $s = 13$ （二进制 $1101$ ）表示（）（4 个元素编号 $0\sim3$ ）。

（2 分）

A

只选了第 $1$ 个

B

选了 $13$ 个

C

没选任何

D

选了第 $0$ 、 $2$ 、 $3$ 个（位 $0$ 、 $2$ 、 $3$ 为 $1$ ）

原创 2026 · 单选第83题｜知识点 KS-62b、KS-62c

第 84 题单选未作答

检查状压状态 $s$ 的第 $i$ 位是否为 $1$ 的位运算是（）。

（2 分）

A

s ^ i

B

s & i

C

s | (1 << i)

D

(s >> i) & 1

原创 2026 · 单选第84题｜知识点 KS-62b、KS-62c

第 85 题单选未作答

多维 DP 是指（）。

（2 分）

A

状态有多个维度（如 $f[i][j][k]$ 表示前 $i$ 个、容量 $j$ 、已选 $k$ 个）——背包加数量限制等

B

三维以上的数组

C

多个 DP 同时跑

D

只能用递归

原创 2026 · 单选第85题｜知识点 KS-62b、KS-62c

第 86 题单选未作答

DP 常见的优化方法不包括（）。

（2 分）

A

滚动数组（空间优化）

B

随机化优化

C

单调队列优化

D

斜率优化

原创 2026 · 单选第86题｜知识点 KS-62b、KS-62c

第 87 题单选未作答

滚动数组优化背包问题时， $f[i][j]$ 变为 $f[j]$ ，关键是（）。

（2 分）

A

枚举顺序——0-1 背包倒序保证用上一行、完全背包正序允许用本行

B

用哈希

C

删掉一行

D

不需要考虑顺序

原创 2026 · 单选第87题｜知识点 KS-62b、KS-62c

第 88 题单选未作答

DP 与贪心的核心区别是（）。

（2 分）

A

没有区别

B

贪心不回退（当前选择不可撤销）；DP考虑所有子问题（枚举所有可能转移取最优）

C

贪心更准

D

DP 更快

原创 2026 · 单选第88题｜知识点 KS-62b、KS-62c

第 89 题单选未作答

树形 DP 的时间复杂度通常是（）。

（2 分）

A

$O(n^2)$

B

$O(2^n)$

C

$O(n \log n)$

D

$O(n)$ ——每个结点处理一次，每个结点的转移合并所有孩子

原创 2026 · 单选第89题｜知识点 KS-62b、KS-62c

第 90 题单选未作答

关于 S 级 DP，错误的是（）。

（2 分）

A

树形 DP 在树上做

B

所有 DP 都能优化到 $O(n)$

C

状压 DP 用二进制表示状态

D

多维 DP 状态有多个维度

原创 2026 · 单选第90题｜知识点 KS-62b、KS-62c

第 91 题单选未作答

当问题同时具有最优子结构和贪心选择性质时，应优先选（）。

（2 分）

A

随机

B

贪心——时间复杂度更低（通常 $O(n \log n)$ vs DP 的 $O(nW)$ 或更高）

C

分治

D

DP——更保险

原创 2026 · 单选第91题｜知识点 KJ-31a、KJ-37b

第 92 题单选未作答

"从 $(1,1)$ 走到 $(n,m)$ ，只能向右或向下，求最大路径和"是（）模型。

（2 分）

A

贪心

B

树形 DP

C

二维线性 DP—— $f[i][j] = \max(f[i-1][j], f[i][j-1]) + a[i][j]$

D

区间 DP

原创 2026 · 单选第92题｜知识点 KJ-31a、KJ-37b

第 93 题单选未作答

DP 调试最有效的方法是（）。

（2 分）

A

换编译器

B

只看最终答案

C

增大数据

D

打印 DP 表（小规模）——逐格检查转移是否正确、初始值是否合理

原创 2026 · 单选第93题｜知识点 KJ-31a、KJ-37b

第 94 题单选未作答

DP 的两个必要条件是（）。

（2 分）

A

递归和循环

B

贪心选择和排序

C

最优子结构和无后效性

D

排序和二分

原创 2026 · 单选第94题｜知识点 KJ-31a、KJ-37b

第 95 题单选未作答

0-1 背包不能用贪心（按单位价值排序）是因为（）。

（2 分）

A

数据太大

B

贪心太慢

C

物品不可分割，贪心的"当前最优"可能导致后续无法放入更优的组合

D

排序不正确

原创 2026 · 单选第95题｜知识点 KJ-31a、KJ-37b

第 96 题单选未作答

区间 DP $f[l][r]$ 的转移需要枚举分割点 $k$ ，时间复杂度是（）。

（2 分）

A

$O(n^3)$ —— $n^2$ 个区间每个 $O(n)$ 枚举分割

B

$O(n^4)$

C

$O(n^2)$

D

$O(n)$

原创 2026 · 单选第96题｜知识点 KJ-31a、KJ-37b

第 97 题单选未作答

LIS 的 $O(n \log n)$ 优化方法是（）。

（2 分）

A

排序

B

无法优化

C

哈希

D

维护单调数组+二分查找插入位置

原创 2026 · 单选第97题｜知识点 KJ-31a、KJ-37b

第 98 题单选未作答

记忆化搜索与递推填表的关系是（）。

（2 分）

A

记忆化总是更快

B

本质等价——只是方向不同（自顶向下 vs 自底向上）

C

完全不同

D

递推总是更快

原创 2026 · 单选第98题｜知识点 KJ-31a、KJ-37b

第 99 题单选未作答

树形 DP 求"树上最大独立集"的时间复杂度是（）。

（2 分）

A

$O(2^n)$

B

$O(n \log n)$

C

$O(n^2)$

D

$O(n)$

原创 2026 · 单选第99题｜知识点 KJ-31a、KJ-37b

第 100 题单选未作答

关于 DP 和贪心，错误的是（）。

（2 分）

A

DP 和贪心总能互相替换且结果相同

B

贪心不回退

C

DP 利用重叠子问题

D

DP 需要最优子结构

原创 2026 · 单选第100题｜知识点 KJ-31a、KJ-37b

DP贪心 · 考纲词条练习

判分报告

客观题

重置作答

DP贪心 · 考纲词条练习

判 分 报 告

客 观 题

打印

导出 HTML 子卷

判分报告

客观题