（单选题）
用动态规划算法解决最大字段和问题，其时间复杂性为（）
Alogn
Bn
Cn2
Dnlogn
正确答案
答案解析
略
相似试题
（简答题）
给定由n个整数（其中可能有负数）组成的序列a1，a2，...an，求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为： 动态规划解决方案：记，则对于n个整数序列的最大子段和问题，即为所求。 动态规划递归式： 问：对于实例：（a1，a2，...a6）＝（－2，11，－4，13，－5，－2）按照前述动态规划递归式填充b数组，算法运行完毕后，请写出b数组中的数值，和最大子段和的值。
（简答题）
用动态规划算法解0-1背包问题：n=5，w=[2，9，4，6，7]，p=[6，10，12，8，13]，c=15。
（单选题）
一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。
（填空题）
问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。
（填空题）
最大子段和：动态规划算法。横线处填（）
（判断题）
动态规划法的思想是把大问题归结为大量不同规模子问题，而子问题的求解采用一次计算并保存，以后查表的方法来解决，从而节约计算量。因此可以说，动态规划方法是以空间换时间的方法。
（填空题）
算法就是用计算机解决问题的（）和步骤。
（填空题）
动态规划算法有一个变形方法（）。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。
（填空题）
动态规划算法的基本思想是将待求解问题分解成若干（），先求解（），然后从这些（）的解得到原问题的解。
