数据结构与算法 · 单选题 · 第 56 题
计算机基础面试八股 · 第 56 题
一个问题适合用动态规划求解,通常需要具备哪两个性质?
- A最优子结构和重叠子问题
- B贪心选择性质和局部最优即全局最优
- C子问题相互独立且没有重叠
- D输入数据必须事先有序排列
答案
A A. 最优子结构和重叠子问题
解析
最优子结构保证可以由子问题的最优解组合出原问题的最优解;重叠子问题使「记下子问题答案、避免重复计算」变得有意义。子问题互不重叠时,用分治就够了。贪心选择性质是贪心算法的前提,比动态规划的要求更强。
在线刷这套题:即时判分、错题本、闪卡复习,不用登录就能练。