Dinamik programlama korkutucu bir isim taşıyan basit bir fikirdir: bir alt problemi bir kez çöz, cevabını yaz, sonra hep oradan oku. Merdiveni 1 ya da 2 basamak atarak çıkmanın kaç yolu var? n'inci basamağa ya bir önceki basamaktan ya iki öncekinden gelirsin; yollar toplanır.
ways = [0] * (n + 1)ways[0] = 1ways[1] = 1for step in range(2, n + 1):ways[step] = ways[step - 1] + ways[step - 2]return ways[n]
ways[0] = 1 tuhaf görünür ama doğrudur: hiç basamak çıkmamanın tek bir yolu vardır, o da yerinde durmak.Her DP çözümü üç soruya verilmiş cevaptır. Tablonun bir kutusu ne anlama geliyor? Bir kutu, daha küçük kutulardan nasıl hesaplanıyor? En küçük kutuların değeri ne? Kod yazmadan önce bu üçünü cümleyle söyleyebilmelisin.