第七章 动态规划：介绍动态规划的基本思想、基本步骤、基本要素、复杂度分析。动态规划和分治算法、贪心算法、备忘录方法的联系和区别。递推关系和子问题的联系和区别。动态规划的分类、常用问题和设计与分析方法。7.1动态规划:引入兔子序列和赋权区间调度，介绍动态规划的基本思想、基本步骤和基本要素，动态规划和分治、贪心、备忘录方法的联系和区别。[判断题]动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
7.2数字三角形:引入数字三角形问题，介绍正推与反推、递推关系和状态转移方程。
7.3增加变量:介绍0-1背包、恰好装满、完全背包和多重背包问题的动态规划算法。
7.4区间动归:引入矩阵连乘介绍区间动归的算法和加括号的方法。
7.5DAG图:引入实例介绍DAG图的动归算法，拓扑排序算法。
7.6树图动归（上）:介绍了负权的最短路算法，负环的检测和处理。
7.7树图动归（下）:介绍任意点间的最短路算法、树状动归和树上最大独立集问题的动归算法。
7.8序列比对:介绍序列比对和最长公共子序列问题的动归算法。
错
对
答案：√
[判断题]0/1背包问题的动态规划算法是多项式时间算法。
错
对[判断题]对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法。
错
对[判断题]Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
错
对[单选题]含负权的最短路问题一般使用（）求解。
贪心算法
分治算法
网络流算法
动态规划[单选题]动态规划算法的基本要素有（ ）和最优子结构性质。
独立子问题性质
分解合并性质
贪心选择性质
重叠子问题性质[单选题]下面不是动态规划的基本方法有（）。
区间变量
增加变量
多重选择
舍入[多选题]最短路算法中适用于稀疏图的是（）
Dijkstra算法
Bellman算法
SPFA算法
Floyd算法[多选题]分治算法与动态规划算法的相同点是（）
递推关系
最优子结构
子问题重叠
子问题独立
[判断题]DAG上最短路，固定起点和终点没有意义。
对
错[判断题]DAG图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度 。
对
错[判断题]树上最大权独立集不包含u，可能包含儿子结点，也可能不包含儿子结点。
错
对[判断题]SPFA算法的时间复杂度为O（mn）
错
对
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
