将一个规模较大的问题分割成若干个较小的类型相同且互相独立的子问题分别求解,而通过这些子问题的解能合并到原问题的解。这种求解方法叫
A: 分治法
B: 减治法
C: 动态规划法
D: 贪心法
A: 分治法
B: 减治法
C: 动态规划法
D: 贪心法
举一反三
- 将一个较大规模的问题分解为较小规模的子问题，求解子问题、合并子问题的解得到整个问题的解的算法是（）。 A: 贪心法 B: 分治法 C: 动态规划法 D: 回朔法
- 动态规划法和分治法求解问题时,都是将规模较大的问题分解为规模较小的同类子问题来求解,但分治法要求分解出来的子问题相互独立,而动态规划法要求子问题具有重叠性。
- 对于分治法，如果原问题可以分割成m个子问题，并且这些子问题都可解，然后求解这些子问题，那么就可以用这些子问题的解求出原问题的解
- 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（ ）
- 分治法求解很自然导致一个递归算法的主要原因是( )。 A: 子问题规模比原问题小 B: 子问题很容易求解 C: 子问题与原问题类型相同 D: 子问题的解都不一样