全面的動態(tài)規(guī)劃入門指南幫你決勝技術(shù)面試

譯者 | 趙青窕

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

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

思維方式

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

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

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

復(fù)制//非記憶函數(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}1.2.3.4.5.6.7.8.9.10.

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

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

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

復(fù)制/*1.

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

復(fù)制let sequence = [8, 10, 2, 9, 7, 5]let results = pairValues(sum: 11) = //returns (9, 2)*/1.2.3.

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

暴力方式

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

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

復(fù)制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)

}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.

記憶方式

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

復(fù)制//記憶方法 - O(n + d)func pairNumbersMemoized(sum: Int) ->(Int, Int) {

var addends = Set()

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)

}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.

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

斐波那契序列

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

復(fù)制public func fibRec(_ n: Int) ->Int { if n

} else { return fibRec(n-1) + fibRec(n-2)

}

}1.2.3.4.5.6.7.

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

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

復(fù)制func fibMemoizedPosition(_ n: Int) ->Int { var sequence: Array = [0, 1] var results: Int = 0

var i: Int = sequence.count

//trivial case

guard n >i else { return n

}

//all other cases..

while i

}

return results}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.

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

總結(jié)

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

譯者介紹

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

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

關(guān)鍵詞： 全面的動態(tài)規(guī)劃入門指南幫你決勝技術(shù)面試 動態(tài)規(guī)劃