当前位置：首页 > news >正文

算法分析与设计——动态规划复习题（待更新

news 2025/8/24 8:20:44

检测题：

组合优化问题的目标函数通常不包括以下哪种形式？
A. 需最小化的代价函数
B. 需最大化的回报函数
C. 需满足的硬约束条件
D. 需最小化的能量函数
答案：C
关于约束条件的说法，以下哪项是正确的？
A. 硬约束可以通过惩罚函数间接处理
B. 软约束是必须严格满足的条件
C. 硬约束是必须满足的条件，软约束通过惩罚处理
D. 所有约束条件都必须转化为硬约束
答案：C
动态规划技术特别适合解决以下哪种问题？
A. 目标函数不明确的组合优化问题
B. 具有重叠子问题和最优子结构的问题
C. 仅包含软约束的问题
D. 需要随机搜索的复杂问题
答案：B
组合优化问题中，“可行解”的定义是？
A. 使目标函数最小的解
B. 满足所有约束条件的解
C. 忽略软约束后的近似解
D. 仅满足硬约束的解
答案：B
动态规划的核心思想是：
A. 通过暴力枚举所有可能的解
B. 将问题分解为子问题并避免重复计算
C. 仅处理单一阶段的优化问题
D. 完全依赖启发式规则
答案：B

动态规划的必要条件不包括以下哪一项？
A. 多阶段决策问题
B. 子问题之间存在重叠
C. 目标函数具有最优子结构
D. 子问题之间完全独立
答案：D
“最优子结构”性质的含义是？
A. 问题的最优解包含子问题的最优解
B. 所有子问题必须完全相同
C. 问题的规模必须从小到大递增
D. 必须使用递归方法求解
答案：A
动态规划与分治法的本质区别在于？
A. 动态规划必须使用迭代实现
B. 分治法要求子问题不重叠
C. 动态规划需要记录子问题的解
D. 分治法适用于多阶段决策问题
答案：B
以下哪种场景适合动态规划？
A. 归并排序中对数组的拆分与合并
B. 斐波那契数列的递归计算（未优化）
C. 最短路径问题中局部最优导致全局最优
D. 随机生成解的蒙特卡洛方法
答案：C
动态规划“以空间换时间”的核心原因是？
A. 必须使用贪心策略
B. 需要存储所有可能的解
C. 记录子问题的解以避免重复计算
D. 问题必须分解为固定大小的子问题
答案：C

判断题

动态规划必须采用自顶向下的递归实现。
答案：错误（动态规划通常用自底向上的迭代实现，递归实现需配合记忆化）
若一个问题没有重叠子问题，动态规划将退化为分治法。
答案：正确
最短路径问题的最优子结构性质是指：从起点到终点的最短路径包含路径上任意两点的最短路径。
答案：正确

填空题

动态规划的两个必要条件是 最优子结构 和 重叠子问题。
动态规划通过 记录子问题的解（或记忆化） 来避免重复计算。
归并排序不属于动态规划应用，因为它 不存在重叠子问题。

应用题

场景：设计一个算法计算斐波那契数列的第 nn 项。

递归实现（无优化）的时间复杂度是多少？为什么？
如何用动态规划优化？请说明具体方法及其优势。

参考答案：

时间复杂度为 O(2n)O(2n)，因为递归过程中存在大量重复计算（如 F(n−2)F(n−2) 被多次计算）。
使用动态规划：
- 自底向上迭代：从 F(0)F(0) 和 F(1)F(1) 开始，逐步计算到 F(n)F(n)，保存中间结果。
- 记忆化递归：在递归中记录已计算的 F(k)F(k) 值，避免重复调用。
- 时间复杂度优化为 O(n)O(n)，空间复杂度为 O(1)O(1)（迭代法）或 O(n)O(n)（记忆化）。

综合题

问题：分析背包问题（0-1 Knapsack）是否满足动态规划的两个必要条件，并简述动态规划的求解思路。
答案：

最优子结构：若当前物品是否放入背包的决策能推导出剩余容量和剩余物品的最优解，则满足最优子结构。
重叠子问题：不同容量和物品组合的子问题可能被多次计算（如容量为 ww 时选择前 ii 个物品）。
求解思路：

定义 dp[i][w]dp[i][w] 表示前 ii 个物品在容量 ww 下的最大价值。
递推方程：
dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−weighti]+valuei)dp[i][w]=max(dp[i−1][w],dp[i−1][w−weighti]+valuei)
自底向上填表，最终 dp[n][W]dp[n][W] 即为最优解。

