#718 最长重复子数组(动态规划)

718. 最长重复子数组 - 力扣（LeetCode）

提示：Use dynamic programming. dp[i][j] will be the longest common prefix of A[i:] and B[j:].

状态描述：dp[i][j]为nums1[i:]和nums2[j:]的最长重复子数组长度。

以1,2,3,2,1 3,2,1,4,7为例：

dp[2][0]：由于nums1[2]与nums2[0]相同，则这可以是一个重复子数组的起点，检查下一个字符，因此dp[2][0]=1+dp[2+1][0+1]。dp[2+1][0+1]的值由动态规划管理，因此需要从后向前推进。

状态转移方程：dp[i][j]=0(不相同，无法作为起点)/1+dp[i+1][j+1](如果没有越界)

状态初态：dp[n1][0...n2]，dp[0...n1][n2]（边界）

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
      vector<vector<int>> dp(nums1.size(), std::vector<int>(nums2.size(),0));
      //update dp
      int max = 0;
      for (int i = dp.size() - 1; i >= 0; i--)
          for (int j = dp[i].size()-1; j >= 0; j--) {
              if (nums1[i] == nums2[j]) dp[i][j] = 1;
              if (i == dp.size()-1 || j == dp[i].size()-1){
                  if(dp[i][j]>max) max=dp[i][j];
                  continue;
              }
              if(dp[i][j]) dp[i][j] += dp[i + 1][j + 1];
              if(dp[i][j]>max) max=dp[i][j];
          }
      return max;
    }
};

常数优化：

主要取决于二层循环中的4个if条件的不同优先条件，leetcode判题可以到90ms-150ms不等。