问题标签 [dynamic-programming]

经典的 RLE 算法通过使用数字来表示数字后面的字符在该位置出现在文本中的次数来压缩数据。例如：

AAABBAAABBCECE => 3A2B3A2B1C1E1C1E

但是，在上面的示例中，该方法会导致压缩文本使用更多空间。一个更好的主意是使用数字来表示数字后面的子字符串在给定文本中出现的次数。例如：

AAABBAAABBCECE => 2AAABB2CE（“AAABB”两次，然后“CE”两次）。

现在，我的问题是：如何实现一个有效的算法，使用这种方法找出最佳 RLE 中的最小字符数？存在蛮力方法，但我需要更快的方法（最多O(length ² )）。也许我们可以使用动态规划？

这是 TSP（旅行商问题）的动态编程伪代码。我了解它的最佳子结构，但我无法弄清楚红括号中的代码是做什么的。

我不是要求任何人编写实际代码，我只需要解释正在发生的事情，这样我就可以编写自己的......谢谢:)

这是伪代码的链接，我不能在这里上传。 http://www.imagechicken.com/viewpic.php?p=1266328410025325200&x=jpg

给定一组可能的值和一些“数字”，我想找到每个唯一的、无序的值分组。例如，假设您有一个 A、B、C 的字母表。所有 3 位数字的组合将是：

我要解决的具体问题要简单一些。我正在做一个二十一点游戏作为 F# 中的练习（我之前已经发布过这个）。我计算手牌值的方法是使用卡片可能值列表的列表。除了 A 之外的所有卡片在列表中都有一个项目，但 A 可以是 1 或 11。我在那篇文章中提出的实现产生了很多冗余。例如，3 个 ace 将创建一个类似的列表[3; 13; 13; 13; 23; 23; 23; 33]。现在我正在获取最终列表并运行它Distinct()，但感觉有点像黑客。

将这一切联系在一起，A 的潜在值 (1, 11) 构成了字母表，而手中 A 的数量决定了数字的数量。在这种情况下，我希望算法提出以下模式：

有些东西告诉我动态编程可能会在这里发挥作用，但我缺乏适当的术语让我有点卡住了。任何帮助，将不胜感激。

编辑

对于它的价值，我知道对于特定问题有更简单的解决方案，但是作为函数式编程的练习，通用性是我的目标之一。

我在很多地方都发现了这个著名的 dp 问题，但我不知道如何解决。

给定一组 n 种类型的矩形 3-D 框，其中第 i^th 框的高度为 h(i)，宽度为 w(i)，深度为 d(i)（均为实数）。您想创建一个尽可能高的盒子堆叠，但如果下层盒子的 2-D 底座的尺寸每个都严格大于 2-D 盒子的尺寸，您只能将一个盒子堆叠在另一个盒子的顶部。上盒的 D 底座。当然，你可以旋转一个盒子，让任何一面作为它的基础。也允许使用同一类型盒子的多个实例。

这个问题对我来说似乎太复杂了，无法弄清楚步骤。因为它是 3D，所以我得到了高度、宽度和深度的三个序列。但是由于可以交换 3 维，所以问题对我来说变得更加复杂。所以请有人解释在没有交换时解决问题的步骤，然后在交换时如何做。我厌倦了这个问题。所以，请有人解释解决方案的简单方法。

有一个由 M 个二进制数组成的数组，每个二进制数都处于状态“0”或“1”。您可以执行几个步骤来更改数字的状态，并且在每个步骤中，您都可以更改恰好 N 个连续数字的状态。当然，给定数字 M、N 和包含成员的数组，您将要计算将所有二进制数转换为一种状态（1 或 0）所需的最小步骤数。

如果 M = 6 且 N = 3 且数组为 1 0 0 1 0 0，则解将为 2。 说明：我们可以分两步翻转它们，使它们都为 1：我们从索引 2 翻转到 4，然后我们将数组转换为 111000，然后将最后三个 (N) 0 翻转为 1。

整数数组 A[i] (i > 1) 定义如下：元素 A[k] ( k > 1) 是大于 A[k-1] 的最小数，使得其数字之和等于数字 4* A[k-1] 的数字之和。

您需要编写一个程序，根据给定的第一个元素 A[1] 计算此数组中的第 N 个数。

输入：在一行标准输入中，有两个数字用一个空格分隔：A[1] (1 <= A[1] <= 100) 和 N (1 <= N <= 10000)。

输出：标准输出应该只包含一个整数 A[N] ，即定义序列的第 N 个数字。

输入：7 4

输出：79

解释：数组的元素如下：7、19、49、79……第4个元素是解。

我尝试通过编写一个单独的函数来解决这个问题，该函数对于给定的数字 A[k] 计算它的数字之和，并找到大于 A[k-1] 的最小数字，正如它在问题中所说的那样，但没有成功。第一次测试由于内存限制而失败，第二次测试由于时间限制而失败，现在我不知道如何解决这个问题。一位朋友建议递归，但我不知道如何设置。

任何可以以任何方式帮助我的人都请写信，同时提出一些关于使用递归/DP 来解决这个问题的想法。谢谢。

我有打包 2 个任意多边形的问题。即我们有2个任意多边形。我们要找到这个多边形的这种位置（我们可以进行旋转和移动），当包围这个多边形的矩形具有最小的面积时。

我知道，这是一个 NP 完全问题。我想选择一种有效的算法来解决这个问题。我正在寻找 No-Fit-Polygon 方法。但是我在任何地方都找不到用于查找两个任意多边形的 NFP 的简单而清晰的算法。

我有一组整数。我想使用动态编程找到该集合的最长递增子序列。

我正在回顾我的算法课程中的一些旧笔记，动态编程问题对我来说似乎有点棘手。我有一个问题，我们有无限供应的硬币，有一些面额 x1，x2，... xn，我们想找一些价值 X。我们正在尝试设计一个动态程序来决定 X 的找零是否可以制作与否（不是最小化硬币的数量，或者返回哪些硬币，只是对或错）。

我已经对这个问题做了一些思考，我可以看到一种递归方法，它类似于......

将其转换为动态程序对我来说并不容易。我该如何处理？

输入：一个二维数组 NxN - 矩阵 - 具有正负元素。

输出：任意大小的子矩阵，使得其总和是所有可能子矩阵中的最大值。

要求：算法复杂度为O(N^3)

历史：在算法专家 Larry 和 Kadane 算法的修改的帮助下，我设法部分解决了仅确定求和的问题 - 下面是 Java。
感谢Ernesto，他设法解决了剩下的问题，即确定矩阵的边界，即左上角、右下角 - 在 Ruby 下方。