题目导航

林老师 · 客观题题库 · 专题 S06 动态规划与贪心 · 复习强化

专题 S06 动态规划与贪心 · 复习强化

100 题 · 每题对应一个知识细节 · 全部原创

真题
复刻

试卷编号ORIG-专题S06动态规划与贪心-复习强化

题目总数100 题 · 100 分

试卷类型客观题

考生须知：
① 本卷共 8 大部分，合计 100 题 · 100 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。

判分报告

0 / 100 分

答对 · 得 0 分

答错 · 失 0 分

未作答

当前筛选下没有题目

壹

贪心基础

12 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

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

（1 分）

把问题分成两半递归

随机选择

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

穷举所有可能

第 2 题 A2 未作答

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

（1 分）

问题是树形结构

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

数据规模足够小

没有条件

第 3 题 A3 未作答

最优子结构是指（）。

（1 分）

子问题的解是唯一的

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

子问题互相独立

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

第 4 题 A4 未作答

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

（1 分）

一定

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

一定不

只在数据有序时

第 5 题 A5 未作答

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

（1 分）

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

目测

随机测试

无法证明

第 6 题 A6 未作答

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

（1 分）

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

没有目的

让输出更美观

减少数据量

第 7 题 A7 未作答

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

（1 分）

没有更优解

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

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

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

第 8 题 A8 未作答

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

（1 分）

试几个例子

看时间复杂度

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

凭直觉

第 9 题 A9 未作答

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

（1 分）

DP 总是更好

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

随便选

贪心总是更好

第 10 题 A10 未作答

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

（1 分）

$O(2^n)$

$O(n^2)$

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

$O(n!)$

第 11 题 A11 未作答

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

（1 分）

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

贪心一定比 DP 快

贪心就是暴力搜索

贪心可以回退

第 12 题 A12 未作答

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

（1 分）

贪心不一定全局最优

贪心需要排序预处理

贪心总能得到最优解

贪心不回退

贰

贪心经典问题

14 QUESTIONS · 2 POINTS EACH

第 13 题 B1 未作答

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

（1 分）

按左端点从小到大选

随机选

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

按区间长度从小到大选

第 14 题 B2 未作答

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

（1 分）

结束时间从早到晚

活动时长从短到长

开始时间从早到晚

活动名称字典序

第 15 题 B3 未作答

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

（1 分）

$6$

$4$

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

$5$

第 16 题 B4 未作答

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

（1 分）

$6$

$3$

$4$

$2$

第 17 题 B5 未作答

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

（1 分）

按顶点编号

随机选边

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

按边权从大到小

第 18 题 B6 未作答

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

（1 分）

按编号从小到大

随机选结点

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

每次选最远的结点

第 19 题 B7 未作答

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

（1 分）

随机选

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

按右端点排序

按区间长度排序

第 20 题 B8 未作答

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

（1 分）

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

打水时间从大到小

随机

编号从小到大

第 21 题 B9 未作答

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

（1 分）

随机出马

全部认输

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

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

第 22 题 B10 未作答

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

（1 分）

没有排序算法

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

贪心太慢

数据量太大

第 23 题 B11 未作答

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

（1 分）

每次合并权重最小的两个

每次合并最大的两个

按编号合并

随机合并

第 24 题 B12 未作答

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

（1 分）

跳跃次数

步数

当前位置

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

第 25 题 B13 未作答

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

（1 分）

$1$

$4$

$2$

$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$ 个）

第 26 题 B14 未作答

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

（1 分）

0-1 背包

最小生成树（Kruskal）

哈夫曼编码

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

叁

DP 基础概念

14 QUESTIONS · 2 POINTS EACH

第 27 题 C1 未作答

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

（1 分）

每步选当前最优

随机搜索

分治但不合并

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

第 28 题 C2 未作答

DP 设计的第一步是（）。

（1 分）

找贪心策略

排序

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

写代码

第 29 题 C3 未作答

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

（1 分）

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

最终答案

初始值

输出格式

第 30 题 C4 未作答

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

（1 分）

没有作用

加速

减小空间

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

第 31 题 C5 未作答

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

（1 分）

不能有副作用

不能修改数组

不能递归

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

第 32 题 C6 未作答

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

