最长公共子串的 DP 记忆方法

Question

谁能提供两个字符串之间最长公共子串的记忆方法。我知道最底层的解决方案，但我无法以自上而下的方式思考。预期时间复杂度-O(n^2)

Answer 1

自上而下的方法

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

string X, Y;             //input strings
int ans, dp[105][105];   // ans : answer

int LCS(int n, int m)    //our function return value of (n,m) state
{                        // so that we can use the result in (n+1,m+1) state
  if(n == 0 || m == 0) return 0;   //in case of match in (n+1,m+1) state
  if(dp[n][m] != -1) return dp[n][m];

  LCS(n-1,m);          //to visit all n*m states          (try example:  X:ASDF
  LCS(n,m-1);          // we call these states first                     Y:ASDFF)

  if(X[n-1] == Y[m-1])
  {

    dp[n][m] =  LCS(n-1,m-1) + 1;
    ans = max(ans, dp[n][m]);
    return dp[n][m];
  }
    return dp[n][m] = 0;
}

int main()
{
    int t; cin>>t;
    while(t--)
    {
      int n, m; cin>>n>>m;  //length of strings
      cin>>X>>Y;
      memset(dp, -1, sizeof dp);
      ans = 0;
      LCS(n, m);
      cout<<ans<<'\n';
    }
    return 0;
}