Dynamic Programming di Python

Ini adalah salah satu materi yang ada di buku Pemrograman Kompetitif. Buku ini bisa di download di https://tlx.toki.id/courses/competitive/chapters/07/lessons/A. Seharusnya penjelasannya diketik ulang , tapi maaf belum sempat... 

Dalam buku dijelaskan konsep dan Pseudocode dari soal. Keduanya diterjemahkan dalam bahasa Python versi saya.

Soalnya seperti ini:

Diberikan M jenis koin, masing-masing jenis bernilai a₁,a₂, ....aₘ rupiah. Asumsikan banyaknya koin  yang ada tak terbatas. Tentukan banyaknya koin paling sedikit untuk membayar tepat sebesar N rupiah!

Solusinya bisa diselesaikan dalam dua cara: Bottom up dan Top down.

1. Bottom-up: (ubah variabel M dan N untuk mengubah input)

1. def solve(a, N):
2.     f = [0] * (N + 1)
3.     for x in range(1, N + 1):
4.         best = float('inf')
5.         for k in range(len(a)):
6.             if a[k] <= x:
7.                 best = min(best, f[x - a[k]] + 1)
8.         f[x] = best
9.     return f[-1]
10. 
    
11. def main():
12.     M = 1, 6, 10
13.     N = 12
14.     print(solve(M, N))
15. 
    
16. if __name__ == '__main__':
17.     main()

2. Top-down:

1. def solve(x):
2.     if x == 0: return 0
3. 
   
4.     best = float('inf')
5.     for k in range(len(M)):
6.         if M[k] <= x:
7.             best = min(best, solve(x - M[k]) + 1)
8.     return best
9. 
   
10. def main():
11.     global M
12.     M = 1000, 2000, 5000
13.     N = 12000
14.     print(solve(N))
15. 
    
16. if __name__ == '__main__':
17.     main()