코테/알고리즘
[DP] 아이템 적절히 고르기 (은행, 배낭)
imname1am
2023. 9. 15. 16:30
반응형
🧩 필요한 최소 동전의 수 (은행)
⇨ i : 지금까지 선택한 동전의 합
⇨ dp[i] : 필요한 최소 동전 수
🧩 배낭 문제 (Knapsack)
dp[ i ][ j ] : 가능한 보석 가치의 최대값
• i번째 보석까지 고려했고, 지금까지 선택한 보석 무게의 합은 j
⇨ i번째 보석을 가방에 넣었는지 / 넣지 않았는지 구분해 점화식
반응형