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