动态规划C++

解题思路:由字母LCS变单词LCS
注意事项:找相同的单词数，单词的第一个字母是大写
参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N=1e3+10;

string a,b;

string sta[N],stb[N];//由字母变单词，找相同的单词数，单词的第一个字母是大写

int dp[N][N];

int main()

{

  cin>>a>>b;

  int lenA=a.length();

  int lenB=b.length();

  int cna=0;//分割第一个字符串

  for(int i=0;i<lenA;i++)

  {

    if(a[i]>='A'&&a[i]<='Z')

    {

      cna++;

    }

    sta[cna]+=a[i];

  }

  int cnb=0;//分割第二个字符串

  for(int i=0;i<lenB;i++)

  {

    if(b[i]>='A'&&b[i]<='Z')

    {

      cnb++;

    }

    stb[cnb]+=b[i];

  }

  for(int i=1;i<=cna;i++)

  {

    for(int j=1;j<=cnb;j++)

    {

      if(sta[i]==stb[j])

      {

        dp[i][j]=dp[i-1][j-1]+1;

      }

      else 

      {

        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

      }

    }

  }

  cout<<dp[cna][cnb];

  return 0;

}