查表与动态规划

Question

在旧游戏时代，由于在旧CPU中计算这些值的速度慢，我们习惯于有一个预先计算出的sin和cos，..etc值的查表。

这被认为是一种动态规划技术吗？或者动态规划必须解决一个递归函数，它总是被计算或者是某种程度上的？

更新:在动态编程中，关键是要有一个回忆录表，这是sin的解决方案，因为查找表，那么技术的真正区别是什么？

Answer 1

我要说的是我在你的问题中看到的，不，它不是动态编程。动态规划更多地是通过解决较小的子问题来解决问题，并从较小的子问题中获得问题的解决方法。

您的情况看起来更像回忆录。

对我来说，如果您的问题是计算cos N，并且有公式从cos 0、cos 1、.、cos i - 1数组中计算cos i，那么就可以考虑DP，这样就可以计算cos 1、sin 1，并从0到N运行I的计算。

也许有人会纠正我:)

关于dynamic programming与divide-and-conquer范式的不同之处，也有一句有趣的话：

要使动态规划适用，一个问题必须具备两个关键属性:最优子结构和重叠子问题。如果一个问题可以通过组合不重叠子问题的最优解来解决，那么这种策略被称为“分而治之”。这就是为什么合并和快速排序不属于动态规划问题的原因。

Answer 2

动态编程()是一种编程技术，通过将难题分解成不独立的小问题(这是很重要的！)。

即使您可以从cos i-1计算cos i，这仍然不是动态规划，只是递归。

动态规划经典例子是背包问题：问题

您希望用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 

添加初始案例，这就是解决问题的方法。当然，您应该构建以m= 0，w=0开始的解决方案，然后迭代到m=N和w= W，这样就可以重用以前的计算值。

使用这种技术，您可以在N*W时间内找到将对象带入背包的最佳组合(当然，这在输入大小上不是多项式，否则P= NP，没有人想要它！)，而不是一个指数级的计算步骤。

Answer 3

不我不认为这是动态规划。由于计算能力有限，正弦波和余弦的数值都是预先计算出来的，就像其他数值常数一样。

动态规划技术中需要解决的问题有许多必要条件。一个重要的条件是，我们应该能够将问题分解为递归可解子问题，这些子问题的结果可以作为查找表来代替递归中的更高链。因此，它既是递归，也是内存。

有关更多信息，您可以参考维基百科链接。编程

另外，本课程的第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/