动态规划算法N，K问题

Question

动态规划算法N，K问题

7

一个算法，它将取两个正整数N和K，并计算通过从N中删除K个数字来将N转换为另一个数字的最大可能数字。

例如，假设我们有N=12345和K=3，那么通过从N中删除3个数字可以得到的最大可能数字是45（其他变换可能是12、15、35，但45是最大的）。此外，您不能更改N中数字的顺序（因此54不是解决方案）。另一个例子是N=66621542和K=3，所以解决方案将是66654。

我知道这是一个与动态规划相关的问题，我无法想出任何解决方法。我需要在2天内解决这个问题，所以任何帮助都将不胜感激。如果您不想为我解决这个问题，您也不必这样做，但请指点我一下诀窍，或者至少提供一些我可以阅读更多类似问题的材料。

提前感谢您的帮助。

- jajox

5个回答

5

好的，为了解决任何动态规划问题，您需要将其分解为重复的子问题。

假设我们将您的问题定义为A(n, k)，它通过从n中删除k个数字返回可能的最大数字。

我们可以从中定义一个简单的递归算法。

使用您的示例，A(12345, 3) = max { A(2345, 2), A(1345, 2), A(1245, 2), A(1234, 2) }

更一般地，A(n, k) = max { A(删除1个数字后的n, k - 1) }

并且您的基本情况是A(n, 0) = n。

使用这种方法，您可以创建一个缓存n和k值的表格。

int A(int n, int k)
{
  typedef std::pair<int, int> input;
  static std::map<input, int> cache;

  if (k == 0) return n;

  input i(n, k);
  if (cache.find(i) != cache.end())
    return cache[i];

  cache[i] = /* ... as above ... */

  return cache[i];
}

现在，这是一种简单直接的解决方案，但是有一种更好的解决方案可以使用非常小的一维缓存。考虑重新表述问题，如下所示：“给定字符串n和整数k，在n中找到长度为k的按字典顺序最大的子序列”。这本质上就是你的问题，而且解决方案要简单得多。

我们现在可以定义一个不同的函数B（i，j），它仅使用n的前i个数字（换句话说，从n的前i个数字中删除j个数字），并给出长度为（i-j）的最大词典序列。

再次使用您的示例，我们将有：

B（1，0）= 1

B（2，0）= 12

B（3，0）= 123

B（3，1）= 23

B（3，2）= 3

等等。

经过一点思考，我们可以找到递归关系：

B（i，j）= max（10B（i-1，j）+ n _i，B（i-1，j-1））

或者，如果j = i，则B（i，j）= B（i-1，j-1）

并且B（0，0）= 0

然后，您可以以与上面非常相似的方式编写代码。

- Peter Alexander

4

解决动态规划问题的关键通常是找出解决方案的结构，更具体地说，是否表现出最优子结构。

在这种情况下，我认为对于N=12345和K=3的最优解，N=12345和K=2的最优解应该是解的一部分。如果你能让自己相信这个结论，那么你就应该能够递归地表达问题的解决方案。然后使用记忆化或自底向上实现此解决方案。

- Hans W

或者N=2345，K=2。 - Vatine

1

任何动态规划解决方案中最重要的两个元素是：

定义正确的子问题
定义一个递归关系，将子问题的答案与较小子问题的答案联系起来
找到基本情况，即答案不依赖于其他答案的最小子问题
确定必须解决子问题的扫描顺序（以便永远不会使用基于未初始化数据的递归关系）

当您定义正确的子问题时，您将会发现：

您需要回答的问题就是其中之一
基本情况确实很简单
递归容易评估
扫描顺序很直接

在您的情况下，指定子问题很简单。由于这可能是作业，我只会给您一个提示：您可能希望 N 的位数更少。

- forefinger

0

这是我的想法：

考虑从左边开始的前k+1个数字。找到最大的数字并删除左边的数字。如果存在两个相同的最大数字，则找到最左边的一个并删除该数字左边的数字。存储已删除数字的数量（将其命名为j）。

使用新数字N和k + 1-j作为K重复上述步骤。一直重复此过程，直到k + 1-j等于1（希望如此，如果我没有弄错的话）。

最终得到的数字就是您要查找的数字。

- erelender

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

这可以在O（L）的时间复杂度内解决，其中L =数字位数。当我们可以使用栈来完成此操作时，为什么要使用复杂的DP公式：

对于：66621542 在堆栈上添加一个数字，同时堆栈上少于或等于L-K个数字： 66621。现在，在当前读取的数字小于堆栈中的数字时，从堆栈中删除数字并将当前数字放入堆栈中：

读取5：5>2，从栈中弹出1。5>2，也弹出2。放置5：6665 读取4：堆栈未满，请放置4：66654 读取2：2<4，不做任何操作。

您需要另一个条件：确保不要从堆栈中弹出比剩余数字更多的项，否则您的解决方案将不完整！

另一个例子：12345 L = 5，K = 3 在堆栈上放置L-K = 2个数字：12

读取3，3>2，弹出2，3>1，弹出1，放置3。堆栈：3 读取4，4>3，弹出3，放置4：4 读取5：5>4，但是我们不能弹出4，否则我们将没有足够的数字。所以推5：45。