一、单选题

第 1 题

0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（ ）。

{{ select(1) }}

• 内层 j 必须从小到大，否则会漏解
• 内层 j 必须从大到小，否则同一件物品会被用多次
• j 从大到小或从小到大都一样
• 只要 dp 初始为 0 ，方向无所谓

---

第 2 题

以下关于动态规划的说法中，错误的是（ ）。

{{ select(2) }}

• 动态规划方法通常能够列出递推公式。
• 动态规划方法的时间复杂度通常为状态的个数。
• 动态规划方法有递推和递归两种实现形式。
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

---

第 3 题

给定n个物品和一个最大承重为W 的背包，每个物品有一个重量wt[i] 和价值val[i] ，每个物品只能选择放或 不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过W ，则横线上应填写（ ）。

{{ select(3) }}

• dp[w] = max(dp[w], dp[w] + val[i]);
• dp[w] = dp[w - wt[i]] + val[i];
• dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);
• dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

---

第 4 题

以下关于动态规划算法特性的描述，正确的是（ ）。

{{ select(4) }}

• 子问题相互独立，不重叠
• 问题包含重叠子问题和最优子结构
• 只能从底至顶迭代求解
• 必须使用递归实现，不能使用迭代

---

第 5 题

给定n个物品和一个最大承重为 W的背包，每个物品有一个重量wt[i] 和价值val[i] ，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过W 。关于下面代码，说法正确的是（ ）。

{{ select(5) }}

• 该算法不能处理背包容量为 0 的情况
• 外层循环 i 遍历背包容量，内层遍历物品
• 从大到小遍历 w 是为了避免重复使用同一物品
• 这段代码计算的是最小重量而非最大价值

---

第 6 题

小杨在玩一个闯关游戏，从第 1 关走到第 4 关。每一关的体力消耗如下（下标表示关卡编号）： cost = [ 0, 3, 5, 2, 4 ] ，其中 cost[i] 表示到达第 i 关需要消耗的体力， cost[0]=0 表示在开始状态，体力消耗为 0。小杨每次可以从当前关卡 前进 1 步或 2 步。按照上述规则，从第 1 关到第 4 关所需消耗的最小体力为 7。 ( )

{{ select(6) }}

• T
• F

---

第 7 题

下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是O(2^n) 。 ( )

{{ select(7) }}

• T
• F

---

第 8 题

下面代码采用动态规划求解零钱兑换问题：给定n种硬币，第i种硬币的面值为coins[i - 1]，目标金额为amt，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回-1。( )

{{ select(8) }}

• T
• F

---

第 9 题

在动态规划解决一维硬币找零问题时，若硬币面额为 [1, 3, 4] ，目标金额为 6 ，则最少需要 2 枚硬币 （3+3）。 ( ) {{ select(9) }}

• T
• F

---

第 10 题

在解决简单背包问题时，动态规划的状态转移方程如下： 该方程表示：在考虑第i个物品时，当前背包容量为w，如果不放物品i，则最大价值是dp[i-1][w]；如果放入物品i，则最大价值是dp[i-1][w - weights[i-1]] + values[i-1]，其中数组weights和values分别表示所有物品的重量和价值，数组下标从0开始。( )

{{ select(10) }}

• T
• F

---