考慮下面的貨幣兌付問題:在面值為(v1,v2,…,vn)的n種貨幣中,需要支付y值的貨幣,應(yīng)如何支付才能使貨幣支付的張數(shù)最少,即滿足,且使最小(xi是非負(fù)整數(shù))。設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法求解貨幣兌付問題,并分析時(shí)間性能和空間性能。
Ackermann函數(shù)A(m,n)的遞歸定義如下: 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法計(jì)算A(m,n),要求算法的空間復(fù)雜性為O(m)。