譯者 | 趙青窕

審校 | 梁策 孫淑娟

如果你已有不少編程經(jīng)歷，對(duì)動(dòng)態(tài)規(guī)劃這個(gè)術(shù)語大概不會(huì)陌生。動(dòng)態(tài)規(guī)劃常常是技術(shù)面試的重點(diǎn)話題，在設(shè)計(jì)評(píng)審會(huì)議或與開發(fā)者的交流互動(dòng)中也會(huì)涉及。本文將介紹什么是動(dòng)態(tài)規(guī)劃及運(yùn)用動(dòng)態(tài)規(guī)劃的原因。

為清晰闡釋動(dòng)態(tài)規(guī)劃概念，我將用Swift代碼示例來說明，其他語言亦可適用。

思維方式

與特定的編碼語法或設(shè)計(jì)模式不同，動(dòng)態(tài)編程不是一種具體算法，而是一種思維方式。因此，具體到執(zhí)行層面，動(dòng)態(tài)規(guī)劃有多種表現(xiàn)形式。

動(dòng)態(tài)規(guī)劃的核心思想是將一個(gè)大問題化整為零。同時(shí)，執(zhí)行動(dòng)態(tài)規(guī)劃的推薦方式也需要數(shù)據(jù)存儲(chǔ)和重用來提高算法效率。軟件開發(fā)中的許多問題都可以通過各種形式的動(dòng)態(tài)規(guī)劃來解決，關(guān)鍵是要知道什么時(shí)候用簡單變量，什么時(shí)候用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)或算法來設(shè)計(jì)出最佳解決方案。

例如，代碼變量可視為動(dòng)態(tài)規(guī)劃的基本形式。變量的目的是在內(nèi)存中保留一個(gè)特定的位置，以便之后調(diào)用。

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

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

上面的addNumbersMemo 進(jìn)行了一個(gè)簡要引入，而動(dòng)態(tài)規(guī)劃解決方案的目標(biāo)則是將先前看到的值保留，這種設(shè)計(jì)技巧被稱為記憶。

代碼挑戰(zhàn)-數(shù)字對(duì)

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

/*

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

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

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

暴力方式

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

在不考慮大O符號(hào)的細(xì)節(jié)的情況下，我們可以認(rèn)為這類解決方式的平均時(shí)間復(fù)雜度是O(n ^ 2)或更大，這主要是因?yàn)槲覀兯惴ǖ墓ぷ鞣绞绞敲總€(gè)值與其他值比較。其過程可以通過下面的代碼實(shí)現(xiàn):

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)
}

記憶方式

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

//記憶方法 - 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)
 }

通過使用記憶方法，我們將之前看到的值添加到集合對(duì)象中，從而將算法的平均運(yùn)行時(shí)效率提高到O(n + d)。熟悉哈希結(jié)構(gòu)的人會(huì)知道，項(xiàng)目的插入和檢索的時(shí)間復(fù)雜度是O(1)——常數(shù)時(shí)間內(nèi)。這進(jìn)一步簡化了我們的解決方案，因?yàn)榧媳辉O(shè)計(jì)為以優(yōu)化方式檢索值而無需考慮其大小。

斐波那契序列

遞歸是人們在學(xué)習(xí)各種編程技術(shù)時(shí)會(huì)碰到的一個(gè)主題。遞歸解決方案通過一個(gè)引用自身的模型來工作，因此遞歸技術(shù)是通過算法或數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。斐波那契數(shù)列就是一個(gè)著名的遞歸案例，在這個(gè)數(shù)列中每一項(xiàng)等于前兩項(xiàng)之和(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)
      }
 }

在檢查上述代碼時(shí)，代碼未報(bào)錯(cuò)并按預(yù)期實(shí)現(xiàn)。但是，該算法的性能有些需要注意:

如上述表格所示，函數(shù)被調(diào)用的次數(shù)顯著增加。與我們前面的示例類似，算法的性能根據(jù)輸入大小呈指數(shù)級(jí)下降，這是因?yàn)樵摬僮鞑淮鎯?chǔ)以前的計(jì)算值。如果存儲(chǔ)變量不能訪問，我們獲取前面所需值的唯一方法就是遞歸。假設(shè)在生產(chǎn)環(huán)境中使用此代碼，該函數(shù)可能會(huì)引入bug或性能錯(cuò)誤。讓我們來重構(gòu)代碼以使用記憶方法:

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
}

修改后的解決方案通過使用存儲(chǔ)變量可支持記憶化方法，且重構(gòu)后的代碼不再需要遞歸技術(shù)。最前面的兩個(gè)值相加，其和被添加到結(jié)果中，結(jié)果再被添加到主數(shù)組序列中。雖然算法的性能仍然取決于序列大小，但我們的修改將算法的時(shí)間復(fù)雜度提高到O(n) ——線性時(shí)間。另外，因?yàn)橹惶砑訂蝹€(gè)函數(shù)到調(diào)用堆棧中，我們的迭代解決方案較容易修改、測試和調(diào)試，從而減少了內(nèi)存管理和對(duì)象作用域的復(fù)雜性。

總結(jié)

通過本文我們了解了動(dòng)態(tài)規(guī)劃并不是一種特定的設(shè)計(jì)模式，而是一種思維方式。它的目標(biāo)是創(chuàng)建一個(gè)解決方案來保存以前看到的值，以提高時(shí)間效率。雖然示例涵蓋的是基本算法，但動(dòng)態(tài)規(guī)劃幾乎為所有程序提供了基礎(chǔ)，這當(dāng)中既包括使用簡單變量也包括復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

譯者介紹

趙青窕，51CTO社區(qū)編輯，從事多年驅(qū)動(dòng)開發(fā)。研究興趣包含安全OS和網(wǎng)絡(luò)安全領(lǐng)域，曾獲得陜西賽區(qū)數(shù)學(xué)建模獎(jiǎng)，發(fā)表過網(wǎng)絡(luò)相關(guān)專利。

原文標(biāo)題：The complete beginners guide to dynamic programming，作者：Wayne Bishop