Kursusnya
Dynamic programming dan optimasi adalah kursus Coding tingkat lanjut dalam tujuh pelajaran, setelah Rekursi dan backtracking. Setiap pelajaran memakai Python biasa di Pi, dengan rakitan dua LED dari galeri dan modul lampu lalu lintas tempat sesuatu seharusnya menyala. Setiap langkah dicek lewat apa yang dicetak Pi atau apa yang dilakukan pin-nya, dan setiap angka dalam pelajaran adalah angka yang benar-benar dicetak program.
- Overlapping subproblems: a 16-rung docking ladder climbed 1, 2 or 3 rungs at a time. The slow recursion makes 37,921 calls and works out rung 2 3,136 times; a memo cuts it to 49 calls, a table fills it bottom up, and three rolling numbers climb 1000 rungs.
- Coin change: thruster burns of 9, 6, 5 and 1 m/s. Greedy uses three burns for 11 m/s where DP finds two (5 and 6), a pick table says which, a second table counts the 6 mixes, and reachability lists the speeds 4 and 7 m/s burns can never make.
- Knapsack: 10 kg kargo roket untuk sains terbanyak. Brute force atas 256 muatan, tabel knapsack 0/1, muatan yang dilacak mundur, versi satu baris dengan bug maju klasiknya, dan 30 peti diselesaikan dalam 3,030 sel.
- Jarak edit: perintah probe yang kacau. Mengapa menghitung posisi gagal, tabel Levenshtein dicetak penuh, edit yang dilacak mundur, dan baris perintah yang menjawab "did you mean DEPLOY?"
- Greedy vs DP: lintasan satelit berdasarkan akhir terawal (terbukti benar) lawan terpendek dulu (salah), bahan bakar terbagi lawan tangki utuh, dan pengecekan sistem koin mana yang bisa ditangani greedy.
- Penjadwalan: lintasan yang membawa jumlah data berbeda. Greedy mendapat 105 MB, DP dengan
bisectmendapat 120, jadwal dilacak mundur dan diputar di LED merah, dan sweep line menghitung antena. - Proyek: perencana rute: penutup.
Babak final
Perencana feri antara delapan stasiun luar angkasa. Waktu tercepat didapat dari DP dalam urutan stasiun (petanya hanya terbang ke luar, jadi ini directed acyclic graph): Bumi ke Titan 45 jam. Rutenya dilacak mundur dari came_from, tabel kedua menjawab rute terbaik dengan paling banyak k kaki (putaran Bellman-Ford, 49 jam dalam empat kaki), dan sebuah kios menerima tujuan lewat Serial Monitor dan menyalakan lampu lalu lintas: hijau untuk rute, merah untuk stasiun yang tidak ada.
Yang berbeda dari engine Pi
Pi menjalankan MicroPython 1.29, bukan CPython:
- Tidak ada numpy, jadi setiap tabel berupa list atau list of lists, dan memang begitulah DP biasanya diajarkan.
- Dict tidak menjaga urutan masuknya key. Perencana membaca dict-nya hanya berdasarkan key, dan semua yang dicetak berasal dari list.
- Rekursi berhenti mendekati 1.000 panggilan, jadi memo top-down tidak bisa mendaki tangga 1000 anak. Kursus ini memakai hal itu untuk menunjukkan mengapa tabel bottom-up penting.
str.rjusttidak ada, jadi tabel jarak edit meratakan angka dengan"%2d" % v.bisect,functoolsdan bilangan bulat besar bekerja seperti di CPython.