algorithm - 查找表和动态规划

Question

在旧游戏时代，由于在旧 CPU 中计算这些值的速度很慢，我们习惯于使用查找表来查找 sin 和 cos 等的预计算值。

这被认为是一种动态编程技术吗？或动态规划必须解决总是计算或排序的递归函数？

更新：在动态编程中，关键是要有一个记忆表，这是 sin,cos 查找表的解决方案，那么该技术的真正区别是什么？

score 4 · Accepted Answer

对于我在您的问题中看到的内容，我想说不，这不是动态编程。动态规划更多的是通过解决较小的子问题来解决问题，并创造从较小的子问题中获得问题解决方案的方法。

你的情况看起来更像memoization。

对我来说，如果你的问题是计算cos N，并且你有公式从, , ...,cos i的数组中计算，那么你可以计算，然后计算 i 从 0 到 N。cos 0cos 1cos i - 1cos 1sin 1

可能有人会纠正我:)

关于范式的dynamic programming不同之处还有一段有趣的引述：divide-and-conquer

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

score 4 · Accepted Answer

动态编程是一种编程技术，您可以通过将其拆分为不独立的较小问题来解决难题（这很重要！）。

即使您可以从 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，没有人想要那个！），而不是指数级的计算步骤。

score 0 · Accepted Answer

不，我不认为这是动态编程。由于计算能力有限，正弦和余弦的值作为预先计算的值提供，就像其他数字常数一样。

动态规划技术要解决的问题有很多必要条件。重要的条件之一是我们应该能够将问题分解为递归可解决的子问题，然后将这些子问题的结果用作查找表以替换递归中的更高链。所以它既是递归又是记忆。

有关更多信息，您可以参考维基百科链接。 http://en.wikipedia.org/wiki/Dynamic_programming

3 回答 3