Leetcode 718. 最长重复子数组

问题描述

解题报告

此题是最长公共子数组，注意与最长公共子序列不同；

对于最长公共子数组， $dp[i][j]$dp[i][j] 表示子串以 $A[i]$A[i] 和 $B[j]$B[j] 结尾的最长公共子数组。
$if A[i]==B[j] \;dp[i][j]=dp[i-1][j-1]+1\\ if A[i]\ne B[j]\;dp[i][j]=0$ifA[i]==B[j]dp[i][j]=dp[i−1][j−1]+1ifA[i]​=B[j]dp[i][j]=0

对于最长公共子序列， $dp[i][j]$dp[i][j] 表示数组 $A[1,\cdots ,i]$A[1,⋯,i] 和数组 $B[1,\cdots,j]$B[1,⋯,j] 的最长公共子串的长度
$if A[i]==B[j]\;dp[i][j]=dp[i-1][j-1]+1\\ if A[i] \ne B[j]\;dp[i][j]=max(dp[i-1][j],dp[i][j-1])$ifA[i]==B[j]dp[i][j]=dp[i−1][j−1]+1ifA[i]​=B[j]dp[i][j]=max(dp[i−1][j],dp[i][j−1])

实现代码

• 最长公共子数组

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m=A.size(),n=B.size(),ans=0;
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(A[i-1]==B[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    ans=max(ans,dp[i][j]);
                }
            }
        }
        return ans;
    }
};

• 最长公共子序列

class Solution{
	public:
		int FindLength(vector<int>& A,vector<int>& B){
			int m=A.size(),n=B.size(),ans=0;
        	vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        	for(int i=1;i<=m;i++){
            	for(int j=1;j<=n;j++){
                	if(A[i-1]==B[j-1]){
                    	dp[i][j]=dp[i-1][j-1];
                	}
                	else{
                		dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                	}
            	}
        	}
        	return dp[m][n]; 
		}
};