本文主要是介绍动态规划 Leetcode 718 最长重复子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最长重复子数组
Leetcode 718
学习记录自代码随想录
要点：1.想到dp数组二维表达的含义；
2.想到正确初始化dp数组， f o r ( i n t i = 0 ; i < m ; i + + ) i f ( n u m s 1 [ i ] = = n u m s 2 [ 0 ] ) d p [ i ] [ 0 ] = 1 f o r ( i n t j = 0 ; j < n ; j + + ) i f ( n u m s 2 [ j ] = = n u m s 1 [ 0 ] ) d p [ 0 ] [ j ] = 1 for(int i = 0; i < m; i++) if(nums1[i] == nums2[0]) dp[i][0] = 1 \\ for(int j = 0; j < n; j++) if(nums2[j] == nums1[0]) dp[0][j] = 1 for(inti=0;i<m;i++)if(nums1[i]==nums2[0])dp[i][0]=1for(intj=0;j<n;j++)if(nums2[j]==nums1[0])dp[0][j]=1
3.两层遍历都要从0开始；
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();// 1.定义dp数组dp[i][j]含义为以nums1[i]结尾和nums2[j]结尾时最大公共数组的长度vector<vector<int>> dp(m, vector<int>(n, 0));// 2.递推公式 if(nums1[i] == nums2[j]) dp[i][j] = dp[i-1][j-1] + 1;// 3.初始化dp数组for(int i = 0; i < m; i++) if(nums1[i] == nums2[0]) dp[i][0] = 1;for(int j = 0; j < n; j++) if(nums2[j] == nums1[0]) dp[0][j] = 1;// 4.遍历顺序，两层遍历，正向遍历int result = 0;// 需要从0开始遍历，有可能会出现一个数组首个元素和另一个数组中间某个元素相等的情况for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(nums1[i] == nums2[j] && i > 0 && j > 0) dp[i][j] = dp[i-1][j-1] + 1;if(dp[i][j] > result) result = dp[i][j];}}// 5.举例推导dp数组return result;}
};
这篇关于动态规划 Leetcode 718 最长重复子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
