一道简单的动态规划,可以先写出递归方程(注意到每一总票值都是由比它小的票值产生的),然后通过其求解。


用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;