【leetcode】718. 最长重复子数组（maximum-length-of-repeated-subarray）（DP）[中等]

链接

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

耗时

解题：14 min
题解：22 min

题意

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

思路

最长公共子序列。
二维DP，dp[i][j]，[i] 指数组 A 对应的元素A[i]，[j] 指数组 B 对应的元素B[j]，dp[i][j] 是 A[0~i] 和 B[0~j] 中包含 A[i]、B[j] 的最长公共子序列长度，那么最终的最长公共子序列即是 dp[i][j] 中的最大值。
状态转移方程：
d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] + 1    ( A [ i ] = = B [ j ] ) 0    ( 其 它 ) dp[i][j] = \begin{cases} dp[i-1][j-1]+1 \ \ (A[i] == B[j]) \\ 0 \ \ (其它) \end{cases} dp[i][j]={dp[i−1][j−1]+1  (A[i]==B[j])0  (其它)​
因为 dp[i][j] 的值从 dp[i-1][j-1] 转移得到，所以 dp[i][0] 和 dp[0][j] 需要空出来。

AC代码

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int dp[1100][1100];
        memset(dp, 0, sizeof(dp));
        int max_len = 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;
                    if(dp[i][j] > max_len) max_len = dp[i][j];
                }
            }
        }
        return max_len;
    }
};