最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构。
（简答题）
请说明动态规划方法为什么需要最优子结构性质？
正确答案
答案解析
略
相似试题
（填空题）
最优子结构性质的含义是（）。
（填空题）
贪心算法的基本要素是（）和最优子结构性质。
（简答题）
请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。 ⑴若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 ⑵如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 ⑶描述一个城市的设计和规划。
（简答题）
在绘制类图时，第一步就是发现类，最常用的方法是什么？请简要说明它的使用方法。
（简答题）
用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。 （2）给定两个序列X={B，C，D，A}，Y={A，B，C，B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
（填空题）
动态规划算法有一个变形方法（）。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。
（判断题）
在程序运行过程中，对于动态数据结构结的分配和回收需要采用动态存储管理的方法。
（简答题）
请叙述动态规划算法与贪心算法的异同。
（简答题）
写出0/1背包问题的动态规划方程，并简要说明。
