本文默認讀者具有動態(tài)規(guī)劃前置知識

• 動態(tài)規(guī)劃的特點：

1. 重疊子問題
2. 狀態(tài)轉(zhuǎn)移方程
3. 最優(yōu)子結(jié)構(gòu)

• 題型：求最值
• 解題套路：

1. 明確【狀態(tài)】
2. 明確【選擇】
3. 明確dp函數(shù)/數(shù)據(jù)的定義
4. 明確base case

• 例：給你一個可裝載容量為W的背包和N個物品，每個物品有重量和價值兩個屬性。其中第i個物品的重量為wt[i]，價值為va[i]，現(xiàn)在讓你用這個背包裝物品，最多能裝的價值是多少?
• 在這里將問題具體化：現(xiàn)在有4 (N=4)個物品，背包總?cè)萘繛?strong>8 (W=8),背包最多能裝入價值為多少的物品?

• 第一步，明確狀態(tài)和選擇

• 狀態(tài)：背包的空余容量剩多少；可選擇的物品還有哪些

• 選擇：把這個物品裝進背包；把這個物品裝進背包

• 第二步，明確dp數(shù)組的定義：對于前1個物品，當(dāng)背包的容量為w時，可以裝的最大價值是 dp[i][w]

• 比如說，dp[4][8]=10的含義為:
  對于給定的一系列物品中，若只對前4個物品進行選擇，當(dāng)背包容量為8時，最多可以裝下的價值為10。

• 根據(jù)此定義，還可得出:base case為dp[0][…] = dp[…][0] =0（編號為0，不裝物品；容量為0，裝不下任何物體），我們想計算的結(jié)果是 dp[N][W]
  

• 背包容量為1，物品編號可選為1，通過上表可知，物品編號為1時物品體積為2，所以此時選擇不裝任何物品。

• 背包容量為2，物品編號可選為1，裝入則價值為3。依次往后填充該行。

• 背包容量為3，物品編號可選為1、2時，裝入編號為2的物品，此時價值為4。

• 背包容量為5，物品編號可選為1、2時，裝入編號為1和2的物品，此時價值為7。

• 依次往后填充完該表格
  

• 第三步，根據(jù)[選擇]寫出狀態(tài)轉(zhuǎn)移邏輯：在w的約束下，把物品i裝進背包,最大價值是多少；在w的約束下，不把物品i裝進背包，最大價值是多少?文章來源地址http://www.zghlxwxcb.cn/news/detail-853298.html

for(let i=1;i<=n;i++) {
    for(let v=w[i]; v<=c;v++) {
      dp[i][v] = Math.max(dp[i-1][v], dp[i-1][v-w[i]]+value[i])
    }
}

• 背包問題完整求解代碼：

// 入?yún)⑹俏锲返膫€數(shù)和背包的容量上限，以及物品的重量和價值數(shù)組
function knapsack(n, c, w, value) {
    // dp是動態(tài)規(guī)劃的狀態(tài)保存數(shù)組
    const dp = (new Array(c+1)).fill(0)  
    // res 用來記錄所有組合方案中的最大值
    let res = -Infinity
    for(let i=1;i<=n;i++) {
        for(let v=c;v>=w[i];v--) {
            // 寫出狀態(tài)轉(zhuǎn)移方程
            dp[v] = Math.max(dp[v], dp[v-w[i]] + value[i])
            // 即時更新最大值
            if(dp[v] > res) {
                res = dp[v]
            }
        }
    }
    return res
}

• 擴展 – 最長上升子序列模型

題目描述：給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。

• 代碼實現(xiàn)

/**
 * @param {number[]} nums
 * @return {number}
 */
// 入?yún)⑹且粋€數(shù)字序列
const lengthOfLIS = function(nums) {
  // 緩存序列的長度
  const len = nums.length  
  // 處理邊界條件
  if(!len) {
      return 0
  }
  // 初始化數(shù)組里面每一個索引位的狀態(tài)值
  const dp = (new Array(len)).fill(1)
  // 初始化最大上升子序列的長度為1
  let maxLen = 1 
  // 從第2個元素開始，遍歷整個數(shù)組
  for(let i=1;i<len;i++) {
      // 每遍歷一個新元素，都要“回頭看”，看看能不能延長原有的上升子序列
      for(let j=0;j<i;j++) {  
          // 若遇到了一個比當(dāng)前元素小的值，則意味著遇到了一個可以延長的上升子序列，故更新當(dāng)前元素索引位對應(yīng)的狀態(tài)
          if(nums[j]<nums[i]) {
              dp[i] = Math.max(dp[i], dp[j] + 1)  
          }
      }
      // 及時更新上升子序列長度的最大值
      if(dp[i] > maxLen) {
          maxLen = dp[i]
      }
  }
  // 遍歷完畢，最后到手的就是最大上升子序列的長度
  return maxLen
};

到了這里，關(guān)于動態(tài)規(guī)劃（01背包問題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！