一個小例子

問 : 1+1+1+1+1 = ？

答 ：5

問：再 + 1 = ?

答 ：6

這就是DP算法的大概意思，比起問6個1相加等於6，需要計算6次。那麼把之前計算過的5個1相加等於5再加上1等於6，這樣拿到結果少計算了5次。把1+1換成複雜的運算，基本就適用於各種DP算法的場景了。

DP算法

通過把複雜的問題，分解成較簡單的子問題合集，再把子問題的結果保存在一般是帶索引的數據結構裡。下次再需要計算的時候則把已經計算完的值拿來用以縮短計算時間。

CodeWars 問題 Sums of Parts

首先舉個簡單的例子，在解決這個問題的時候甚至很難察覺到使用到了DP算法

Let us consider this example (array written in general format): （舉個例子，如下方數組）

<code>ls = [0, 1, 3, 6, 10]/<code>

Its following parts:（如下）

<code>ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []/<code>

The corresponding sums are (put together in a list)（對應輸出結果放在一個數組裡應該是）:

<code> [20, 20, 19, 16, 10, 0]/<code>

如果直接按照邏輯來寫的話，代碼應該是，先計算出每個shift完的數組，求和，再合併。有點麻煩。

<code>//不自覺的一寫就是這樣，本質上就是DP算法了，因為最後要求的結果數組中，每一項都是可以基於下一項來計算出
function partsSums(ls) {
    let dp = Array(ls.length+1).fill(0)
    let count = 0
    ls.reduceRight((total,ele)=>{return dp[++count]=total+ele},0)
    return dp.reverse()
}
//準確的說，這個問題 ， 並不是用DP算法解決問題，而是在解決問題的過程中，實現了DP算法的思路。
//最後返回的結果 dp 其實就是大部分DP算法的中間寄存的數據結構。/<code>

熱身結束。我們接下來用3個問題循序漸進的的研究下 Dynamic Programming

1 ，Maximum SubArray 最大子序和

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

<code>輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。/<code> 

第一步 ：確定 dp 數組 的值 應該是 以 dp 數組的索引 i 為終點的 最大子序和

<code>let dp = Array(inputArray.length) // dp[i] 的值就是 以i為終點 的 最大子序和/<code>

第二步 : 確定邏輯，dp[i]的值應該用什麼邏輯來計算？

<code>dp[i] = Math.max( inputArray[i] , dp[i-1]+inputArray[i] ) 
//這裡需要注意，先不考慮 dp[i-1] 是怎麼計算 出來就是 它的最大子序和的
//只考慮 已知dp[i-1]就是最大子序和，那麼要計算dp[i]的最大子序和需要什麼樣的邏輯。
//最大子序 是連續的 所以 對於 dp[i]來說，就是帶不帶 inputArray[i] 加入的問題，帶就加上，不帶就重新開始/<code>

第三步 : 敲代碼 ^_^

<code>function maxSubArray (nums) {
  let dp = new Int32Array(nums.length+1)
  nums.map((e,i)=>{
  \tdp[i+1] = Math.max(nums[i],dp[i]+nums[i])
  })
  dp[0] = nums[0] //本來想直接 dp.shift() 。沒想到typedArray不支持這個方法
\treturn Math.max(...dp)
}
//程序有點瑕疵，在沒有shift掉的情況下，dp[i]表示的其實是 nums[i-1]的 maxSubArrayLength
//用 map 又不寫判斷的問題，還是 for 循環更合適，算了，繞一點連連腦吧。跟理解DP算法比不算什麼
//把最後的比較放在map裡 那就是 一次遍歷 複雜度是 O(N) , 空間上還有優化空間 ^_^/<code> 

2，LIS Longest Increasing Subsequence 最長上升子序列

給定一個無序的整數數組，找到其中最長上升子序列的長度。

<code>輸入: [10,9,2,5,3,7,101,18]
輸出: 4 
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。/<code>

第一步，確定dp數組 要存儲的 內容 ，dp[i]應該是 把inputArray[i]作為數組的結尾，存儲最長上升子序列的長度。（有了問題1的鋪墊這裡無需贅述了。邏輯相同）

第二步，確定邏輯，dp[i]的值相比於dp[i-1]應該如何去計算

<code>dp[i] = inputArray[i] > inputArray[i-1] ? dp[i-1] + 1 : dp[i]
//如果 inputArray[i] 比 上一個要大的 話 ，那麼“最長”上升子序列的長度就應該+1，否則不變
//上方的想法是錯誤的。對於[1,2,0,3]這種情況 2對應的dp[i]應該是2，那麼0對應的dp[i]也是2,明顯是錯誤的
//也就是說
dp[i] = inputArray[i] > inputArray[j] ? dp[j]+1 : dp[i] // j的範圍是 0 -> i-1
//同時還要保證dp[i]在經歷了一輪循環後一直保持在最大值
//比如這種情況[1,2,3,0,1]
dp[i] = inputArray[i] > inputArray[j] ? Math.max( dp[j]+1 , dp[i] ): dp[i]/<code>

