C++ 解法, 执行用时: 1ms, 内存消耗: 756KB, 提交时间: 2017-09-06

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        int dp[n+1][m+1];
        for(int i=0;i<=n;i++) dp[i][0]=0;
        for(int i=0;i<=m;i++) dp[0][i]=0;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(A[i]==B[j])
                    dp[i+1][j+1]=dp[i][j]+1;
                else
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
        return dp[n][m];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 552KB, 提交时间: 2022-01-05

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        if(!n||!m)
            return 0;
        short**dp=new short*[n+1];
        for(short i=n;i>=0;--i)
            dp[i]=new short[m+1];
        for(short i=0;i<=n;++i)
            dp[i][0]=0;
        for(short i=0;i<=m;++i)
            dp[0][i]=0;
        for(short i=1;i<=n;++i)
            for(short j=1;j<=m;++j){
                if(A[i-1]==B[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        int result=dp[n][m];
        for(int i=0;i<=n;++i)
            delete[]dp[i];
        delete[]dp;
        return result;
    }
};