跳转至

718 最长重复子数组

动态规划

二维做法

有两种dp[i][j] 的方法

方法一:

dp[i][j] 的含义

dp[i][j] 表示数组a第i个元素和数组第j个元素的公共子数组长度

递推公式:

如果A[i] == B[j],dp[i][j] = dp[i - 1][j - 1] + 1

否则dp[i][j] = 0

遍历顺序:

从上到下,从左到右

初始化:

需要分类讨论

如果A[0] == B[0],dp[0][0] = 1

如果A[0] != B[0],dp[0][0] = 0

如果A[i] == B[0],dp[i][0] = 1

如果B[j] == A[0],dp[0][j] = 1

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector<vector<int>> dp(n, vector<int>(m, 0));

        // 初始化
        for(int i = 0; i < n; i++){
            if(nums1[i] == nums2[0])
                dp[i][0] = 1;
        }
        for(int j = 0; j < m; j++){
            if(nums1[0] == nums2[j])
                dp[0][j] = 1;
        }

        // 设定res求dp[i][j]的最大值
        int res = 0;
        // 本质上dp[i][j] = dp[i - 1][j - 1] + 1适用于i >= 1 && j >= 1
        // 因为dp[i][0]和dp[0][j]已经被更新
        // 但是res需要求dp[i][j]的最大值,包括dp[i][0]和dp[0][j]的最大值
        // 所以这里从i == 0 和j == 0开始
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // 这里需要i > 0 && j > 0 
                if(i > 0 && j > 0 && nums1[i] == nums2[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                res = max(res, dp[i][j]);
            }          
        }

        return res;
    }
};

方法二:

dp[i][j] 的含义

dp[i][j] 表示数组a第i - 1个元素和数组第j - 1个元素的公共子数组长度

递推公式:

如果A[i] == B[j],dp[i][j] = dp[i - 1][j - 1] + 1

否则dp[i][j] = 0

遍历顺序:

从上到下,从左到右

初始化:

dp[i][j] 表示数组a第i - 1个元素和数组第j - 1个元素的公共子数组长度

所以i和j从1开始

所以i == 0|| j ==0没有含义,dp[i][0]和dp[0][j]都为0

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        // 因为dp[i][j]表示数组a第i - 1个元素和数组第j - 1个元素的公共子数组长度
        // 数组a有n个元素,数组b有m个元素
        // 所以i最大值为n而不是n - 1,j最大值为m而不是m - 1
        // 这里初始化要注意dp(n + 1, vector<int>(m + 1, 0))
        // 而不是dp(n, vector<int>(m, 0));
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        int res = 0;
        // 从i == 1和j == 1开始遍历, i <= n, j <= m
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                res = max(res, dp[i][j]);
            }          
        }

        return res;
    }
};

总结

可以发现,方法二初始化比方法一要简单很多

  • 时间复杂度:O(n × m),n 为A长度,m为B长度
  • 空间复杂度:O(n × m)

一维优化

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector<int> dp(m + 1, 0);

        int res = 0;
        for(int i = 1; i <= n; i++){
            // 因为dp[i][j] = dp[i - 1][j - 1] + 1
            // 如果直接变成dp[j] = dp[j - 1] + 1,这里的dp[j - 1]是dp[i][j]
            // 因此需要改变j的遍历顺序
            for(int j = m; j >= 1; j--){
                if(nums1[i - 1] == nums2[j - 1])
                    dp[j] = dp[j - 1] + 1;
                // 不相等的时候需要将dp[j]置为0,表示公共长度为0
                // 二维做法中其实也需要置为0,但是初始化的时候已经置为了0
                // 在一维做法中,由于滚动数组每个位置都会在每个i循环中使用,因此需要更新dp[j] = 0
                else
                    dp[j] = 0;
                res = max(res, dp[j]);
            }          
        }

        return res;
    }
};
  • 时间复杂度:\(O(n × m)\),n 为A长度,m为B长度
  • 空间复杂度:\(O(m)\)