自学动态规划——最长重复子数组（子序列问题）

本文主要是介绍自学动态规划——最长重复子数组（子序列问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最长重复子数组

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;}