算法分析与设计这门课程第三章动态规划的知识点有哪些？

发布网友发布时间：2022-03-24 06:02

共2个回答

懂视网时间：2022-03-24 10:23

动态规划的基本要素如下：

　　1、最优子结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

　　2、重叠子问题。可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要此子问题时，只要简单地用常数时间查看一下结果。通常，不同的子问题个数随问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

热心网友时间：2022-03-24 07:31

算法分析与设计这门课第三章动态规划的知识点包含章节导引,第一节动态规划算法的概念,第二节动态规划算法的基本步骤,第三节动态规划算法的基本要素,第四节动态规划算法设计策略,课后练习,。