网站被收录又被取消了,重庆网站制,法治建设的网站,网页版攻速传奇题意理解#xff1a; 给两个整数数组 nums1 和 nums2 #xff0c;返回 两个数组中 公共的 、长度最长的子数组的长度 。 如#xff1a; nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] 则最长重复子序列为#xff1a; 321 长度为3 这里采用动态规划解决这个问题。最长公共子序… 题意理解 给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度 。 如 nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] 则最长重复子序列为 321 长度为3 这里采用动态规划解决这个问题。最长公共子序列涉及从nums1的i位置和nums2的j位置长度为x的公共子序列。 所以我们这里定义一个二维数组来统计状态。 解题思路 1定义二维dp数组 dp[i][j]表示从nums1中到第i个位置之前即nums1[i-1]的位置 从nums2中到第j个位置以前即nums2[j-1]的位置所获得的最长公共子序列。 2初始化 dp[0][i] 和dp[0][j]都是拿一个空数组和一个数组求最长公共子序列所以都初始化为0 其余位置在尚未操作之前都初始化为0。 3递推公式 对dp[i][j]进行赋值 首先判断到当前位置的数值是否一致 即nums1[i-1]nums[j-1] 若满足条件则有 dp[i][j]dp[i-1][j-1]1 (4)遍历顺序先便利哪个数组都是可以的 由于dp[i][j]表示的是到nums1的第i个位置以前即nums1[i-1],nums2的第j个位置以前即nums[j-1]的最长公共子序列的所以inum1.size,jnums2.size 1.解题
public int findLength(int[] nums1, int[] nums2) {int[][] dpnew int[nums1.length1][nums2.length1];for(int i0;inums1.length;i){Arrays.fill(dp[i],0);}int max0;for(int i1;i nums1.length;i){for(int j1;jnums2.length;j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}maxMath.max(dp[i][j],max);}}return max;}
2.分析 时间复杂度O(n^2) 空间复杂度O(n^2)
