14.8   練習¶

14.8.1   知識鞏固¶

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

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

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

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

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

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] 應取多少？對應選擇了哪些物品？

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. 處理每件物品時，容量應從大到小還是從小到大更新？這樣做避免了什麼問題？

14.8.2   程式設計練習¶

1.   爬樓梯的方案數¶

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

LeetCode 題目解析

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

2.   0-1 背包¶

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

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