动态规划的基本要素（动态规划的基本要素是最优子结构性质与贪心选择性质）
时间：2022-07-07人气：作者：未知
动态规划的基本要素如下：
1、最优子结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
2、重叠子问题。可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要此子问题时，只要简单地用常数时间查看一下结果。通常，不同的子问题个数随问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。
最新文章
数学符号≌是全等于的意思，表示两个图形能完全重合，包括形状和面积，全等于是程序设计的一种逻辑运算符。数学符号的发明及使用比数字要
(57)人喜欢2024-10-07
数学符号≡是恒等的意思，≡是无条件等于，不论条件怎么变，都是成立的。恒等式是无论其变量如何取值，等式永远成立的算式。恒等式成立的范
(56)人喜欢2024-10-07
数学期望可以是负数，期望等于随机变量乘以相应的概率，随机变量可以取负，因此期望就可能为负。期望值并不一定等同于常识中的“期望”，“
(62)人喜欢2024-10-07
数学感叹号是阶乘的意思，阶乘是基斯顿·卡曼于1808年发明的运算符号，是数学术语。一个正整数的阶乘是所有小于及等于该数的正整数的积，
(56)人喜欢2024-10-07
-
数学符号≌是全等于的意思，表示两个图形能完全重合，包括形状和面积，全等于是程序设计的一种逻辑运算符。数学符号的发明及使用比数字要
(57)人喜欢2024-10-07 -
数学符号≡是恒等的意思，≡是无条件等于，不论条件怎么变，都是成立的。恒等式是无论其变量如何取值，等式永远成立的算式。恒等式成立的范
(56)人喜欢2024-10-07 -
数学期望可以是负数，期望等于随机变量乘以相应的概率，随机变量可以取负，因此期望就可能为负。期望值并不一定等同于常识中的“期望”，“
(62)人喜欢2024-10-07 -
数学感叹号是阶乘的意思，阶乘是基斯顿·卡曼于1808年发明的运算符号，是数学术语。一个正整数的阶乘是所有小于及等于该数的正整数的积，
(56)人喜欢2024-10-07
