本文主要是介绍自学动态规划——最长重复子数组(子序列问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最长重复子数组
718. 最长重复子数组 - 力扣(LeetCode)
第一次接触,确实会有些懵,但是看了题解,仔细想想,确实是这么回事。要点如下:
- dp数组含义——
dp[i][j]
表示当num1取i个,nums2取j个的时候,其最长重复子数组的长度 - 递推公式——
if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
表示,如果当前长度下对应的最后一个值匹配上了,那么当前(i,j)的最长重复子数组的长度应该是之前两个数组退格1个时候的长度+1 - 初始化——当
i==0 || j==0
的时候,相当于一个数组为空,那么是绝对无法匹配的,即初始化为0。这也是为什么从1开始遍历,因为从0开始无意义,还需要额外加个判断,让她为0,还不如从一开始就让他为0
AC:
int findLength(vector<int>& nums1, vector<int>& nums2) {//只用1维实在很难想出来应该怎么做,但是如果开二维就不一样了int n1=nums1.size(),n2=nums2.size();vector<vector<int>>dp(n1+1,vector<int>(n2+1,0)); //dp[i][j] 表示当取num1长度i,num2长度j的时候,对应的最长重复子数组长度//初始化:i或j为0,那一定没有子数组,所以保持为0即可int ans=0;for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(nums1[i-1]==nums2[j-1]) //因为ij表示的长度,所以定位到具体值的时候需要-1dp[i][j]=dp[i-1][j-1]+1; //当前长度应该是两者退格1个前的基础上+1ans=max(ans,dp[i][j]); //记录最值}}return ans;}
这篇关于自学动态规划——最长重复子数组(子序列问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!