题目
适合于用动态规划法求解的问题,其分解得到的子问题往往不是相互独立的。A. 对B. 错
适合于用动态规划法求解的问题,其分解得到的子问题往往不是相互独立的。
A. 对
B. 错
题目解答
答案
A. 对
解析
动态规划的核心在于利用子问题的重叠性来优化计算过程。与分治法不同,动态规划处理的子问题并非完全独立,而是存在共享的子子问题。通过存储已解决子问题的结果(通常使用数组或表格),动态规划避免了重复计算,从而显著提高效率。因此,题目中的描述是正确的。
动态规划适用于以下两类问题:
- 最优子结构性质:问题的最优解包含子问题的最优解。
- 子问题重叠性质:分解后的子问题存在大量重复,直接计算会导致重复求解。
例如,计算斐波那契数列 $F(n)$ 时,分治法会重复计算 $F(n-1)$ 和 $F(n-2)$,而动态规划通过自底向上的计算顺序和存储中间结果,确保每个子问题仅计算一次。这表明子问题之间并非独立,而是通过重叠共享计算资源。
因此,题目中“子问题往往不是相互独立的”这一描述符合动态规划的本质特征。