建站
咨詢
售后
建站咨詢
新聞中心
審校 | 梁策 孫淑娟
成都創(chuàng)新互聯(lián)憑借在網(wǎng)站建設、網(wǎng)站推廣領域領先的技術能力和多年的行業(yè)經(jīng)驗，為客戶提供超值的營銷型網(wǎng)站建設服務，我們始終認為：好的營銷型網(wǎng)站就是好的業(yè)務員。我們已成功為企業(yè)單位、個人等客戶提供了成都網(wǎng)站設計、成都做網(wǎng)站服務，以良好的商業(yè)信譽，完善的服務及深厚的技術力量處于同行領先地位。
如果你已有不少編程經(jīng)歷，對動態(tài)規(guī)劃這個術語大概不會陌生。動態(tài)規(guī)劃常常是技術面試的重點話題，在設計評審會議或與開發(fā)者的交流互動中也會涉及。本文將介紹什么是動態(tài)規(guī)劃及運用動態(tài)規(guī)劃的原因。
為清晰闡釋動態(tài)規(guī)劃概念，我將用Swift代碼示例來說明，其他語言亦可適用。
思維方式
與特定的編碼語法或設計模式不同，動態(tài)編程不是一種具體算法，而是一種思維方式。因此，具體到執(zhí)行層面，動態(tài)規(guī)劃有多種表現(xiàn)形式。
動態(tài)規(guī)劃的核心思想是將一個大問題化整為零。同時，執(zhí)行動態(tài)規(guī)劃的推薦方式也需要數(shù)據(jù)存儲和重用來提高算法效率。軟件開發(fā)中的許多問題都可以通過各種形式的動態(tài)規(guī)劃來解決，關鍵是要知道什么時候用簡單變量，什么時候用復雜的數(shù)據(jù)結構或算法來設計出最佳解決方案。
例如，代碼變量可視為動態(tài)規(guī)劃的基本形式。變量的目的是在內(nèi)存中保留一個特定的位置，以便之后調(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 進行了一個簡要引入，而動態(tài)規(guī)劃解決方案的目標則是將先前看到的值保留，這種設計技巧被稱為記憶。
代碼挑戰(zhàn)-數(shù)字對
多年來，我曾與幾十名準備面試蘋果、Facebook和亞馬遜等頂級公司的開發(fā)人員進行了模擬面試，大多數(shù)人都很樂意在模擬時跳過那些可怕的現(xiàn)場白板面試或帶回家的編程項目。但事實是，當中很多題目正是專門測試一個人對計算機科學基礎知識的基本理解。例如，下面這種情況：
/*
在技術面試中，你被給到一個數(shù)組，然后需要找到一對與給定目標值相等的數(shù)字。數(shù)字可正可負，或兩者兼有。你能設計出一個在O(n)線性時間內(nèi)工作的算法嗎?
let sequence = [8, 10, 2, 9, 7, 5]
let results = pairValues(sum: 11) = //returns (9, 2)
*/
對開發(fā)人員來說，解決問題的方式通常有很多種。在本例中，我們的目標是找到數(shù)字對來達到預期結果。人用肉眼能快速瀏覽數(shù)字序列，很容易找到9和2的一對。但是，算法需要檢查并比較序列中的每個值，或者開發(fā)一個更精簡的解決方案才能幫助我們找到正在尋找的值。接下來我將分別闡述這兩種技術。
暴力方式
第一種方法是先查看第一個值，然后后續(xù)一一檢查每個值，判斷其差異能否實現(xiàn)目標。例如，我們的算法檢查數(shù)組中的第一個數(shù)值8，然后在剩下的值里找3(例如 11-8=3)。但我們發(fā)現(xiàn)這一組里沒有3，那么算法就以相同的方式繼續(xù)找下一個值(也就是例子里的10)，直到找到成功匹配的一對。
在不考慮大O符號的細節(jié)的情況下，我們可以認為這類解決方式的平均時間復雜度是O(n ^ 2)或更大，這主要是因為我們算法的工作方式是每個值與其他值比較。其過程可以通過下面的代碼實現(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í)行代碼之前，我們需要思考如何利用存儲以前計算到的值幫助簡化這個過程。使用標準數(shù)組是可行的，但集合對象(也稱為哈希表或散列表)也可提供優(yōu)化的解決方案。
//記憶方法 - 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)
}
通過使用記憶方法，我們將之前看到的值添加到集合對象中，從而將算法的平均運行時效率提高到O(n + d)。熟悉哈希結構的人會知道，項目的插入和檢索的時間復雜度是O(1)——常數(shù)時間內(nèi)。這進一步簡化了我們的解決方案，因為集合被設計為以優(yōu)化方式檢索值而無需考慮其大小。
斐波那契序列
遞歸是人們在學習各種編程技術時會碰到的一個主題。遞歸解決方案通過一個引用自身的模型來工作，因此遞歸技術是通過算法或數(shù)據(jù)結構實現(xiàn)的。斐波那契數(shù)列就是一個著名的遞歸案例，在這個數(shù)列中每一項等于前兩項之和(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)
}
}
在檢查上述代碼時，代碼未報錯并按預期實現(xiàn)。但是，該算法的性能有些需要注意:
如上述表格所示，函數(shù)被調(diào)用的次數(shù)顯著增加。與我們前面的示例類似，算法的性能根據(jù)輸入大小呈指數(shù)級下降，這是因為該操作不存儲以前的計算值。如果存儲變量不能訪問，我們獲取前面所需值的唯一方法就是遞歸。假設在生產(chǎn)環(huán)境中使用此代碼，該函數(shù)可能會引入bug或性能錯誤。讓我們來重構代碼以使用記憶方法:
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 <= n {
results = sequence[i - 1] + sequence[i - 2]
sequence.append(results)
i += 1
}
return results
}
修改后的解決方案通過使用存儲變量可支持記憶化方法，且重構后的代碼不再需要遞歸技術。最前面的兩個值相加，其和被添加到結果中，結果再被添加到主數(shù)組序列中。雖然算法的性能仍然取決于序列大小，但我們的修改將算法的時間復雜度提高到O(n) ——線性時間。另外，因為只添加單個函數(shù)到調(diào)用堆棧中，我們的迭代解決方案較容易修改、測試和調(diào)試，從而減少了內(nèi)存管理和對象作用域的復雜性。
總結
通過本文我們了解了動態(tài)規(guī)劃并不是一種特定的設計模式，而是一種思維方式。它的目標是創(chuàng)建一個解決方案來保存以前看到的值，以提高時間效率。雖然示例涵蓋的是基本算法，但動態(tài)規(guī)劃幾乎為所有程序提供了基礎，這當中既包括使用簡單變量也包括復雜的數(shù)據(jù)結構。
譯者介紹
趙青窕，社區(qū)編輯，從事多年驅(qū)動開發(fā)。研究興趣包含安全OS和網(wǎng)絡安全領域，曾獲得陜西賽區(qū)數(shù)學建模獎，發(fā)表過網(wǎng)絡相關專利。
原文標題：The complete beginners guide to dynamic programming，作者：Wayne Bishop
分享名稱：全面的動態(tài)規(guī)劃入門指南幫你決勝技術面試
分享路徑：http://www.5511xx.com/article/dhosgsp.html
