题目:
给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。
dp数组含义:
dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。 (特别注意: “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 )
解决初始化nums【-1】【-1】的问题:
模拟遍历:
i的范围是0~nums1.size()
j的范围是0~nums2.size()
依次选定i,然后依次选定j,然后算出dp【i】【j】,if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;即dp【i】【j】通过dp【i-1】dp【j-1】得到。
此时想象遍历过程。当 i 为0,j 依次为0~nums2.size()。dp【0】【0】决定了dp【0】【后面的值】,dp【0】【0】怎么初始化呢?很明显看nums1【0】与nums2【0】是否相等,这个就是递归公式。相等则nums【-1】【-1】+1。只需要将nums【-1】【-1】初始化为0即可。那么我们可以将数组扩大一个元素,所有元素都向后移动一个单位,此时dp【0】【0】设为0,然后就可以从第0个元素开始遍历了。此时dp数组下标为1的元素代表的是nums1,nums2小标为0的元素。即dp【i】【j】代表的是以nums1下标 i-1结尾,以nums2下标 j-1结尾的最长重复子数组的长度。
代码:
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(result < dp[i][j]) result = dp[i][j];
}
}
return result;
}
};