什么是动态规划？(dynamic programming?)
当提到计算机科学领域时，动态规划描述了一组类似的计算机算法，通过将问题分解为一组较小的问题来解决复杂问题。动态规划最早由Richard Bellman在20世纪50年代创建，它处理的问题要么是重叠的子问题，要么是最优的子结构。要理解动态规划是如何工作的，最好理解这两个术语背后的概念。
重叠子问题描述了复杂的方程，当分解成更小的方程组时，会多次重复使用较小方程的部分以获得答案。例如，一个被告知使用一组数字计算所有可能结果的数学方程可能会多次计算相同的结果，而只计算一次其他结果。动态规划会告诉这个问题，在第一次计算结果之后，它应该保存该结果，然后将答案插入到方程中，而不是再次计算。在处理长而复杂的过程和方程时，这可以节省时间，并使用更少的步骤创建更快的解决方案。
最优子结构通过找到所有子问题的最佳答案，然后创建最佳总体答案来创建解决方案。在把一个复杂的问题分解成更小的问题后，计算机使用一个数学系统来确定每个问题的最佳答案。它根据较小的答案计算原始问题的答案。这一过程确实存在缺陷。虽然它给出了数学上最有效的解决方案，但它可能是也可能不是现实生活中的最佳解决方案，这取决于问题的类型及其与现实世界的关系。
在任何这些操作中，动态规划算法都试图找到解决方案的最短路径。它可以采取两种方法之一来实现这一点。自上而下的方法将方程分解为更小的方程，并在必要时重用这些方程的答案。自下而上的方法尝试在分解方程后求解最小的数学值，然后从那里向上求最大值。这两种方法都可以节省时间，但动态规划只有在原始问题可以分解为更小的方程时才起作用，而这些方程在某个点上可以重新用于求解方程。
- 发表于 2021-12-13 14:36
- 阅读 ( 105 )
- 分类：互联网
你可能感兴趣的文章
动态规划：示例、常见问题和解决方案
... 什么是动态规划(dynamic programming)？ ...
动态拉伸(dynamic stretching)和静态拉伸(static stretching)的区别
...角色。两者之间的本质区别在于练习的方式和时间。 什么是动态拉伸练习(dynamic stretch exercises)？ 动态拉伸运动比静态运动更有活力。当进行动态运动时，拉伸不保持。一系列的动作是通过一系列的伸展运动来完成的。动态...
动态(dynamic)和运动粘度(kinematic viscosity)的区别
...度的方法，而运动粘度是流体的动态粘度除以其密度。 什么是动态粘度(dynamic viscosity)？ Whenever a fluid flows against a surface, the different layers of fluid exert frictional forces between each other, causing them to flow at different speeds. A force needs to be appli...
静止的(static)和动态ip(dynamic ip address)的区别
...而动态地址是经常更改的临时地址。 覆盖的关键领域 1.什么是静态IP地址-定义，功能2.什么是动态IP地址-定义，功能3.静态IP地址和动态IP地址的区别-主要区别比较 关键术语 IP地址，静态IP，动态IP 什么是静态ip地址(a static ip addr...
静止的(static)和动态哈希(dynamic hashing)的区别
...型的散列称为静态散列和动态散列。 覆盖的关键领域 1.什么是静态哈希-定义，功能2.什么是动态哈希-定义，功能3.静态哈希和动态哈希的区别是什么-关键区别的比较 关键术语 哈希、静态哈希、动态哈希 什么是静态哈希(static h...
动态绑定(dynamic binding)和消息传递(message passing)的区别
...绑定和消息传递就是这样两个特性。 覆盖的关键领域 1.什么是动态绑定-定义，功能2.什么是消息传递-定义，功能3.动态绑定和消息传递的区别是什么-关键区别的比较 关键术语 动态绑定、后期绑定、消息传递、面向对象 什么是...
分(divide)和征服(conquer)的区别
...决方案以获得主问题的解决方案 什么是动态规划(dynamic programming)？ 动态规划将主问题分解为若干个较小的子问题，但它不能独立地求解这些子问题。它存储子问题的结果，以便在解决类似的子问题时使用。存储子问题的结果称...
静止的(static)和动态路由(dynamic routing)的区别
...个称为路由表的表来维护路径信息。 覆盖的关键领域 1.什么是静态路由-定义，功能2.什么是动态路由-定义，功能3.静态路由和动态路由的区别-关键区别的比较 关键术语 动态路由，非自适应路由，路由器，静态路由，网络 什么...
静止的(static)和动态链接(dynamic linking)的区别
...其他文件相连。 Assume that there are some changes in the external programs. In that case, it is necessary to recompile and re-link again. Otherwise, the existing executable file does not reflect these changes. Furthermore, in statistical linking, all the modules and libraries are available as...
什么是动态耳机？(dynamic headphones?)
有很多方法可以对耳机进行分类，无论是按风格、功率、品牌还是音质。但所有耳机都分为两大类：动态耳机和静电耳机。这些类别的耳机基于用于产生声音的技术类型。...
0 篇文章
