動(dòng)態(tài)規(guī)劃（英語(yǔ)：Dynamic programming赶袄，簡(jiǎn)稱(chēng)DP）是一種通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法沪停。

動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題浆兰，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法雨饺。

動(dòng)態(tài)規(guī)劃的基本思想：若要解一個(gè)給定問(wèn)題荐吉，我們需要解其不同部分（即子問(wèn)題）对省，再合并子問(wèn)題的解以得出原問(wèn)題的解蝗拿。

通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次蒿涎，從而減少計(jì)算量：一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出哀托，則將其記憶化存儲(chǔ)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表劳秋。這種做法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用仓手。

背包問(wèn)題（Knapsack problem）
一種組合優(yōu)化的NP完全問(wèn)題。問(wèn)題可以描述為：給定一組物品玻淑，每種物品都有自己的重量和價(jià)格嗽冒，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇补履，才能使得物品的總價(jià)格最高辛慰。問(wèn)題的名稱(chēng)來(lái)源于如何選擇最合適的物品放置于給定背包中。

關(guān)于各種背包問(wèn)題的講解詳見(jiàn)：背包問(wèn)題九講

這里給出01背包問(wèn)題和完全背包問(wèn)題的JavaScript實(shí)現(xiàn)
另外干像，“換零錢(qián)問(wèn)題”也是背包問(wèn)題中的一種帅腌。

01背包問(wèn)題
有N件物品和一個(gè)容量為V的背包驰弄。放入第i件物品耗費(fèi)的空間是Ci，得到的價(jià)值是Wi速客。求解將哪些物品裝入背包可使價(jià)值總和最大戚篙。

這是最基礎(chǔ)的背包問(wèn)題。
特點(diǎn)：每種物品僅有一件溺职，可以選擇放或不放岔擂。

