有n种硬币，面值分比为v1，v2，……vn，每种有无限多。给定非负整数S,可以选用多少个硬币，是面值之和恰好为S？输出硬币数目的最小值和最大值。1<=n<=100,0<=S<=10000,1<=vi<=S.

分析：此问题尽管看上去和嵌套矩形问题很不一样，但本题的本质也是DAG上的路径问题。将每种面值看做一个点，表示“还需要凑足的面值”，则初始状态为S，目标状态为0，若当前在状态i，每使用一个硬币j，状态便转移到i-vj。

 这个模型和嵌套矩形类似，但是还有一些明显的不同之处：那题并没有确定路径的起点和终点（可以把任意矩形放在第一个和最后一个），而本题的起点必须为S,终点必须为0，点固定后的“最短路”才是有意义的。在那道题中，最短序列显然是空（如果不允许空，就是单个矩形，不管怎样都是平凡的），而本题的最短路确实不容易确定的。

 本题要求最小最大两个值，记忆化搜索就必须写两个，在这种情况下，用递推更加方便（此时需要注意递推的顺序）

minv[0]=maxv[0]=0;
for(itn i=1;i<=S;i++){
    minv[i]=inf;maxv[i]=-inf;
}
for(int i=1;i<=S;i++)
    for(int j=1;j<=n;j++)
{
    if(i>v[j]){
        minv[i]=min(minv[i],minv[i-v[j]]+1);
        maxv[i]=max(maxv[i],maxv[i-v[j]]+1);
    }
}
printf("%d %d\n",minv[S],maxv[S]);

如何输出字典序最小的方案？嵌套矩形的方法依然使用，如下：

void print_ans(int *d,int S)
{
    for(int i=1;i<=n;i++)
    {
        printf("%d ",i);
        print_ans(d,S-v[i]);
        break;
    }
}
然后分别调用print_ans(min,S)和print_ans(max,S)即可。输出路径和嵌套矩形的区别是，那题打印的是路径上的点，而这里打印的是路径上的边。