在旧游戏时代,我们习惯于拥有一个预先计算好的正弦和余弦值等数值表格,因为在那个老版CPU上计算这些值的速度很慢。这是否被视为动态规划技术?或者动态规划必须解决一直被计算或类似地递归的函数?
更新: 在动态规划中,关键是要有一个备忘录表,这就是sin、cos查找表的解决方案,那么这种技术的区别是什么呢?
更新: 在动态规划中,关键是要有一个备忘录表,这就是sin、cos查找表的解决方案,那么这种技术的区别是什么呢?
动态规划是一种编程技术,通过将一个困难的问题分解成较小的、但并不独立的子问题来解决它(这很重要!)。
即使您可以从cos i-1计算cos i,这仍然不是动态规划,只是递归。
动态规划的经典例子是背包问题:http://en.wikipedia.org/wiki/Knapsack_problem
您想用N个物品填满大小为W的背包,每个物品都有其大小和价值。由于您不知道哪种排列方式最好,因此您会“尝试”每一种情况。
递推公式将类似于:
OPT(m,w) = MAX ( OPT(m-1, w), //if I don't take this object
OPT(m-1, w - w(m)) //If i take it
cos N
,并且您有公式可以从cos 0
、cos 1
、...、cos i-1
的数组中计算cos i
,那么您可以计算cos 1
、sin 1
,并且从i从0到N运行您的计算。动态规划
与分治
范例区分开来:不,我认为这不是动态规划。由于计算能力有限,正弦和余弦的值被作为预先计算的值提供,就像其他数字常量一样。
要使用动态规划技术解决问题,有许多必要条件。其中一个重要条件是我们应该能够将问题分解成可递归求解的子问题,这些子问题的结果可以用作查找表来替换递归中的更高链。因此,它既是递归又是记忆。
有关更多信息,您可以参考维基百科链接。 http://en.wikipedia.org/wiki/Dynamic_programming
此外,本课程的第19讲将为您概述动态规划。 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-19-dynamic-programming-i-fibonacci-shortest-paths/