目錄
LeetCode718.最長重復子串
題目描述
解法1：動態規劃
代碼實現
題目鏈接
題目描述
給兩個整數數組 A 和 B ，返回兩個數組中公共的、長度最長的子數組的長度。
示例：
輸入：
-
A: [1,2,3,2,1]
-
B: [3,2,1,4,7]
-
輸出：3
-
解釋：長度最長的公共子數組是 [3, 2, 1] 。
提示：
-
1 <= len(A), len(B) <= 1000
-
0 <= A[i], B[i] < 100
解法1：動態規劃
本題其實是動規解決的經典題目，我們只要想到 用二維數組可以記錄兩個字符串的所有比較情況，這樣就比較好推 遞推公式了。 分析如下：
-
確定dp數組（dp table）以及下標的含義
dp[i]：以下標i - 1為結尾的A，和以下標j - 1為結尾的B，最長重復子數組長度為dpi。 （特別注意： “以下標i - 1為結尾的A” 標明一定是 以A[i-1]為結尾的字符串 ）
此時細心的同學應該發現，那dp[0]是什么含義呢？總不能是以下標-1為結尾的A數組吧。其實dp[i]的定義也就決定著，我們在遍歷dp[i]的時候i 和 j都要從1開始。那有同學問了，我就定義dp[i]為 以下標i為結尾的A，和以下標j 為結尾的B，最長重復子數組長度。不行么？
行倒是行！ 但實現起來就麻煩一點，需要單獨處理初始化部分，在本題解下面的拓展內容里，我給出了 第二種 dp數組的定義方式所對應的代碼和講解，大家比較一下就了解了。
-
確定遞推公式
根據dpi的定義，dpi的狀態只能由dpi - 1推導出來。即當A[i - 1] 和B[j - 1]相等的時候，dpi = dp[i - 1] + 1;根據遞推公式可以看出，遍歷i 和 j 要從1開始！
-
dp數組如何初始化
根據dpi的定義，dp[i] 和dp[0]其實都是沒有意義的！但dp[i]和dp[0]要初始值，因為 為了方便遞歸公式dp[i] = dp[i - 1] + 1;
所以dp[i] 和dp[0]初始化為0。
舉個例子A[0]如果和B[0]相同的話，dp[1] = dp[0] + 1，只有dp[0]初始為0，正好符合遞推公式逐步累加起來。
-
確定遍歷順序
外層for循環遍歷A，內層for循環遍歷B。
代碼實現
class Solution {public int findLength(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int max = 0;int[][] dp = new int[len1][len2];
?for (int i = 0; i < len1; i++) {if (nums1[i] == nums2[0]) dp[i][0] = 1;max = Math.max(max, dp[i][0]);}for (int i = 0; i < len2; i++) {if (nums2[i] == nums1[0]) dp[0][i] = 1;max = Math.max(max, dp[0][i]);}
?for (int i = 1; i < len1; i++) {for (int j = 1; j < len2; j++) {if (nums1[i] == nums2[j]) {dp[i][j] = dp[i-1][j-1] + 1;max = Math.max(max, dp[i][j]);}
?
?}}
?return max;}
}
