題目描述：
給兩個(gè)整數(shù)數(shù)組?A?和?B?，返回兩個(gè)數(shù)組中公共的、長度最長的子數(shù)組的長度。
示例：
輸入:A: [1,2,3,2,1]? B: [3,2,1,4,7]
輸出:3
解釋:長度最長的公共子數(shù)組是 [3, 2, 1]。
題目鏈接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
在LeetCode中這題屬于中等難度題，一般來說中等難度題無法使用暴力法通過。但是本人頭鐵，就是想試一試，反正暴力法寫起來相對(duì)來說是最簡單的。當(dāng)然，最主要的原因是通過暴力法我們能夠清楚的感受到算法存在哪些不足、哪些地方可以改進(jìn)。進(jìn)而寫出令自己滿意的代碼。
暴力法：
每次我們從A組中選取一個(gè)子數(shù)組，然后去B組中找到一個(gè)與它相同的。我們可以先選取長度為Math.max（A.length,B.length）的子數(shù)組，然后慢慢減少長度，直到長度為0.
上面的代碼一看時(shí)間復(fù)雜度就很高，循環(huán)寫了好幾層。雖然結(jié)果沒問題，但是顯然不能讓人滿意。問題出在哪里呢？我們在用A中取出子數(shù)組與B數(shù)組匹配時(shí)進(jìn)行了許多重復(fù)的判斷。用題目給到的例子來解釋。我們一開始取出A中的{1,2,3,2,1},然后與B匹配，判斷A[0]與B[0]是否相等。結(jié)束循環(huán)，縮小窗口，取出A中的{1,2,3,2},繼續(xù)與B匹配，判斷A[0]與B[0]是否相等......有此可見，我們對(duì)于已經(jīng)判斷過的元素并沒有好好利用起來。刷題經(jīng)驗(yàn)豐富的同學(xué)可能看出來了，這完全可以用動(dòng)態(tài)規(guī)劃的思想來減少重復(fù)判斷啊。
動(dòng)態(tài)規(guī)劃：
我們使用dp[i][j]來保存A[ 0 : i ] (A[0]到A[i])? 與 B[ 0 : j ]的最長公共前綴長度。dp[i][j]可由dp[i-1][j-1]轉(zhuǎn)移而來。當(dāng)A[ i ]!=B[ j ]時(shí)dp[ i ][ j ] = 0.若A[ i ]==B[ j ] 那么dp[ i ][ j ]=dp[ i -1 ][ j - 1 ] + 1.由于我們只需要最大值，所以每次計(jì)算完dp[i][j]后都將maxLength與它比較一下，然后取較大者。
這個(gè)時(shí)候，我們就完美的解決了重復(fù)計(jì)算的問題。當(dāng)然，這題仍然有改進(jìn)的空間。若是有時(shí)間的話就更新一下。
