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[i][j]表示以nums1[i-1]结尾和以nums2[j-1]结尾的最长公共子数组的长度
如果nums1[i-1]等于nums2[j-1]，才存在以nums1[i-1]结尾和以nums2[j-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[i][j]=dp[i-1][j-1] +1。
如果nums1[i-1]不等于nums2[j-1]，此时不存在以nums1[i-1]结尾和以nums2[j-1]结尾的公共子数组，dp[i][j]等于0。
第三步，理解dp数组如何初始化
//dp[0][j]表示nums1为空,显然此时nums1和nums2没有公共子数组,dp[0][j]都应该初始化为0
//dp[i][0]表示nums2为空,显然此时nums1和nums2没有公共子数组,dp[i][0]都应该初始化为0
//当i!=0 && j!=0时,分两种情况：
//如果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。
//如果nums1[i-1]!=nums2[j-1],dp[i][j]应该为0,初始化时候统一赋0也没问题。
第四步，理解遍历顺序
由递推公式，可知i和j都应该从小到大遍历。注意i的取值范围是[1,len1]，j的取值范围是[1,len2]。
代码
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size();int len2 = nums2.size();//i的取值范围是[1,len1]//j的取值范围是[1,len2]//dp[i][j]表示以nums1[i-1]结尾和以nums2[j-1]结尾的最长公共子数组的长度//dp[0][j]表示nums1为空,显然此时nums1和nums2没有公共子数组,dp[0][j]都应该初始化为0//dp[i][0]表示nums2为空,显然此时nums1和nums2没有公共子数组,dp[i][0]都应该初始化为0//当i!=0 && j!=0时,分两种情况：//如果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。//如果nums1[i-1]!=nums2[j-1],dp[i][j]应该为0,初始化时候统一赋0也没问题。vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));int res = 0;for(int i = 1;i <=len1;i++){for(int j = 1; j <=len2;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;}
};