知识点复习：

一、组合优化问题是什么？

是指在有限的离散解集合中，找到满足约束条件且使目标函数最优（最小化或最大化）的解，而且动态规划是解决组合优化问题的重要工具，组合优化问题 ≈ 在一大堆可能的“组合”里，挑出最好的那个。

1、举个栗子 🌰：

假设你周末要完成3件事：取快递、买菜、去银行。
目标：找出最短路线，少走路！
可能的组合：

家 → 快递 → 菜场 → 银行 → 家
家 → 菜场 → 银行 → 快递 → 家
家 → 银行 → 快递 → 菜场 → 家
...（还有很多种顺序）

你需要挨个算每条路线的总距离，然后选最短的那条。这就是一个典型的组合优化问题！

2、为什么难？

如果事情变多（比如有10件事），可能的路线组合会爆炸式增长（比如10! = 362万种）。这时你不可能一个个试，得用“聪明的方法”快速找到最优解。

3、关键点：

组合：解是多个元素的排列或选择（比如路线顺序、带哪些物品）。
优化：有明确的目标（比如最短、最便宜、最快）。
限制条件：必须满足某些规则（比如背包不能超重、时间不能超时）。

4、生活中的组合优化问题：

网购凑满减：怎么选商品凑到满减，花最少的钱？
旅行计划：7天去5个城市，怎么安排路线最省时间？
排课表：如何把课程排进教室，不冲突且教室利用率最高？

5、一句话总结：

组合优化就是——在众多可能的“排列组合”里，用聪明的方法快速找出“最好用”的那个！
（比如你的大脑自动选了最短路线，而不是挨个试走一遍 😉）

二、矩阵链乘法问题

一句话总结：

矩阵链乘法问题就是——找一种给矩阵相乘“加括号”的方式，让总的计算量（乘法次数）最少！

1、举个栗子 🌰：

假设有3个矩阵要连乘：

A₁ 是 10×100 的矩阵
A₂ 是 100×5 的矩阵
A₃ 是 5×50 的矩阵

它们的乘积有两种加括号方式：

(A₁A₂)A₃
- 先算 A₁A₂：计算量 = 10×100×5 = 5000
- 再算 (结果)×A₃：计算量 = 10×5×50 = 2500
- 总计算量 = 5000 + 2500 = 7500
A₁(A₂A₃)
- 先算 A₂A₃：计算量 = 100×5×50 = 25000
- 再算 A₁×(结果)：计算量 = 10×100×50 = 50000
- 总计算量 = 25000 + 50000 = 75000

结论：不同的加括号方式，计算量差了10倍！

2、动态规划解决思路：

拆分子问题：
- 用 m[i][j] 表示计算从第 i 到第 j 个矩阵的最小乘法次数。
- 例如：m[1][3] 表示计算 A₁A₂A₃ 的最小乘法次数。
递推公式：
- 如果 i = j（单个矩阵），m[i][j] = 0。
- 如果 i < j：
  m[i][j] = min{ m[i][k] + m[k+1][j] + (第i个矩阵的行数 × 第k个矩阵的列数 × 第j个矩阵的列数) } 其中 k 是分割点（比如在 A₁ 和 A₂ 之间分割，或在 A₂ 和 A₃ 之间分割）。
自底向上填表：
从最小的子问题开始计算（比如先算2个矩阵相乘，再算3个矩阵相乘...）。

3、练习题

选择题

动态规划解决矩阵链乘法问题的核心思想是：
A. 暴力枚举所有可能的括号组合
B. 利用最优子结构和重叠子问题
C. 直接计算所有矩阵的乘积
答案：B
若矩阵链的维度为 <5, 10, 3, 12>，计算 A₁A₂A₃ 的最优分割点 k 是：
A. 1
B. 2
C. 无法确定
答案：B（计算方式见下边的计算题）

计算题

题目：给定矩阵链 <30×35, 35×15, 15×5>，求最小乘法次数。
步骤：

计算所有可能的 k 值（分割点）：
- k=1（分割为 A₁(A₂A₃)）：
  - m[1][1] + m[2][3] + 30×35×5 = 0 + (35×15×5) + 5250 = 2625 + 5250 = 7875
- k=2（分割为 (A₁A₂)A₃）：
  - m[1][2] + m[3][3] + 30×15×5 = (30×35×15) + 0 + 2250 = 15750 + 2250 = 18000
最小计算量 = 7875
答案：7875 次乘法