题解 | #最长公共子数组#

时间复杂度O(mn) 空间复杂度O(mn)。可以考虑使用滚动数组思想，将空间复杂度优化到O(n)

「C++ 代码」

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param B int整型vector 
     * @return int整型
     */
    int longestCommonSubarry(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        int res = 0;
        // dp[i][j]表示以第i个元素为底的A数组和以第j个元素为底的B数组的最长公共子数组长度
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        // 初始化状态
        for(int i=0; i<=m; ++i) dp[i][0] = 0;
        for(int j=0; j<=n; ++j) dp[0][j] = 0;
        // 状态转移
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
};