学习交流加

  • 个人qq:
    1126137994
  • 个人微信:
    liu1126137994
  • 学习交流资源分享qq群:
    962535112

给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A="1A2C3D4B56”,B="B1D23CA45B6A”,”123456"或者"12C4B6"都是最长公共子序列。

给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例:
“1A2C3D4B56”,10,“B1D23CA45B6A”,12
返回:6

这是一个最长公共子序列问题,不是最长上升子序列问题,注意区分!!!!!!!

我们同样是使用动态规划的思想,假设字符串A的长度为n,字符串B的长度为m,则我们生成一个dp矩阵,大小为n*m。
那么dp[i][j]含义,就为A[0i]与B[0j]的最长公共子序列!!!

那么dp[i][j]的求法是什么?
1、矩阵dp的第一行dp[0][i]:
代表A[0]与B[0i]的最长公共子序列长度,A[0]只有一个字符,所以dp[0][i]最大值为1,如果A[0]==B[i],则另dp[0][i]=1;一旦dp[0][i]=1,则将dp[0][(i+1)(m-1)]全部设为1;
2、矩阵的第一列dp[j][0]
求法与求第一行的值相同,如果B[0]==A[j],则另dp[j][0]=1;一旦dp[j][0]=1,则将dp[(j+1)~(n-1)][0]全部设为1;
3、矩阵其他行的值的求法
dp[i][j]的情况,只可能来自以下两种情况:

情况一:A[i] 与 B[j]不相等
dp[i][j]可能是等于dp[i-1][j]的值

同理,也有可能是等于dp[i][j-1]

然后选择上述两者的最大值即可!!!

情况二:A[i] 与 B[j]相等
此时,dp[i][j]=dp[i-1][j-1]+1

代码实现如下:

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
       // if(n==0||m==0)
          // return 0;
        int dp[n][m];
        //先求第一行
        int flag1,flag2;
        for(int h=0;h<=m-1;h++)
        {
            if(A[0]!=B[h])
                dp[0][h]=0;
            else
            {
                flag1=h;
                 for(int k=flag1;k<=m-1;k++)
                {
                    dp[0][k]=1;
                }
                break;
            }  
        }
        //再求第一列
        for(int q=0;q<=n-1;q++)
        {
            if(B[0]!=A[q])
                dp[q][0]=0;
            else
            {
                flag2 =q;
                for(int p=flag2;p<=n-1;p++)
                {
                    dp[p][0]=1;
                }
                break;
            } 
        }
        //再求其他行的值
        for(int i=1;i<=n-1;i++)
        {
            for(int j=1;j<=m-1;j++)
            {
                if(A[i]==B[j])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[n-1][m-1];
        
    }
};

求最优解问题,往往能够使用动态规划的方法来做,动态规划,就是先求解子问题,然后整合求解整体问题!算法的思想,还是很奇妙的!!!