最长重复子数组

动态规划

• 确定dp数组含义
  dp[i][j] ：以下标i - 1为结尾的A（A的第i个元素），和以下标j - 1为结尾的B（B的第j个元素），最长重复子数组长度为dp[i][j]。
• 确定递推公式
  根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
  即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
• 初始化
  dp[0][0]、dp[i][0]、dp[0][j]都为0，因为下标为0意味着没有元素进行匹配，因此匹配的个数也是0。从dp[i][j]开始有意义，即nums1和nums2都拿出了一个元素
  

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
    	//dp数组下标i和j意味着第几个元素，因此长度+1
       vector<vector<int>>  dp(nums1.size()+1 , vector<int>(nums2.size()+1,0));
        int result = 0 ;
        for(int i=0 ; i<nums1.size() ;i++)
        {
            for(int j=0 ;j<nums2.size();j++)
            {
                if(nums1[i] == nums2[j])
                    dp[i+1][j+1] = dp[i][j]+1;
                if(dp[i+1][j+1] > result) result = dp[i+1][j+1];
            }
        
        }
         
        // for(int i=0 ; i<=nums1.size() ;i++)
        // {
        //     for(int j=0 ;j<=nums2.size();j++)
        //     {
        //         if(dp[i][j] > result) result = dp[i][j];
        //          cout<<dp[i][j]<<' ';
        //     }
        //      cout<<endl;
        // }
         return result;
    }
};

二刷

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() , vector<int>(nums2.size(),0));
        int result = 0;

        for(int i=0 ; i<nums1.size() ; i++)
        {
            if(nums1[i] == nums2[0]) dp[i][0] = 1;
            if(dp[i][0] > result) result = dp[i][0];
        }
            
        
        for(int j=0 ; j<nums2.size() ; j++)
        {
            if(nums1[0] == nums2[j]) dp[0][j] = 1;
            if(dp[0][j] > result) result = dp[0][j];
        }
            

        for(int i=1 ; i<nums1.size() ; i++)
        {
            for(int j=1 ; j<nums2.size() ;j++)
            {
                if(nums1[i] == nums2[j]) 
                    dp[i][j] = dp[i-1][j-1] + 1;

                if(dp[i][j] > result) result = dp[i][j];
            }
        }

        //  for(int i=0 ; i<nums1.size() ; i++)
        // {
        //     for(int j=0 ; j<nums2.size() ;j++)
        //     {
        //         cout<<dp[i][j]<<' ';
        //     }
        //     cout<<endl;
        // }
        return result;
    }
};

高刷题

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size()+1 , 0 ));

        int result = 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;
                if(dp[i][j] >= result) result = dp[i][j];
            }
        }

        //  for(int i=1 ; i <=nums1.size() ; i++)
        // {
        //     for(int j=1 ; j <=nums2.size() ; j++)
        //     {
        //         cout<<dp[i][j]<<' ';
        //     }
        //     cout<<endl;
        // }

        return result;


    }
};