跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 14.8 練習

## 14.8.1 知識鞏固

### 1. 什麼時候適合使用動態規劃

一位同學說：“只要能寫出遞推式，就應該使用動態規劃。” 請判斷下面三個任務分別更適合使用動態規劃、回溯，還是使用迴圈或數學公式而不建立 `dp` 表，並寫出一個關鍵理由。

1. 使用面值 `[1, 3, 4]` 的硬幣湊出金額 6，求最少硬幣數，每種硬幣可重複使用；
2. 輸出 `[1, 2, 3]` 的全部排列；

3. 計算 \(1 + 2 + \dots + n\)。

   對於你判斷為適合動態規劃的任務，再說明 `dp[i]` 表示什麼。

參考答案

1. 適合動態規劃。令 `dp[i]` 表示湊出金額 `i` 所需的最少硬幣數。 對於每枚不超過 `i` 的硬幣 `c`，都可以把 `dp[i-c] + 1` 作為候選答案， 再從這些候選值中取最小值。不同選擇會反覆遇到同一金額，較大金額的最優解也能由較小金額的最優解構成。 金額 6 的答案是 2，即 `3 + 3`。

2. 應使用回溯。題目要求逐個生成全部 6 個排列，回溯可以系統地嘗試一個選擇、繼續搜尋， 再撤銷選擇並嘗試其他分支。無論採用什麼方法，實際輸出這些排列時都不能跳過列舉。

3. 使用迴圈或等差數列公式即可。雖然能寫出 `S(i) = S(i-1) + i`，但計算 `S(i)` 時只依賴一個更小的 `S(i-1)`， 每個部分和只需計算一次，不存在重複子問題，因此無需建立 `dp` 表。“能寫遞推式”不等於“需要動態規劃”。

### 2. 背包表中的一個格子怎麼算

0-1 背包：物品重量 `wgt = [1, 2, 3]` ，價值 `val = [5, 11, 15]` ，背包容量 4 。 `dp[i][c]` 表示只考慮前 \(i\) 件物品、背包容量上限為 \(c\) 時，能夠取得的最大價值； 不要求恰好裝滿背包。

現在只計算狀態 `dp[3][4]`。已知 `dp[2][4] = 16`、`dp[2][1] = 5`：

1. 不選第 3 件物品時，候選價值是多少？
2. 選擇第 3 件物品時，還剩多少容量，候選價值是多少？
3. `dp[3][4]` 應取多少？對應選擇了哪些物品？

參考答案

1. 不選第 3 件物品時，沿用前兩件物品的結果，候選價值為 `dp[2][4] = 16`。

2. 第 3 件物品重量為 3，放入後還剩容量 \(4-3=1\)；候選價值為 `dp[2][1] + 15 = 5 + 15 = 20`。

3. 比較 16 和 20，得到 `dp[3][4] = 20`。它對應選擇第 1、3 件物品， 總重量為 \(1+3=4\)，總價值為 \(5+15=20\)。

   這個狀態的計算體現了 0-1 背包的一次“選或不選”比較。

### 3. 背包容量應該按什麼順序更新

一個 0-1 背包只有一件物品：重量為 2，價值為 5；背包容量為 4。 每件物品最多選擇一次，初始一維陣列為 `dp = [0, 0, 0, 0, 0]`。

一位同學在處理這件物品時，按容量從 2 到 4 更新：

- 更新 `dp[2]` 後得到 5；
- 更新 `dp[3]` 後也得到 5；
- 更新 `dp[4]` 時又使用剛得到的 `dp[2]`，於是得到 `dp[4] = 10`。

1. `dp[4] = 10` 這個結果是否正確？為什麼？
2. 根據“每件物品最多選擇一次”的條件，`dp[4]` 應為多少？
3. 處理每件物品時，容量應從大到小還是從小到大更新？這樣做避免了什麼問題？

參考答案

1. 這個結果不正確。價值 10 相當於把這件價值為 5 的物品放入了兩次， 違反了“每件物品最多選擇一次”的條件。

2. 背包中最多隻能放入這一件物品，所以正確的 `dp[4]` 為 5。

3. 容量應從大到小更新，即依次處理 4、3、2。 這樣在計算 `dp[c]` 時，所讀取的 `dp[c-2]` 仍是處理當前物品之前的結果， 不會在同一輪中重複使用當前物品。

## 14.8.2 程式設計練習

### 1. 爬樓梯的方案數

一段樓梯共有 `n` 階。你每次只能向上走 1 階或 2 階，且必須恰好到達第 `n` 階。 請計算共有多少種不同的走法。規定 `n >= 1`，走法只按每一步走 1 階還是 2 階來區分。 請使用一維動態規劃陣列完成，暫不使用只保留兩個狀態的空間最佳化寫法。

解題提示

1. 到達第 i 階的最後一步，只可能跨 1 階或 2 階
2. 因此有 dp[i] = dp[i-1] + dp[i-2]
3. 先處理 n 為 1 和 2 的情況，再從第 3 階開始填表

LeetCode 題目解析

> 說明： 題解講解了一維 dp 狀態和轉移，但給出的程式碼採用滾動變數壓縮空間；本練習要求先實現一維 dp 表，滾動變數僅作為選做最佳化

### 2. 0-1 背包

給定等長陣列 `wgt` 和 `val`，第 `i` 件物品的重量為正整數 `wgt[i]`、價值為非負整數 `val[i]`， 背包容量 `cap` 為非負整數。每件物品最多選擇一次，請在總重量不超過 `cap` 的條件下， 求能夠裝入背包的最大總價值。請使用一維動態規劃實現。

解題提示

1. 初始化長度為 cap + 1 的陣列 dp，其中 dp[c] 表示容量上限為 c 時的最大價值
2. 處理物品 i 時，比較“不選它”的 dp[c] 與“選它”的 dp[c-wgt[i]] + val[i]
3. 容量必須從大到小更新，避免在同一輪中重複選擇當前物品

##### 歡迎在評論區留下你的見解、問題或建議