718.maximum-length-of-repeated-subarray.md

718. 最长公共子数组(子串)

1. 描述：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
2. 思路：动态规划
   • 定义二维数组dp。dp[i][j]意思是，对于以i结尾的A,以j结尾的B，目前公共子串最长长度是多少。
   • dp初始化为0：顺序是从前到后。
   • 递推方程
     • 回顾：在同类问题最长公共子序列中，递推公式是：

       if(A[i] == A[j])
           dp[i][j] = dp[i-1][j-1] + 1;
       else
           dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
       

     • 在本题最长公共子数组(子串)中，递推公式是：

       if(A[i] == A[j])
           dp[i][j] = dp[i-1][j-1] + 1;
       else
           dp[i][j] = 0;
       

实现

1. 动态规划：二维

   class Solution {
   public:
       int findLength(vector<int>& A, vector<int>& B) {
           // 初始化
           vector<vector<int>> dp(A.size()+1, vector<int>(B.size()+1, 0));
           int res = INT_MIN;
           // 从前到后
           for(int i=1; i<=A.size(); i++){
               for(int j=1; j<=B.size(); j++){
                   if(A[i-1]==B[j-1])
                       dp[i][j] = dp[i-1][j-1] +1;
                   else
                       dp[i][j] = 0;
                   res = max(dp[i][j], res);
               }
           }
           return res;
       }
   };
   

2. 动态规划：一维。注意，倒序。

   class Solution {
   public:
       int findLength(vector<int>& A, vector<int>& B){
           int m=A.size(), n=B.size();
           int res=0, i, j;
           // 初始化
           vector<int> f(n+1, 0);
           for(i=0; i<m; i++){
               // 注意，这里是倒序
               for (int j = n-1; j >= 0; j--) {
                   if(A[i]==B[j]){
                       f[j+1] = f[j]+1;
                   }
                   else{
                       f[j+1] = 0;
                   }
                   res = max(res, f[j+1]);
               }
           }
           return res;
       }    
   };