用子問(wèn)題定義狀態(tài)：即F [i, v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：

【“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題浪耘，若只考慮第i件物品的策略（放或不放）乱灵，那么就可以轉(zhuǎn)化為一個(gè)只和前i ? 1件物品相關(guān)的問(wèn)題。如果不放第i件物品七冲，那么問(wèn)題就轉(zhuǎn)化為“前i ? 1件物品放入容量為v的背包中”痛倚，價(jià)值為F [i ? 1, v]；如果放第i件物品澜躺，那么問(wèn)題就轉(zhuǎn)化為“前i ? 1件物品放入剩下的容量為v ? Ci的背包中”蝉稳，此時(shí)能獲得的最大價(jià)值就是F [i ? 1, v ? Ci]再加上通過(guò)放入第i件物品獲得的價(jià)值Wi【虮桑】

let dp = new Array()
for (let i = 0; i < 1000; i++) {
  dp[i] = new Array()
  for (let j = 0; j < 1000; j++) {
    dp[i][j] = 0
  }
}

function pack(n, capacity, costs, values) {
  if (n < 0 || capacity < 0) return -1
  if (n === 0 || capacity === 0) return 0
  
  for (let i = 0; i <= n; ++i) {
    for (let j = 0; j <= capacity; ++j) {
      if (i > 0 && j >= costs[i - 1]) {
        dp[i][j] = Math.max(dp[i - 1][j], 
                    dp[i - 1][j - costs[i - 1]] + values[i - 1])
      }
    }
  }

  return dp[n][capacity]
}

console.log(pack(4, 10, [1, 3, 4, 5], 
                        [3, 6, 2, 8]))
// 輸出
17

完全背包問(wèn)題
有N種物品和一個(gè)容量為V 的背包耘戚，每種物品都有無(wú)限件可用。放入第i種物品的耗費(fèi)的空間是Ci操漠，得到的價(jià)值是Wi收津。求解：將哪些物品裝入背包，可使這些物品的耗費(fèi)的空間總和不超過(guò)背包容量浊伙，且價(jià)值總和最大撞秋。

這個(gè)問(wèn)題非常類(lèi)似于01背包問(wèn)題，所不同的是每種物品有無(wú)限件吧黄。也就是從每種物品的角度考慮部服，與它相關(guān)的策略已并非取或不取兩種，而是有取0件拗慨、取1件廓八、取2件……直至取?V /Ci?件等很多種。

如果仍然按照解01背包時(shí)的思路赵抢，令F [i, v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值剧蹂。仍然可以按照每種物品不同的策略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，像這樣：

這跟01背包問(wèn)題一樣有O(V N)個(gè)狀態(tài)需要求解烦却，但求解每個(gè)狀態(tài)的時(shí)間已經(jīng)不是常數(shù)了宠叼，求解狀態(tài)F [i, v]的時(shí)間是O(v / Ci)，總的復(fù)雜度可以認(rèn)為是O(NV Σ(v / Ci))，是比較大的冒冬。
將01背包問(wèn)題的基本思路加以改進(jìn)伸蚯，得到了這樣一個(gè)清晰的方法。這說(shuō)明01背包問(wèn)題的方程的確是很重要简烤，可以推及其它類(lèi)型的背包問(wèn)題剂邮。但我們還是要試圖改進(jìn)這個(gè)復(fù)雜度。

最少換零錢(qián)問(wèn)題
如果我們有面值為1元横侦、3元和5元的硬幣若干枚挥萌，如何用最少的硬幣湊夠22元？求出最少硬幣數(shù)枉侧。

let dp = [1]

function MinRCIter(aim, faceValueArr) {
  if (aim < 0) { return 100000000 }
  if (aim === 0) { return 0 }

  if (dp[aim]) {
    return dp[aim]
  }

  let localMin = 100000000

  for (let i = 0; i < faceValueArr.length; i++) {
    if (aim === faceValueArr[i]) {
      return 1
    }

    let rest = MinRCIter(aim - faceValueArr[i], faceValueArr)
    localMin = Math.min(localMin, rest + 1)
  }

  dp[aim] = localMin
  return dp[aim]
}

function MinReplaceChange(aim, arr) {
  console.log('Least: ' + MinRCIter(aim, arr))
}

// 測(cè)試
MinReplaceChange(22, [1, 3, 5])
// 輸出
Least: 6

最長(zhǎng)遞增子序列（longest increasing subsequence）問(wèn)題
在一個(gè)給定的數(shù)值序列中引瀑，找到一個(gè)子序列，使得這個(gè)子序列元素的數(shù)值依次遞增榨馁，并且這個(gè)子序列的長(zhǎng)度盡可能地大憨栽。最長(zhǎng)遞增子序列中的元素在原序列中不一定是連續(xù)的。

給定一個(gè)長(zhǎng)度為n的數(shù)組a[0], a[1], a[2]..., a[n-1]辆影，找出一個(gè)最長(zhǎng)的單調(diào)遞增子序列（注：遞增的意思是對(duì)于任意的i < j徒像，都滿(mǎn)足a[i] < a[j]黍特，此外子序列的意思是不要求連續(xù)蛙讥，順序不亂即可）。
例如：給定一個(gè)長(zhǎng)度為6的數(shù)組: [5灭衷， 6次慢， 7， 1翔曲， 2迫像， 8]，則其最長(zhǎng)的單調(diào)遞增子序列為[5瞳遍，6闻妓，7，8]掠械，長(zhǎng)度為4由缆。

用dp[i]表示以i結(jié)尾的子序列中LIS的長(zhǎng)度。然后用dp[j] (0 <= j < i)來(lái)表示在i之前的LIS的長(zhǎng)度猾蒂。然后我們可以看到均唉，只有當(dāng)a[i] > a[j]的時(shí)候，我們需要進(jìn)行判斷肚菠，是否將a[i]加入到dp[j]當(dāng)中舔箭。

為了保證我們每次加入都是得到一個(gè)最優(yōu)的LIS，有兩點(diǎn)需要注意：（1）每一次蚊逢，a[i]都應(yīng)當(dāng)加入最大的那個(gè)dp[j]层扶，保證局部性質(zhì)最優(yōu)箫章，也就是我們需要找到max(dp[j] (0 <= j < i))；（2）每一次加入之后镜会，我們都應(yīng)當(dāng)更新dp[j]的值炉抒，顯然，dp[i] = dp[j] + 1稚叹。
如果寫(xiě)成遞推公式焰薄，我們可以得到dp[i] = max(dp[j] (0 <= j < i)) + (a[i] > a[j] ? 1 : 0)。

JavaScript實(shí)現(xiàn)
【時(shí)間復(fù)雜度：O(n ^ 2)】

let dp = [1]
let pre = [null]

function lisIter(endWith, listArr) {
  if (dp[endWith]) { 
    return dp[endWith] 
  }

  let localMaxLen = 1
  for (let i = 0; i < endWith; i++) {
    if (listArr[i] < listArr[endWith]) {
      if (localMaxLen < lisIter(i, listArr) + 1) {
        localMaxLen = lisIter(i, listArr) + 1
        pre[endWith] = i
      }
    }
  }
  
  dp[endWith] = localMaxLen
  return dp[endWith]
}


function LIS(arr) {
  for (let i = 0; i < arr.length; i++) {
    lisIter(i, arr)
  }

  let answer = -1
  let lastNode = -1
  for (let i = 0; i < dp.length; i++) {
    if (answer < dp[i]) {
      answer = dp[i]
      lastNode = i
    }
  }

  const seq = []
  do {
    seq.unshift(arr[lastNode])
    lastNode = pre[lastNode]
  } while(lastNode !== null)

  console.log('length: ' + answer)
  console.log('list: ' + seq)
}

// 測(cè)試
LIS([3, 5, 8, 2, 9, 10, 4])
// 輸出
length: 5
list: 3,5,8,9,10

斐波那契數(shù)列
詳見(jiàn)上一篇《斐波那契數(shù)列及其優(yōu)化》扒袖。

漢諾塔問(wèn)題
詳見(jiàn)《漢諾塔問(wèn)題》