現有2元、3元、5元共三種面額的貨幣，如果需要找零99元，一共有多少種找零的方式？
點評：
還有一個非常類似的題目：“一個小朋友走樓梯，一次可以走1個臺階、2個臺階或3個臺階，問走完10個臺階一共有多少種走法？”，
這兩個題目的思路是一樣，如果用遞歸函數來寫的話非常簡單。
from functools import lru_cache @lru_cache() def change_money(total): if total == 0: return 1 if total < 0: return 0 return change_money(total - 2) + change_money(total - 3) + \ change_money(total - 5)
說明：在上面的代碼中，我們用 lru_cache裝飾器裝飾了遞歸函數change_money，如果不做這個優化，上面代碼的漸近時間復雜度將會是$O(3^N)$，而如果參數total的值是99，這個運算量是非常巨大的。lru_cache裝飾器會緩存函數的執行結果，這樣就可以減少重復運算所造成的開銷，這是空間換時間的策略，也是動態規劃的編程思想。
京公網安備 11010802030320號