[DP] 아이템 적절히 고르기 (은행, 배낭)

🧩 필요한 최소 동전의 수 (은행)

---

단, 1 ≤ j ≤ n이며, i ≥ coin[j]

⇨ i        : 지금까지 선택한 동전의 합

⇨ dp[i] : 필요한 최소 동전 수

 

 

 

 

 

🧩 배낭 문제 (Knapsack)

---

dp[ i ][ j ] : 가능한 보석 가치의 최대값

• i번째 보석까지 고려했고, 지금까지 선택한 보석 무게의 합은 j

⇨ i번째 보석을 가방에 넣었는지 / 넣지 않았는지 구분해 점화식