会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题求的是两个数组里连续相同的那一段的最大长度，不是最长公共子序列。
- 设 dp[i][j] 表示「以 nums1 的第 i 个元素、nums2 的第 j 个元素结尾」的公共子数组最长能有多长。这里下标按 1 开始写转移，实现时用 i−1、j−1 去取原数组。
- 若 nums1i−1=nums2j−1，当前这一对可以对上，长度就是左上角那一格再加 1：dp[i][j]=dp[i−1][j−1]+1。
- 若对不上，公共子数组在这里断开，dp[i][j]=0。这一步是和「最长公共子序列」的本质差别：子序列允许跳过，子数组不允许。
- 答案取所有 dp[i][j] 的最大值。没有任何公共元素时答案为 0。
- n,m≤1000，二维 DP 是 O(nm)，大约 106 次运算，可以直接过。常见假解是当成 LCS 子序列来做，例如 1,2,3,4 与 1,3,2,4 子序列长度是 3，但公共子数组最长只有 1。
