LeetCode 718 最长重复子数组
718.最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
动态规划
本质上就是在两个序列中，寻找两个最长的公共子序列（此处的公共子序列是连续的）。使用动态规划求解，重点依旧是动态规划数组的定义。
动态规划数组的定义：定义数组 dp[nums1.size()][nums2.size()] 其中 dp[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的最长公共子序列的长度。
动态规划数组的推导：对于 dp[i][j] ，若是 nums1[i]==nums2[j] 那么 dp[i][j]=dp[i-1][j-1]+1 ，否则 dp[i][j]=0
动态规划数组的初始化：此处的初始化主要是针对于第一行和第一列进行， i=0 时 dp[i][j]=1 if nums1[0]==nums2[j] else =0 ， j=0 时 dp[i][j]=1 if nums1[i]==nums2[0] else =0
动态规划数组的遍历顺序：从前向后，逐行进行遍历。
举例验证：
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size(),m=nums2.size();
vector<vector<int>> dp(n,vector<int>(m,0));
int res=0;
for(int j=0;j<m;j++)
if(nums1[0]==nums2[j]){
dp[0][j]=1;
res=max(res,dp[0][j]);
}
for(int i=0;i<n;i++)
if(nums1[i]==nums2[0]){
dp[i][0]=1;
res=max(res,dp[i][0]);
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(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-1][j-1] ，可以基于滚动数组实现。
动态规划数组的定义：定义动态规划数组 dp[nums2.size()] ，在初始时 dp[j] 表示以 nums1[0] 和 nums2[j] 结尾公共子序列的长度。在 i 次迭代时， dp[j] 表示以 nums1[i] 和 nums2[j] 结尾公共子序列的长度。
动态规划数组的推导：在第 i 次迭代时，判断 nums1[i]==nums2[j] 成立则 dp[j]=dp[j-1]+1 否则 dp[j]=0
动态规划数组的初始化：只需要初始化一行， i=0 时，nums1[0]==nums2[j] 成立则 dp[j]=1 否则 dp[j]=0
动态规划数组的遍历顺序：逐行遍历，在行内从后向前遍历。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size(),m=nums2.size();
vector<int> dp(m,0);
int res=0;
for(int j=0;j<m;j++)
if(nums1[0]==nums2[j]){
dp[j]=1;
res=max(res,dp[j]);
}
for(int i=1;i<n;i++){
for(int j=m-1;j>0;j--){
if(nums1[i]==nums2[j]){
dp[j]=dp[j-1]+1;
res=max(res,dp[j]);
}else{
dp[j]=0;
}
}
dp[0]=nums1[i]==nums2[0]?1:0;
res=max(res,dp[0]);
}
return res;
}
};
|
修改动态规划数组的定义：将 dp[i][j] 表示为，以 nums1[i-1] 和 nums2[j-1] 结尾的最长子序列长度，数组的长度为 dp[nums1.size()+1][nums2.size()+1] 那么从 i=1,j=1 开始遍历，无序对数组进行初始化。（相同的，在滚动数组中也可以使用这样的定义）
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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 result = 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] > result) result = dp[i][j];
}
}
return result;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<int> dp(vector<int>(B.size() + 1, 0));
int result = 0;
for (int i = 1; i <= A.size(); i++) {
for (int j = B.size(); j > 0; j--) {
if (A[i - 1] == B[j - 1]) {
dp[j] = dp[j - 1] + 1;
} else dp[j] = 0;
if (dp[j] > result) result = dp[j];
}
}
return result;
}
};
|