1.题目解析
题目来源
718.最长重复子数组——力扣
测试用例
2.算法原理
1.状态表示
子数组问题不能像子序列问题使用两个区间来表示状态,因为子数组一定是连续的,因此在填第i个位置就需要用到第i-1个位置的值,那么不妨以某个位置为结尾来设置dp表,即
dp[i][j]:以s1的第i个位置为结尾与以s2的第j个位置为结尾的字符串中最长公共子数组的长度
2.状态转移方程
这里需要借助最后位置字符是否相等来判断,相等则找到前一个位置的dp值后对最长公共组数组的长度+1,也就是dp[i-1][j-1]+1,反之不相等则一定不能构成最长公共子数组,直接将该位置dp表的值赋值为0即可
3.初始化
开辟虚拟位置,但是虚拟位置节点为0,于是无需初始化
4.填表顺序
从上到下,每一行从左到右
5.返回值
返回dp表中的最大值就是最长公共子序列的长度
3.实战代码
代码解析
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2)
{
int m = nums1.size();
int n = nums2.size();
int ret = 0;
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i = 1;i <= m;i++)
{
for(int j = 1;j <= n;j++)
{
if(nums1[i-1] == nums2[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
ret = max(dp[i][j],ret);
}
}
return ret;
}
};