（1 分）

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

子问题必须独立

结构是树形的

每个子问题只有唯一解

第 33 题 C7 未作答

DP 与递推的关系是（）。

（1 分）

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

完全无关

DP 不能用递推实现

递推比 DP 快

第 34 题 C8 未作答

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

（1 分）

DP 用递归，分治用循环

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

没有区别

DP 更慢

第 35 题 C9 未作答

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

（1 分）

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

节省排序

没有利用

增加计算量

第 36 题 C10 未作答

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

（1 分）

完全不同

记忆化更慢

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

只能选一种

第 37 题 C11 未作答

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

（1 分）

找贪心→验证→修改

写代码→调试→提交

排序→扫描→输出

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

第 38 题 C12 未作答

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

（1 分）

循环填表

分治

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

贪心

第 39 题 C13 未作答

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

（1 分）

随机化

排序

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

递归

第 40 题 C14 未作答

关于 DP，错误的是（）。

（1 分）

DP 需要无后效性

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

DP 利用重叠子问题

DP 需要最优子结构

肆

线性 DP

14 QUESTIONS · 2 POINTS EACH

第 41 题 D1 未作答

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

（1 分）

最大的元素值

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

最长的连续递增段

排序后的长度

第 42 题 D2 未作答

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

（1 分）

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

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

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

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

第 43 题 D3 未作答

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

（1 分）

$3$

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

$2$

$5$

第 44 题 D4 未作答

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

（1 分）

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

$O(n^2)$ 更快

没有区别

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

第 45 题 D5 未作答

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

（1 分）

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

两个串拼接后的长度

两个串的公共前缀

两个串的公共后缀

第 46 题 D6 未作答

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

（1 分）

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

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

$f[i][j] = 0$

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

第 47 题 D7 未作答

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

（1 分）

$4$ （如 BCAB 或 BCBA）

$3$

$7$

$5$

第 48 题 D8 未作答

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

（1 分）

$0$ （可以不选）

没有答案

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

$-1$

第 49 题 D9 未作答

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

（1 分）

没有含义

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

$f[i]$ 是全序列和

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

第 50 题 D10 未作答

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

（1 分）

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

$5$

$4$

$11$

第 51 题 D11 未作答

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

（1 分）

$6$

$8$

$13$

$5$

第 52 题 D12 未作答

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

（1 分）

$(i,j)$ 的值

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

第 $i$ 行的和

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

第 53 题 D13 未作答

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

（1 分）

只需一层循环

两层都从 $1$ 到 $n$

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

用 DFS

第 54 题 D14 未作答

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

（1 分）

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

最大子段和是线性 DP

爬楼梯是线性 DP

LIS 和 LCS 都是线性 DP

伍

背包 DP

14 QUESTIONS · 2 POINTS EACH

第 55 题 E1 未作答

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

（1 分）

第 $i$ 件物品的价值

前 $i$ 件物品的总价值

剩余容量

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

第 56 题 E2 未作答

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

（1 分）

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

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

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

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

第 57 题 E3 未作答

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

（1 分）

$4$

$7$

$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$ ）

$5$

第 58 题 E4 未作答

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

（1 分）

习惯写法

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

没有原因

倒序更快

第 59 题 E5 未作答

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

（1 分）

没有区别

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

完全背包没有容量限制

完全背包更难

第 60 题 E6 未作答

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

（1 分）

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

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

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

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

第 61 题 E7 未作答

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

（1 分）

没有原因

习惯写法

正序更快

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

第 62 题 E8 未作答

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

（1 分）

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

没有区别

每件必须选

没有重量

第 63 题 E9 未作答

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

（1 分）

$O(n + W)$

$O(1)$

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

$O(n)$

第 64 题 E10 未作答

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

（1 分）

不可能装满

物品数

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

容量 $j$ 的最大价值

第 65 题 E11 未作答

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

（1 分）

没有目的

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

节省内存

让答案更大

第 66 题 E12 未作答

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

（1 分）

$0, 0$

$2, 3$

$0, 2$

$2, 2$

第 67 题 E13 未作答

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

（1 分）

$O(n)$

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

$O(2^n)$

$O(W)$

第 68 题 E14 未作答

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

（1 分）

