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)\)