譯者 | 趙青窕

審校 | 梁策 孫淑娟

如果你已有不少編程經歷，對動態規劃這個術語大概不會陌生。動態規劃常常是技術面試的重點話題，在設計評審會議或與開發者的交流互動中也會涉及。本文將介紹什么是動態規劃及運用動態規劃的原因。

為清晰闡釋動態規劃概念，我將用Swift代碼示例來說明，其他語言亦可適用。

思維方式

與特定的編碼語法或設計模式不同，動態編程不是一種具體算法，而是一種思維方式。因此，具體到執行層面，動態規劃有多種表現形式。

動態規劃的核心思想是將一個大問題化整為零。同時，執行動態規劃的推薦方式也需要數據存儲和重用來提高算法效率。軟件開發中的許多問題都可以通過各種形式的動態規劃來解決，關鍵是要知道什么時候用簡單變量，什么時候用復雜的數據結構或算法來設計出最佳解決方案。

例如，代碼變量可視為動態規劃的基本形式。變量的目的是在內存中保留一個特定的位置，以便之后調用。

//非記憶函數
func addNumbers(lhs: Int, rhs: Int) -> Int {
   return lhs + rhs
}

//記憶函數
func addNumbersMemo(lhs: Int, rhs: Int) -> Int {
   let result: Int = lhs + rhs
     return result
}

上面的addNumbersMemo 進行了一個簡要引入，而動態規劃解決方案的目標則是將先前看到的值保留，這種設計技巧被稱為記憶。

代碼挑戰-數字對

多年來，我曾與幾十名準備面試蘋果、Facebook和亞馬遜等頂級公司的開發人員進行了模擬面試，大多數人都很樂意在模擬時跳過那些可怕的現場白板面試或帶回家的編程項目。但事實是，當中很多題目正是專門測試一個人對計算機科學基礎知識的基本理解。例如，下面這種情況：

/*

在技術面試中，你被給到一個數組，然后需要找到一對與給定目標值相等的數字。數字可正可負，或兩者兼有。你能設計出一個在O(n)線性時間內工作的算法嗎?

let sequence = [8, 10, 2, 9, 7, 5]
let results = pairValues(sum: 11) = //returns (9, 2)
*/

對開發人員來說，解決問題的方式通常有很多種。在本例中，我們的目標是找到數字對來達到預期結果。人用肉眼能快速瀏覽數字序列，很容易找到9和2的一對。但是，算法需要檢查并比較序列中的每個值，或者開發一個更精簡的解決方案才能幫助我們找到正在尋找的值。接下來我將分別闡述這兩種技術。

暴力方式

第一種方法是先查看第一個值，然后后續一一檢查每個值，判斷其差異能否實現目標。例如，我們的算法檢查數組中的第一個數值8，然后在剩下的值里找3(例如 11-8=3)。但我們發現這一組里沒有3，那么算法就以相同的方式繼續找下一個值(也就是例子里的10)，直到找到成功匹配的一對。

在不考慮大O符號的細節的情況下，我們可以認為這類解決方式的平均時間復雜度是O(n ^ 2)或更大，這主要是因為我們算法的工作方式是每個值與其他值比較。其過程可以通過下面的代碼實現:

let sequence = [8, 10, 2, 9, 7, 5]

//非記憶方法 - O(n ^ 2)
func pairNumbers(sum: Int) -> (Int, Int) {
    
  for a in sequence {
        let diff = sum - a
     
        for b in sequence {
            if (b != a) && (b == diff) {
                return (a, b)
            }
        }
  }    
  return (0, 0)
}

記憶方式

接下來，讓我們來利用記憶的思維方式來解決問題。在執行代碼之前，我們需要思考如何利用存儲以前計算到的值幫助簡化這個過程。使用標準數組是可行的，但集合對象(也稱為哈希表或散列表)也可提供優化的解決方案。

//記憶方法 - O(n + d)
func pairNumbersMemoized(sum: Int) -> (Int, Int) {
    
  var addends = Set<Int>()
    
  for a in sequence {
        let diff = sum - a
     
      if addends.contains(diff) { //O(1) - constant time lookup
            return (a, diff)
        }
        //store previously seen value
        else {
            addends.insert(a)
        }
      }
    
  return (0, 0)
 }

通過使用記憶方法，我們將之前看到的值添加到集合對象中，從而將算法的平均運行時效率提高到O(n + d)。熟悉哈希結構的人會知道，項目的插入和檢索的時間復雜度是O(1)——常數時間內。這進一步簡化了我們的解決方案，因為集合被設計為以優化方式檢索值而無需考慮其大小。

斐波那契序列

遞歸是人們在學習各種編程技術時會碰到的一個主題。遞歸解決方案通過一個引用自身的模型來工作，因此遞歸技術是通過算法或數據結構實現的。斐波那契數列就是一個著名的遞歸案例，在這個數列中每一項等于前兩項之和(0、1、1、2、3、5、8、13、21等):

public func fibRec(_ n: Int) -> Int {
      if n < 2 {
          return n
      } else {
          return fibRec(n-1) + fibRec(n-2)
      }
 }

在檢查上述代碼時，代碼未報錯并按預期實現。但是，該算法的性能有些需要注意:

如上述表格所示，函數被調用的次數顯著增加。與我們前面的示例類似，算法的性能根據輸入大小呈指數級下降，這是因為該操作不存儲以前的計算值。如果存儲變量不能訪問，我們獲取前面所需值的唯一方法就是遞歸。假設在生產環境中使用此代碼，該函數可能會引入bug或性能錯誤。讓我們來重構代碼以使用記憶方法:

func fibMemoizedPosition(_ n: Int) -> Int {

      var sequence: Array<Int> = [0, 1]
      var results: Int = 0
      var i: Int = sequence.count
     
      //trivial case
      guard n > i else {
          return n
      }
     
      //all other cases..
      while i <= n {
          results = sequence[i - 1] + sequence[i - 2]
          sequence.append(results)
          i += 1
      }
     
      return results
}

修改后的解決方案通過使用存儲變量可支持記憶化方法，且重構后的代碼不再需要遞歸技術。最前面的兩個值相加，其和被添加到結果中，結果再被添加到主數組序列中。雖然算法的性能仍然取決于序列大小，但我們的修改將算法的時間復雜度提高到O(n) ——線性時間。另外，因為只添加單個函數到調用堆棧中，我們的迭代解決方案較容易修改、測試和調試，從而減少了內存管理和對象作用域的復雜性。

總結

通過本文我們了解了動態規劃并不是一種特定的設計模式，而是一種思維方式。它的目標是創建一個解決方案來保存以前看到的值，以提高時間效率。雖然示例涵蓋的是基本算法，但動態規劃幾乎為所有程序提供了基礎，這當中既包括使用簡單變量也包括復雜的數據結構。

譯者介紹

趙青窕，51CTO社區編輯，從事多年驅動開發。研究興趣包含安全OS和網絡安全領域，曾獲得陜西賽區數學建模獎，發表過網絡相關專利。

原文標題：The complete beginners guide to dynamic programming，作者：Wayne Bishop