0-1 背包倒序枚举

完全背包正序枚举

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

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

陆

区间 DP

10 QUESTIONS · 2 POINTS EACH

第 69 题 F1 未作答

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

（1 分）

区间长度

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

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

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

第 70 题 F2 未作答

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

（1 分）

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

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

从长到短

任意顺序

第 71 题 F3 未作答

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

（1 分）

贪心问题

线性 DP

图论问题

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

第 72 题 F4 未作答

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

（1 分）

区间长度

最大值

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

最小值

第 73 题 F5 未作答

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

（1 分）

$9$

$6$

$5$

$10$

第 74 题 F6 未作答

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

（1 分）

代码更短

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

没有原因

排序需要

第 75 题 F7 未作答

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

（1 分）

区间 DP 不能用循环

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

没有区别

区间 DP 更快

第 76 题 F8 未作答

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

（1 分）

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

两层循环

递归

一层循环

第 77 题 F9 未作答

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

（1 分）

$22$

$16$

$18$

$20$

第 78 题 F10 未作答

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

（1 分）

石子合并是经典应用

按长度从短到长枚举

区间 DP 可以用贪心替代

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

柒

S 级 DP

12 QUESTIONS · 2 POINTS EACH

第 79 题 G1 未作答

树形 DP 是指（）。

（1 分）

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

在图上做 DP

排序后再 DP

在树上做贪心

第 80 题 G2 未作答

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

（1 分）

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

不需要遍历

BFS

拓扑排序

第 81 题 G3 未作答

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

（1 分）

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

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

$f[u][1]$

$0$

第 82 题 G4 未作答

状态压缩 DP 是指（）。

（1 分）

用哈希表

减少 DP 维度

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

压缩文件后再 DP

第 83 题 G5 未作答

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

（1 分）

只选了第 $1$ 个

选了 $13$ 个

没选任何

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

第 84 题 G6 未作答

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

（1 分）

s ^ i

s & i

s | (1 << i)

(s >> i) & 1

第 85 题 G7 未作答

多维 DP 是指（）。

（1 分）

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

三维以上的数组

多个 DP 同时跑

只能用递归

第 86 题 G8 未作答

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

（1 分）

滚动数组（空间优化）

随机化优化

单调队列优化

斜率优化

第 87 题 G9 未作答

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

（1 分）

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

用哈希

删掉一行

不需要考虑顺序

第 88 题 G10 未作答

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

（1 分）

没有区别

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

贪心更准

DP 更快

第 89 题 G11 未作答

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

（1 分）

$O(n^2)$

$O(2^n)$

$O(n \log n)$

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

第 90 题 G12 未作答

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

（1 分）

树形 DP 在树上做

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

状压 DP 用二进制表示状态

多维 DP 状态有多个维度

捌

综合与易错

10 QUESTIONS · 2 POINTS EACH

第 91 题 H1 未作答

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

（1 分）

随机

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

分治

DP——更保险

第 92 题 H2 未作答

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

（1 分）

贪心

树形 DP

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

区间 DP

第 93 题 H3 未作答

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

（1 分）

换编译器

只看最终答案

增大数据

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

第 94 题 H4 未作答

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

（1 分）

递归和循环

贪心选择和排序

最优子结构和无后效性

排序和二分

第 95 题 H5 未作答

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

（1 分）

数据太大

贪心太慢

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

排序不正确

第 96 题 H6 未作答

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

（1 分）

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

$O(n^4)$

$O(n^2)$

$O(n)$

第 97 题 H7 未作答

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

（1 分）

排序

无法优化

哈希

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

第 98 题 H8 未作答

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

（1 分）

记忆化总是更快

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

完全不同

递推总是更快

第 99 题 H9 未作答

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

（1 分）

$O(2^n)$

$O(n \log n)$

$O(n^2)$

$O(n)$

第 100 题 H10 未作答

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

（1 分）

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

贪心不回退

DP 利用重叠子问题

DP 需要最优子结构

重置作答

专题 S06 动态规划与贪心 · 复习强化

判 分 报 告

贪心基础

贪心经典问题

DP 基础概念

线性 DP

背包 DP

区间 DP

S 级 DP

综合与易错

打印

导出 HTML 子卷

判分报告