今日主要总结一下动态规划的一道题目,718. 最长重复子数组

题目:718. 最长重复子数组

Leetcode题目地址
题目描述:
给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1:

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

示例 2:

输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出:5

提示:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

本题重难点

注意题目中说的子数组,其实就是连续子序列。

要求两个数组中最长重复子数组,如果是暴力的解法 只要需要先两层for循环确定两个数组起始位置,然后在来一个循环可以是for或者while,来从两个起始位置开始比较,取得重复子数组的长度。

本题其实是动规解决的经典题目,我们只要想到 用二维数组可以记录两个字符串的所有比较情况,这样就比较好推 递推公式了。
动规五部曲分析如下:

  1. 确定dp数组(dp table)以及下标的含义
    dp[i][j] :以下标i – 1为结尾的nums1,和以下标j – 1为结尾的nums2,最长重复子数组长度为dp[i][j]。 (特别注意: “以下标i – 1为结尾的nums1” 标明一定是 以nums1[i-1]为结尾的字符串 )
    此时细心的同学应该发现,那dp[0][0]是什么含义呢?总不能是以下标-1为结尾的nums1数组吧。
    其实dp[i][j]的定义也就决定着,我们在遍历dp[i][j]的时候i 和 j都要从1开始。
    那有同学问了,我就定义dp[i][j]为 以下标i为结尾的nums1,和以下标j 为结尾的nums2,最长重复子数组长度。不行么?
    行倒是行! 但实现起来就麻烦一点,需要单独处理初始化部分,在本题解下面的拓展内容里,我给出了 第二种 dp数组的定义方式所对应的代码和讲解,大家比较一下就了解了。

  2. 确定递推公式
    根据dp[i][j]的定义,dp[i][j]的状态只能由dp[i – 1][j – 1]推导出来。
    即当nums1[i – 1] 和nums2[j – 1]相等的时候,dp[i][j] = dp[i – 1][j – 1] + 1;
    根据递推公式可以看出,遍历i 和 j 要从1开始!

  3. dp数组如何初始化
    根据dp[i][j]的定义,dp[i][0] 和dp[0][j]其实都是没有意义的!
    但dp[i][0] 和dp[0][j]要初始值,因为 为了方便递归公式dp[i][j] = dp[i – 1][j – 1] + 1;
    所以dp[i][0] 和dp[0][j]初始化为0。
    举个例子nums1[0]如果和nums2[0]相同的话,dp[1][1] = dp[0][0] + 1,只有dp[0][0]初始为0,正好符合递推公式逐步累加起来。

  4. 确定遍历顺序
    外层for循环遍历nums1,内层for循环遍历nums2。
    那又有同学问了,外层for循环遍历nums2,内层for循环遍历nums1。不行么?
    也行,一样的,我这里就用外层for循环遍历nums1,内层for循环遍历nums2了。
    同时题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i][j]的最大值记录下来。
    代码如下:

for (int i = 1; i <= nums1.size(); i++) {    for (int j = 1; j <= nums2.size(); j++) {        if (nums1[i - 1] == nums2[j - 1]) {            dp[i][j] = dp[i - 1][j - 1] + 1;        }        if (dp[i][j] > res) res = dp[i][j];    }}
  1. 举例推导dp数组

拿示例1中,A: [1,2,3,2,1],B: [3,2,1,4,7]为例,画一个dp数组的状态变化,如下:

方法一、 动态规划未优化代码

C++代码

class Solution {public:    int findLength(vector<int>& nums1, vector<int>& nums2) {        vector<vector<int>>dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));        int res = 0;        for(int i = 1; i <= nums1.size(); i++){            for(int j = 1; j <= nums2.size(); j++){                if(nums1[i - 1] == nums2[j - 1]){                    dp[i][j] = dp[i - 1][j - 1] + 1;                }                if(dp[i][j] > res){                    res = dp[i][j];                }            }        }        return res;    }};

时间复杂度: O ( n × m ) O(n × m) O(n×m),n 为nums1长度,m为nums2长度
空间复杂度: O ( n × m ) O(n × m) O(n×m)

方法二、 动态规划优化代码

我们可以看出dp[i][j]都是由dp[i – 1][j – 1]推出。那么压缩为一维数组,也就是dp[j]都是由dp[j – 1]推出。

也就是相当于可以把上一层dp[i – 1][j]拷贝到下一层dp[i][j]来继续用。

此时遍历nums2数组的时候,就要从后向前遍历,这样避免重复覆盖。

C++代码

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

时间复杂度: O ( n × m ) O(n × m) O(n×m),n 为nums1长度,m为nums2长度
空间复杂度: O ( m ) O(m) O(m)

拓展

前面讲了 dp数组为什么定义:以下标i – 1为结尾的nums1,和以下标j – 1为结尾的nums2,最长重复子数组长度为dp[i][j]。

我就定义dp[i][j]为 以下标i为结尾的nums1,和以下标j 为结尾的nums2,最长重复子数组长度。不行么?

当然可以,就是实现起来麻烦一些。

如果定义 dp[i][j]为 以下标i为结尾的nums1,和以下标j 为结尾的nums2,那么 第一行和第一列毕竟要经行初始化,如果nums1[i] 与 nums2[0] 相同的话,对应的 dp[i][0]就要初始为1, 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话,同理。

所以代码如下:

class Solution {public:    int findLength(vector<int>& nums1, vector<int>& nums2) {        vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));        int res = 0;        // 要对第一行,第一列经行初始化        for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;        for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;        for (int i = 0; i < nums1.size(); i++) {            for (int j = 0; j < nums2.size(); j++) {                if (nums1[i] == nums2[j] && i > 0 && j > 0) { // 防止 i-1 出现负数                    dp[i][j] = dp[i - 1][j - 1] + 1;                }                if (dp[i][j] > res) res = dp[i][j];            }        }        return res;    }};

大家会发现 这种写法 一定要多写一段初始化的过程。

而且为了让 if (dp[i][j] > result) result = dp[i][j]; 收集到全部结果,两层for训练一定从0开始遍历,这样需要加上 && i > 0 && j > 0的判断。

相对于版本一来说还是多写了不少代码。而且逻辑上也复杂了一些。 优势就是dp数组的定义,更直观一点。


总结

动态规划
英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的

对于动态规划问题,可以拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

注意题目中说的子数组,其实就是连续子序列。

要求两个数组中最长重复子数组,如果是暴力的解法 只要需要先两层for循环确定两个数组起始位置,然后在来一个循环可以是for或者while,来从两个起始位置开始比较,取得重复子数组的长度。

本题其实是动规解决的经典题目,我们只要想到 用二维数组可以记录两个字符串的所有比较情况,这样就比较好推 递推公式了,除此之外还给出动态规划状态压缩为一维数组的代码和拓展分析
欢迎大家关注本人公众号:编程复盘与思考随笔
(关注后可以免费获得本人在csdn发布的资源源码)