leetcode 718 最长重复子数组

题目：718. 最长重复子数组

参考题解：最长重复子数组-代码随想录、最长重复子数组-力扣官方题解

求两个序列，最长重复长度。暴力解，必然可以，但会超时。

具体思路见代码实现。实现如下。

#include 
#include 
using namespace std;

class Solution {
public:
    int findLength(vector& nums1, vector& nums2) {
        // 暴力解
        // 最长连续重复序列 == nums1[i:] nums2[j:]的最长连续前缀
        int result = 0;
        for(int i=0; i nums1 = {0,0,0,0,0,0,1,0,0,0};
    vector nums2 = {0,0,0,0,0,0,0,1,0,0};
    Solution s;
    cout< 
动态规划 
下面代码实现和图片，来自参考题解。
 
class Solution {
public:
    int findLength(vector& nums1, vector& nums2) {
        // 动态规划
        // 如果nums1[i]和nums2[j]位置的元素相同dp[i][j] = dp[i-1][j-1] + 1; 前一个位置相同，将dp[i-1][j-1]累加过来；前一个位置不相同，dp[i-1][j-1]位零
        
        int result = 0;
        vector> dp(nums1.size()+1,vector(nums2.size()+1,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;
                result = max(result,dp[i][j]);
            }   
        }

        return result;
    }
};