问题标签 [dynamic-programming]

上面的代码示例使用 memoization 根据一些输入计算递归公式n。我知道这使用了记忆化，因为我编写了一个使用相同公式的纯递归函数，但是对于更大的n. 我以前从未使用过向量，但我做了一些研究，我理解了它们的概念。我知道记忆应该存储每个计算的值，这样它就可以简单地检索已经计算过的值，而不是再次执行相同的计算。

我的问题是：这个记忆如何，它是如何工作的？我似乎无法在代码中看到它检查 n 的值是否已经存在。另外，我不明白if(as[n]<=0). 这个公式可以产生正值和负值，所以我不确定这个检查在寻找什么。

谢谢，我想我已经接近理解它是如何工作的了，它实际上比我想象的要简单一些。

我不认为序列中的值永远是 0，所以这应该对我有用，因为我认为 n 必须从 1 开始。

但是，如果零在我的序列中是一个可行的数字，那么我可以解决它的另一种方法是什么？例如，如果五个永远不会出现怎么办？我只需要用五个填充我的向量吗？

编辑：哇，我在检查代码和输入这个代码时收到了很多其他的回复。谢谢大家的帮助，我想我现在明白了。

When have you ever directly applied the concepts of dynamic programming to solve a problem in the field? It's sometimes not evident how it can be applied when using it to solve a made-up instance of the knapsack problem.

我有一个与子集和问题有关的问题，我想知道这些差异是否使它更容易，即可以在合理的时间内解决。

给定一个值 V、一个集合大小 L 和一个数字序列 [1,N] S，S 中有多少个大小为 L 的子集总和小于 V？

这在三个方面不同于子集和问题：

1. 我关心有多少子集小于给定值，而不是有多少相等。
2. 子集大小是固定的。
3. 我关心有多少集合总和小于 V，而不仅仅是是否存在。

有没有合理有效的算法来解决这个问题？

编辑：显然，这可以使用组合生成算法在 O(N choose L) 中完成。我真正感兴趣的是可以显着加快速度的巧妙技巧。

我在这个三角形中有大量从 0 到 4 的整数数组。我正在尝试使用 Ruby 学习动态编程，并希望在计算三角形中满足三个标准的路径数方面得到一些帮助：

1. 您必须从包含 70 个元素的行中的零点之一开始。
2. 您的路径可以在您正上方的一排（如果正上方有数字）或向左对角线的一排。这些选项之一始终可用
3. 在第一行达到零的路径总和必须为 140。

例如，从底行的第二个零开始。您可以直接向上移动到 4 的左侧或对角线。在任何一种情况下，您到达的数字都必须添加到您访问过的所有数字的运行计数中。您可以从 1 移动到正上方的 2（运行总和 = 3）或左侧对角线的 0（运行总和 = 1）。

更新

经过更多阅读，可以使用以下递归关系给出解决方案：

这现在开始变得有意义了，除了 C 部分。我将如何确定最小值 k？我想这意味着您可以遍历所有可能的 k 值并仅存储 ( l(k,i) + dist(pk,pj)?

是的，这绝对是我在学校学习的一个问题。我们正在研究旅行商问题的双调旅行。

无论如何，假设我有 5 个顶点 {0,1,2,3,4}。我知道我的第一步是按 x 坐标增加的顺序对它们进行排序。从那里开始，我对如何通过动态编程完成这一点有点困惑。

我正在阅读我应该扫描已排序节点的列表，并为两个部分（初始路径和返回路径）维护最佳路径。我对如何计算这些最佳路径感到困惑。例如，我如何知道是否应该在初始路径或返回路径中包含给定节点，因为它不能同时包含在两者中（端点除外）。回想一下动态编程中的斐波那契，你基本上从你的基本情况开始，然后继续前进。我想我要问的是如何开始解决双音旅行商问题？

对于像斐波那契数字这样的东西，动态规划方法非常清楚。但是，我不知道我是否只是过于密集或什么，但我很困惑试图解决这个问题。

感谢您的关注！

注意：我不是在寻找完整的解决方案，但至少有一些好的提示可以帮助我入门。例如，如果这是斐波那契问题，可以说明前几个数字是如何计算的。请让我知道如何改进这个问题。

好的，这更像是一个后续问题：如何计算旅行商双调旅行的最佳路径？

首先，对于旅行商问题的双调旅行，我有以下递归关系：

l是以前结果的表格。我的问题是 C 部分：假设l(k,i)和dist(pk,pj)已定义，我将如何在 Java 中实现 C 部分？k我最初的想法是我从1to迭代i并存储 的最小结果(l(k,i) + dist(pk,pj))，但我认为这是不对的。

例如：

这似乎是一个愚蠢的问题（可能是，我严重缺乏睡眠），但我希望有人能帮忙。

有一个数字列表。
该列表将被分成 2 个大小相等的列表，总和的差异最小。必须打印总和。

在某些情况下，以下代码算法是否有错误？

我如何优化和/或 pythonize 这个？

问题来自http://www.codechef.com/problems/TEAMSEL/

“假设你想用一排 4×1 和 6×1 的乐高积木拼成一个实心面板。为了结构强度，积木之间的空间绝不能在相邻的行中排列。例如，所示的 18×3 面板下面是不可接受的，因为前两行块之间的空间对齐。

构建 10×1 面板有 2 种方式，构建 10×2 面板有 2 种方式，构建 18×3 面板有 8 种方式，构建 36×5 面板有 7958 种方式。

构建 64×10 面板有多少种不同的方法？答案将适合 64 位有符号整数。编写程序计算答案。你的程序应该运行得非常快——当然，它不应该超过一分钟，即使在旧机器上也是如此。让我们知道您的程序计算的值，您的程序计算该值所用的时间，以及您在哪种机器上运行它。包括程序的源代码作为附件。"

我最近收到了一个编程难题，并且一直在绞尽脑汁试图解决它。我使用 c++ 编写了一些代码，我知道这个数字很大......我的程序运行了几个小时，然后我决定停止它，因为即使在慢速计算机上也需要 1 分钟的运行时间。有没有人见过类似的谜题？已经有几个星期了，我不能再提交了，但这真的让我很烦恼，我无法正确解决它。关于使用算法的任何建议？或者也许可能的解决方法是“开箱即用”。我采用的是制作一个程序，该程序构建每个可能的 4x1 和 6x1 块“层”以制作 64x1 层。结果证明有大约 3300 个不同的层。然后我让我的程序运行并将它们堆叠到所有可能的 10 层高墙上，这些墙没有排列的裂缝……正如你所看到的，这个解决方案需要很长时间。所以很明显，蛮力似乎并不能在时间限制内有效地解决这个问题。任何建议/见解将不胜感激。

什么是获得树的最小顶点覆盖的好算法？

输入：

节点的邻居。

输出：

最小顶点数。

假设我有一个元素数组，其中存在总排序。冒泡排序距离是在我使用冒泡排序时对数组进行排序所需的交换次数。什么是一种有效的（可能涉及动态编程）方法来计算该数组的可能排列的数量，其冒泡排序距离小于或等于某个预先指定的数字？

如果它简化了问题，您可以假设数组的所有元素都是唯一的（没有关系）。