动态编程算法N,K问题

Question

一种算法,它将取两个正数N和K,并通过从N中删除K个数字,将N转换为另一个数,计算出我们可以获得的最大可能数.

例如,假设我们有N = 12345和K = 3所以我们通过从N中删除3位数得到的最大可能数是45(其他转换将是12,15,35但45是最大的).此外,您无法更改N中的数字顺序(因此54不是解决方案).另一个例子是N = 66621542和K = 3,因此解决方案将是66654.

我知道这是一个动态编程相关的问题,我无法理解解决它.我需要解决这个问题2天,所以任何帮助都表示赞赏.如果你不想为我解决这个问题,你没有必要,但请指出我的技巧或至少一些材料,我可以阅读更多有关类似问题的信息.

先感谢您.

Answer 1

这可以在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.

Answer 2

那么,要解决任何动态编程问题,您需要将其分解为重复的子解决方案.

假设我们将您的问题定义为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(n除去1位,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,找到长度为k的n中按字典顺序排列的最大子序列".这基本上就是你的问题,而且解决方案要简单得多.

我们现在可以定义一个不同的函数B(i,j),它使用n的前i个数字(换句话说,从前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

你可以用与上面非常类似的方式对其进行编码.

Answer 3

解决动态规划问题的技巧通常是弄清楚解决方案的结构是什么样的，更具体地说，它是否表现出最佳子结构。

在这种情况下，在我看来，N=12345 和 K=3 的最优解将具有 N=12345 和 K=2 的最优解作为解的一部分。如果您能够说服自己这成立，那么您应该能够递归地表达问题的解决方案。然后通过记忆或自下而上的方式实现这一点。