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