一道簡單的動態規劃,可以先寫出遞歸方程(注意到每一總票值都是由比它小的票值產生的),然后通過其求解。


用F[i]表示得到i面值所需要的最少郵票個數,Value[j](j=1..Stamps)表示每個郵票的面值,可得以下轉移方程:

F[i]=Min ( F[i-Value[j]] + 1 ) (i-Value[j]>=0 j=1..Stamps)
初始狀態:F[0]=0;F[i]=INFINITE;