c++ - 最长公共(public)递增子序列动态规划

Question

我正在努力寻找最长常见递增子序列问题的解决方案。如果您不熟悉这里的链接。 LCIS

这个问题基本上可以归结为两个不同的问题。 “最长公共(public)子序列”和“最长递增子序列”。这是最长公共(public)子序列的递归解决方案:

LCS(S,n,T,m)
{
if (n==0 || m==0) return 0;
if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1); // no harm in matching up
else result = max( LCS(S,n-1,T,m), LCS(S,n,T,m-1) );
return result;
}

基于此和发现的一般递归公式here我一直在尝试实现该算法，以便可以使用动态编程。

int lcis(int S[4], int n, int T[4], int m, int prev)
{
  int result;

  if (n == 0 || m  == 0)
    return 1;
  if (S[n] == T[m] && S[n] > S[prev]){
    result = myMax(1 + lcis(S, n-1, T, m-1, n), lcis(S, n-1, T, m, prev),
                    lcis(S, n, T, m-1, prev)) ;
  }
  else
    result = max(lcis(S,n-1,T,m, prev), lcis(S,n,T,m-1, prev));

  return result;
}

显然这没有给出正确的解决方案。任何帮助，将不胜感激。

例如，如果我给它两个序列 {1, 2, 4, 5} 和 {12, 1, 2, 4} 我得到的输出是 2。这里正确的输出是 3，对于子序列 {1,2,4}

编辑:

根据下面的建议，这里是一些修改后的代码。仍然不是 100% 正确。但更近了。请注意，我现在使用的是 vector ，但这不会改变任何东西。

int lcis(vector<int> S, int n, vector<int> T, int m, int size)
{
  int result;

  if (n < 0 || m < 0)
    return 0;
  if (S[n] == T[m] && (n == size - 1 || S[n] < S[n + 1] )){
    result = myMax(1 + lcis(S, n - 1, T, m - 1, size), lcis(S, n - 1, T, m, size),
                    lcis(S, n, T, m - 1, size));
  }
  else
    result = max(lcis(S, n-1, T, m, size), lcis(S, n, T, m-1, size));

  return result;
}

Answer 1

请记住，您正在向后遍历数组。所以这个测试

 S[n] > S[prev]

应该反过来:

 S[n] < S[prev]

我不确定你为什么需要 prev，因为它应该总是 n+1，所以可以使用

if (S[n] == T[m] && n < 3 && S[n] < S[n+1])

如果你需要让它适用于任何尺寸，那么要么传递尺寸，要么只是一个标志说不要检查 n+1

编辑:

我的错误 - 当 n == 3(或大小)时，您想要处理第一个 if 情况，因为您正处于(可能)增加的子序列的开始。

if 测试应该是

if (S[n] == T[m] && (n == 3 || S[n] < S[n+1]))

注意这个 if 测试:

if (n == 0 || m  == 0)
    return 1;

忽略任一序列的第一个元素(并假设它位于递增子序列的末尾)。需要做的是在任一序列开始之前停止递归。您还知道，当您在序列开始之前就已经走了，您不可能在子序列中，因此您可以为子序列的长度返回 0。所以测试应该是

if (n < 0 || m < 0)
    return 0;