第三步 ，來了老弟

<code>function lengthOfLIS (nums) { 

\tlet size = nums.length
  let dp = new Int32Array(size).fill(1)
  for( let i = 1 ; i < size ; i++ ){
  \tfor(let j = 0 ; j < i ; j++){
    \tdp[i] = nums[i] > nums[j] ? Math.max( dp[j]+1 , dp[i] ): dp[i]
    }
  }
  return Math.max(...dp)
}
//在解題的過程中會感覺到 第二層 循環有可以優化的地方。mark一下 由於是兩個循環複雜度是 O(N²)/<code>

強迫症，優化一下吧

第二層循環其實沒有必要從0開始，從第一個最大dp[j]開始就可以了，比這個位置j更小的值就算再+1，最後的最大值頂多相等。

<code>function lengthOfLIS (nums) {
\tlet size = nums.length
    if(size===0)return 0 //增加一個空數組的判斷
    let dp = new Int32Array(size).fill(1)
    let biggest = 1 // 新增一個最大值 也就是 dp[i]最大的那個的存儲位置
    let bIndex = 0 // 索引位置，
    for( let i = 1 ; i < size ; i++ ){
  \t    for(let j = bIndex ; j < i ; j++){
    \t    dp[i] = nums[i] > nums[j] ? Math.max( dp[j]+1 , dp[i] ): dp[i]
        }
      //更新 biggest的值用於比較 更新bIndex的位置
        if(dp[i]>biggest){
            bIndex = i-1 ;
            biggest = dp[i]
        }
    }
    return biggest
}
//這樣來看，計算量少了一半，第二個循環那裡應該還是可以繼續優化了。/<code> 

3，LCS Longest Common SubSequence 最長公共子序列

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長公共子序列。

<code>輸入：text1 = "abcde", text2 = "ace" 
輸出：3  
解釋：最長公共子序列是 "ace"，它的長度為 3。

輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長公共子序列是 "abc"，它的長度為 3。

輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個字符串沒有公共子序列，返回 0。/<code>

第一步，確定dp數組，之前的輸入都是單數組，這回是兩個字符串，也就當成兩個數組吧。不管dp的結構如何，dp的每一項含義是確定的，在當前情況下，代表兩個字符串的最長公共子序列。

<code>我們拿 text1 = "abc", text2 = "cde" 舉個例子
dp的結構如果是
\\ a b c |
a 0 
c
---------/<code>

我們確定dp的結構是二維數組，沒一項代表當前情況下的 兩個裁剪後的字符串的最長公共子序列

第二步，確定邏輯 , 在兩個值相等的情況下，右下角的值由對應的左上位置+1,反之，取兩個邊的最大值。這裡要研究一遍二維數組的規律。發現存在這樣的邏輯。

<code>dp[i][j] = text1[i] === text2[j] 
  ? dp[i-1][j-1] + 1 
\t: Math.max(dp[i-1][j],dp[i][j-1])
//要注意 現在的 i j 都只是我們自己理解的循環中的結構。邏輯上還不嚴謹/<code>

第三步，動手

<code>var longestCommonSubsequence = function(text1, text2) {
    let [l1,l2] = [text1.length,text2.length]
    let dp = Array.from(text1+' ',()=>new Int32Array(l2+1))
    for(let i = 1 ; i<=l1 ; i++){
        for(let j = 1 ; j <= l2 ; j++){
\t\t\t\t\tdp[i][j] = text1[i-1] === text2[j-1] 
            ? dp[i-1][j-1] + 1Math.max(dp[i-1][j],dp[i][j-1])
        }
    }
    return dp[l1][l2]
};/<code>

總結

如果第一次接觸 dynamic programming 不要急 ， 這東西還是要多想的。它非常適用於“子結構”的計算。如果遇到各種各樣的 子結構 並且結構複雜，不妨試試 DP算法。

這回的 代碼裡 Array.from 是個較新的嘗試 ，Array.prototype.reduceRight , Math.max，跟之前相關，現在使用上已經很熟練了。 Array.prototype.fill 填補了 js數組裡初始化比較尷尬的情況 。typedArray 比如 Int32Array這次就來試一試，在原型方法上跟Array還是有差距了，比如shift就不行，原因自然就是已經分配好了一段buffer空間了吧。[a,b] = [b,a] 解構賦值 瞭解下 ？

閱讀更多 野碼無繮 的文章

關鍵字: 數據結構 算法 刻板