現(xiàn)有2元、3元、5元共三種面額的貨幣，如果需要找零99元，一共有多少種找零的方式？
點(diǎn)評：
還有一個非常類似的題目：“一個小朋友走樓梯，一次可以走1個臺階、2個臺階或3個臺階，問走完10個臺階一共有多少種走法？”，
這兩個題目的思路是一樣，如果用遞歸函數(shù)來寫的話非常簡單。
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裝飾器裝飾了遞歸函數(shù)change_money，如果不做這個優(yōu)化，上面代碼的漸近時間復(fù)雜度將會是$O(3^N)$，而如果參數(shù)total的值是99，這個運(yùn)算量是非常巨大的。lru_cache裝飾器會緩存函數(shù)的執(zhí)行結(jié)果，這樣就可以減少重復(fù)運(yùn)算所造成的開銷，這是空間換時間的策略，也是動態(tài)規(guī)劃的編程思想。
京公網(wǎng)安備 11010802030320號