给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

提示：

• 1 <= len(A), len(B) <= 1000
• 0 <= A[i], B[i] < 100

Solution

参考 代码随想录

• 动态规划
• dp[i] [j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i] [j]。
• 即当A[i - 1] 和B[j - 1]相等的时候，dp[i] [j] = dp[i - 1] [j - 1] + 1;

// @lc code=start
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        // dp[i][j] ：以下标i-1为结尾的A，和以下标j-1为结尾的B，最长重复子数组长度为dp[i][j]
        vector<vector<int>> dp(A.size()+1, vector<int>(B.size()+1, 0));
        int res = 0;
        for (int i = 1; i <= A.size(); ++i) {
            for (int j = 1; j <= B.size(); ++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;
    }
};
// @lc code=end

• 状态压缩
• 此时遍历B数组的时候，就要从后向前遍历，这样避免重复覆盖。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        vector<int> dp(vector<int>(B.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= A.size(); i++) {
            for (int j = B.size(); j > 0; j--) {
                if (A[i - 1] == B[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作 
                if (dp[j] > result) result = dp[j];
            }
        }
        return result;
    }
};