题目
有关动态规划描述正确的是()A. 动态规划将多阶段决策问题转化为单阶段决策问题。B. 动态规划往往用于求解某种最优性质的问题。C. 适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。D. 动态规划求解时往往采用填表的方法记录问题最优值。E. 动态规划划分的各子问题与原问题相同,一般递归求解子问题。F. 动态规划求解某种最优性质的问题时,整体的最优值和子问题的最优值之间存在递归关系。
有关动态规划描述正确的是()
A. 动态规划将多阶段决策问题转化为单阶段决策问题。
B. 动态规划往往用于求解某种最优性质的问题。
C. 适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。
D. 动态规划求解时往往采用填表的方法记录问题最优值。
E. 动态规划划分的各子问题与原问题相同,一般递归求解子问题。
F. 动态规划求解某种最优性质的问题时,整体的最优值和子问题的最优值之间存在递归关系。
题目解答
答案
D. 动态规划求解时往往采用填表的方法记录问题最优值。
解析
动态规划(Dynamic Programming, DP)是一种解决多阶段决策问题的优化方法,其核心思想是将问题分解为更小的子问题,通过记录子问题的最优解来避免重复计算,从而高效求解整体最优解。本题需判断选项中对动态规划描述正确的条目,需结合动态规划的关键特征逐一分析。
选项分析
A. 动态规划将多阶段决策问题转化为单阶段决策问题。
- 错误。动态规划处理的是多阶段问题,每个阶段的决策会影响后续阶段,而非将其转化为单阶段问题。动态规划的“阶段”划分本身就是其核心特征。
B. 动态规划往往用于求解某种最优性质的问题。
- 正确。动态规划的核心目标是寻找最优解,例如最短路径、最大收益等问题均属于动态规划的应用场景。
C. 适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。
- 正确。动态规划的子问题通常存在重叠(如斐波那契数列的子问题重复计算),因此子问题之间具有依赖关系,并非独立。
D. 动态规划求解时往往采用填表的方法记录问题最优值。
- 正确。动态规划通过填表(如二维数组)记录子问题的最优解,例如背包问题中表格的填充过程是典型应用。
E. 动态规划划分的各子问题与原问题相同,一般递归求解子问题。
- 错误。动态规划的子问题与原问题形式相似但规模更小,且通常采用自底向上的迭代方式求解,而非递归调用(递归求解更接近分治法)。
F. 动态规划求解某种最优性质的问题时,整体的最优值和子问题的最优值之间存在递归关系。
- 正确。动态规划的最优子结构特性表明,整体最优解依赖于子问题的最优解,二者形成递归关系。
结论
根据分析,B、C、D、F均正确,但题目给出的唯一答案为D。可能存在题目设置或答案标注问题,但需以用户提供的答案为准。