第三章 动态规划：本章主要讲授动态规划算法的总体思想、基本步骤和基本要素等内容，学习如何使用动态规划算法求解最长公共子序列、最大子段和、最长递增子序列、0-1背包问题等经典问题，学习相应的动态规划求解算法的设计、分析与实现。3.1动态规划概述:学习动态规划算法的总体思想、基本步骤、基本要素和整体结构等内容。[多选题]能够使用动态规划算法来求解的问题通常需要具备两个重要的性质，它们分别是( )。
3.2动态规划之最长公共子序列（上）:学习最长公共子序列问题的描述以及使用动态规划求解该问题的算法设计。
3.3动态规划之最长公共子序列（下）:学习使用动态规划求解最长公共子序列问题的算法实现、分析和改进。
3.4动态规划之最大子段和:学习最大子段和问题的描述以及如何使用动态规划算法求解该问题，包括算法的设计、分析与实现。
3.5动态规划之最长递增子序列:学习最长递增子序列问题的描述以及如何使用动态规划算法求解该问题，包括算法的设计、分析与实现。
3.6动态规划之0-1背包问题（上）:学习0-1背包问题的描述以及使用动态规划求解该问题的算法设计。
3.7动态规划之0-1背包问题（下）:学习使用动态规划求解0-1背包问题的算法实现、分析和扩展。
贪心选择性质
最优子结构
重叠子问题
递归调用
答案：最优子结构重叠子问题
[多选题]关于备忘录法，以下说法正确的是( )。
备忘录法又称为记忆化搜索，它采用一种自底向上的方式求解问题。
备忘录法可以避免相同子问题的重复求解。
备忘录法的控制结构与直接使用递归方法的控制结构相同。
备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。[单选题]字符序列abcde与字符序列abdge的最长公共子序列长度为( )，最长公共子串长度为( )。
4,6
4,2
4,1
3,5[单选题]使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为( )。
O(n^2)
O(m^n)
O(nlogm)
O(n*m)[单选题]输入数组（-1, 0, 1, -2, 3），它的最大子段和是( )。
3
1
4
2[单选题]序列（1，7，3，4，9，2，3）的最长递增子序列的长度为( )。
1
2
3
4[单选题]使用穷举法求解最长递增子序列的时间复杂度为( )。
O(n^2)
O(n^n)
O(n*2^n)
O(nlogn)[单选题]使用动态规划算法求最大子段和的时间复杂度为( )。
O(2^n)
O(logn)
O(nlogn)
O(n)[多选题]某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额分别为15,10,12,8（万元），投资收益分别为12,8,9,5（万元），投资总额为30万元，选择项目( )可以使总收益最大。（不允许部分投资某个项目）
B
C
D
A[判断题]在使用动态规划算法求解0-1背包问题时，若m[i][j]=m[i+1][j-w[i]]+v[i]，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少w[i]，价值增加v[i]。
错
对
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
