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