動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃（英語(yǔ)：Dynamic programming恬口，簡(jiǎn)稱DP）是一種在數(shù)學(xué)、管理科學(xué)弥锄、計(jì)算機(jī)科學(xué)丧靡、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法籽暇。
背包問(wèn)題
簡(jiǎn)單算法, 書中一開(kāi)始是通過(guò)排列組合的方式, 但是速度有些慢, 時(shí)間復(fù)雜度為 O(n2)
引入動(dòng)態(tài)規(guī)劃, 將背包問(wèn)題繪制成表格
[圖片上傳失敗...(image-a29e02-1528622649240)]
音響(3000美元温治、 4磅)、 筆記本電腦(2000美元戒悠、3磅)熬荆、 吉他(1500美元、1磅)
最終結(jié)果, 將吉他和筆記本電腦放入背包時(shí)價(jià)值最高, 為 3500 美元
[圖片上傳失敗...(image-65950a-1528622649240)]
最長(zhǎng)公共子串
引入一個(gè)例子绸狐。 假設(shè)你管理著網(wǎng)站 dictionary.com卤恳。 用戶在該
網(wǎng)站輸入單詞時(shí), 你需要給出其定義。
但用戶拼錯(cuò)了, 你必須要猜測(cè)他原本要輸入的是什么單詞寒矿。 例如, Alex 想查單詞fish, 但不小心輸入了hish突琳。 在你的字典中, 根本就沒(méi)有這樣的單詞, 但有幾個(gè)類似的單詞。
同樣繪制表格, 這其實(shí)是求最長(zhǎng)公共子串
最長(zhǎng)公共序列
[圖片上傳失敗...(image-ce6269-1528622649240)]
偽代碼
if word_a[i] == word_b[j]: # 兩個(gè)字母相同
cell[i][j] = cell[i-1][j-1] + 1
else: # 兩個(gè)字母不同
cell[i][j] = max(cell[i-j][j], cell[i][j-1)
小結(jié)
書上的例子還是比較好理解的, 實(shí)際中的那些題目可能就夠嗆了
最后附上小灰漫解動(dòng)態(tài)規(guī)劃: https://juejin.im/post/5a29d52cf265da43333e4da7
