leetcode 718. Maximum Length of Repeated Subarray

目次
题目描述
第一步，明确并明白dp数组及下标的寄义
第二步，分析明确并明白递推公式
第三步，明白dp数组怎样初始化
第四步，明白遍历次序
代码

---

题目描述

这是子序列题目。子数组是一连的子序列。
第一步，明确并明白dp数组及下标的寄义

用下标(i-1)遍历nums1数组，用下标(j-1)遍历nums2数组。
        int len1 = nums1.size();
        int len2 = nums2.size();
        //i的取值范围是[1,len1]
        //j的取值范围是[1,len2]
        //dp[j]表现以nums1[i-1]末端和以nums2[j-1]末端的最长公共子数组的长度
假如nums1[i-1]等于nums2[j-1]，才存在以nums1[i-1]末端和以nums2[j-1]末端的公共子数组。例如

1. nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

复制代码

nums1[0]和nums2[0]不相等，此时不存在以nums1[0]末端和以nums2[0]末端公共子数组，dp[1][1]应该为0。
nums1[1]和nums2[1]都是2，此时以nums1[2]末端和以nums2[1]末端的最长公共子数组就是2这单个数构成的子数组，dp[2][2]应该为1。
第二步，分析明确并明白递推公式

对于i不等于0且j不等于0的情况：
假如nums1[i-1]等于nums2[j-1]，假如它们的值是x。说明x这单个数构成的子数组肯定是以nums1[i-1]末端和以nums2[j-1]末端的公共子数组，但不肯定是最长的。容易明白dp[j]=dp[i-1][j-1] +1。
假如nums1[i-1]不等于nums2[j-1]，此时不存在以nums1[i-1]末端和以nums2[j-1]末端的公共子数组，dp[j]等于0。
第三步，明白dp数组怎样初始化

        //dp[0][j]表现nums1为空,显然此时nums1和nums2没有公共子数组,dp[0][j]都应该初始化为0
        //dp[0]表现nums2为空,显然此时nums1和nums2没有公共子数组,dp[0]都应该初始化为0
        //当i!=0 && j!=0时,分两种情况：
        //假如nums1[i-1]==nums2[j-1],dp[j]=dp[i-1][j-1]+1,即后面的dp[j]由前面的dp[i-1][j-1]覆盖计算,因此dp[j]可以不初始化，大概为了写代码方便可以统一初始化为0。
        //假如nums1[i-1]!=nums2[j-1],dp[j]应该为0,初始化时候统一赋0也没题目。
第四步，明白遍历次序

由递推公式，可知i和j都应该从小到大遍历。留意i的取值范围是[1,len1]，j的取值范围是[1,len2]。
代码

1. class Solution {
2. public:
3.     int findLength(vector<int>& nums1, vector<int>& nums2) {
4.         int len1 = nums1.size();
5.         int len2 = nums2.size();
6.         //i的取值范围是[1,len1]
7.         //j的取值范围是[1,len2]
8.         //dp[i][j]表示以nums1[i-1]结尾和以nums2[j-1]结尾的最长公共子数组的长度
9.         //dp[0][j]表示nums1为空,显然此时nums1和nums2没有公共子数组,dp[0][j]都应该初始化为0
10.         //dp[i][0]表示nums2为空,显然此时nums1和nums2没有公共子数组,dp[i][0]都应该初始化为0
11.         //当i!=0 && j!=0时,分两种情况：
12.         //如果nums1[i-1]==nums2[j-1],dp[i][j]=dp[i-1][j-1]+1,即后面的dp[i][j]由前面的dp[i-1][j-1]覆盖计算,因此dp[i][j]可以不初始化，或者为了写代码方便可以统一初始化为0。
13.         //如果nums1[i-1]!=nums2[j-1],dp[i][j]应该为0,初始化时候统一赋0也没问题。
14.         vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
15.         int res = 0;
16.         for(int i = 1;i <=len1;i++){
17.             for(int j = 1; j <=len2;j++){
18.                 if(nums1[i-1] == nums2[j-1])
19.                     dp[i][j] = dp[i-1][j-1] + 1;
20.                 if(dp[i][j] > res)
21.                     res = dp[i][j];
22.             }
23.         }
24.         return res;
25.     }
26. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。