Dynamic programming untuk koin minimum
Definisikan state dan isi tabel dari submasalah terkecil.
dasar #dynamic programming
Yang akan kamu pahami
Bangun recurrence dari pilihan terakhir dan urutan evaluasi yang aman.
Konsep inti
dp[x] adalah jumlah koin minimum untuk membentuk x. Set dp[0]=0. Untuk setiap koin positif c yang tidak melebihi x, pertimbangkan 1 + dp[x−c] bila terjangkau. Isi x dari kecil ke besar.
Coba langkahnya
Koin tak terbatas bernilai 1, 3, 4. Bentuk nilai 6.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| dp[x] | 0 | 1 | 2 | 1 | 1 | 2 | · |
| Koin terakhir | · | · | · | · | · | · | · |
| 1 + dp[x−c] | · | · | · | · | · | · | · |