GESP 7级客观题｜二维动态规划｜课后作业

考试频率：高频。本卷共 6 题。

1. 给定一个数字序列 A1，A2，A3，...，An ，要求 i 和 j （ 1<=i<=j<=n )，使 Ai+…+Aj 最大，可以使用动态规划方法来求解。( )

   {{ select(1) }}

• 对
• 错

2. 以下关于动态规划的说法中，错误的是（ ）。

   {{ select(2) }}

• 动态规划方法通常能够列出递推公式。
• 动态规划方法的时间复杂度通常为状态的个数。
• 动态规划方法有递推和递归两种实现形式。
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

3. 动态规划方法将原问题分解为一个或多个相似的子问题，因此必须使用递归实现。（ ）

   {{ select(3) }}

• 对
• 错

4. 动态规划有递推实现和递归实现， 对于很多问题， 通过记录⼦问题的解， 两种实现的时间复杂度是相同的。

   {{ select(4) }}

• 正确
• 错误

5. 动态规划算法通常有递归实现和递推实现。但由于递归调用在运行时会由于层数过多导致程序崩溃，有些动态规划算法只能用递推实现。

   {{ select(5) }}

• 对
• 错

6. 以下关于贪心法和动态规划的说法中，错误的是（ ）。

   {{ select(6) }}

• 对特定的问题，贪心法不一定适用。
• 当特定的问题适用贪心法时，通常比动态规划的时间复杂度更低。
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。
• 采用动态规划的算法一定具有多项式时间复杂度。