最长公共递增子序列动态规划

Question

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

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

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;
}

基于此和这里找到的一般递归公式，我一直在尝试实现该算法，以便可以使用动态规划。

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的输出。对于子序列{1,2,4}，这里的正确输出是3

编辑：

下面是一些经过修改的代码，根据下面的建议。仍然不是100%正确。但更接近。注意，我现在使用向量，但这不会改变任何事情。

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;