[Algorithm Cheat Sheat] — 0/1 Knapsack Dynamic Programming

1. 0/1 Knapsack
2. Coin Change
3. Subset Sum

如果你也跟我一樣學不會DP，這是我整理的資料，供您快速有效的複習。

0/1 Knapsack

這是最簡單且順向之DP作法 :

(以下程式採1-indexing,input:w[1:N],v[1:N])

• 時間複雜度 O(N*W)
• 空間複雜度 O(N*W)
• W:背包重量

空間優化成1維陣列:

• 時間複雜度 O(N*W)
• 空間複雜度 O(N)

手算思維

個人認為若是要用手算0/1背包問題，我會建議使用1維陣列，以i=0持續迭代到i=W，以下舉一個例子（不使用小技巧的話可能要算半小時。）

Example .

W=16

1-index

首先先初始化dp[0:n](i=0)

之後依照核心程式碼 dp[j] >= w[i] ? max(dp[j-w[i]]+v[i] : dp[j])

整理出以下步驟 :

1. 先依照w[i]的值固定dp中i≤w[i]的表格(不會更改，因為拿不動)
2. 之後比較上一回合 max{ dp的左邊w[i]的值+v[i] , 正上方的dp表格v[i] }
3. 持續以上步驟直到 i = W

Start !!!

下圖顯示i=1的迭代情形，因為正上方的表格皆為1，故直接往下填寫即可。

w[1]=2，先固定左邊2格，每次與正上方表格還有左邊2格選大的

i=2以上，便需要比較dp[j]以及dp[j-w[i]]+v[i] (正上方vs左上w[i]格)

Tips:注意下界可加速運算
(i=2時，最後+6還會比較大在2的那格，因此這中間過程都可直接填寫14)

w[3]=5，先固定左邊5格，每次與正上方表格還有左邊5格選大的

i 迭代到快底時，可以利用其狀態轉移式減少計算量 :

（大致剩下3層可用此方法）

最後可獲得在i=7時，dp[16]=38 。

最真實的手算(醜爆我驕傲)

Coin Change Problem

Type-1

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example :

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

我們可以使用像是0/1背包的思維來解決這個問題 :

這題要紀錄的是 : 最少的硬幣數
因此 , 狀態轉移式要 keep的是最少的coin使用量
(與 0/1背包 keep的是最大價值略有不同)

同樣地，也可以重複使用該陣列壓縮成1D 陣列來節省額外空間使用量:

Subset Sum