题目：有n种硬币，面值分别为V1,V2,…Vn,每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值！

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候) 

  首先我们思考一个问题，如何用最少的硬币凑够i元(i<11)？为什么要这么问呢？两个原因：1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

  好了，让我们从最小的i开始吧。当i=0，即我们需要多少个硬币来凑够0元。由于1，3，5都大于0，即没有比0小的币值，因此凑够0元我们最少需要0个硬币。这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。

  那么， 我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。当i=1时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够0元即可，而这个是已经知道答案的，即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。

当i=2时， 仍然只有面值为1的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2。

  一直到这里，你都可能会觉得，好无聊，感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币！耐心点，让我们看看i=3时的情况。当i=3时，我们能用的硬币就有两种了：1元的和3元的(5元的仍然没用，因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬币有两种，我就有两种方案。如果我拿了一个1元的硬币，我的目标就变为了:凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。这个方案说的是，我拿3个1元的硬币；第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1.

  这个方案说的是，我拿1个3元的硬币。好了，这两种方案哪种更优呢？ 记得我们可是要用最少的硬币数量来凑够3元的。所以， 选择d(3)=1，怎么来的呢？

  具体是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。

  上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的”状态”，这个状态是怎么找出来的呢？我在另一篇文章中写过：根据子问题定义状态。你找到子问题，状态也就浮出水面了。

  最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币。 那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)， 上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1,d(3-3)+1}。没错，它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下，d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;

  有了状态和状态转移方程，这个问题基本上也就解决了。

代码一：动规递归方式实现

#include<bits/stdc++.h>
using namespace std;
int n, s, i;
int d[1000],v[10];
int dp(int s)
{
int & ans=d[s];//声明一个引用ans
if (ans!= -1) return ans;
ans = -(1<<30);//设定不能走到终点的路肯定小于能走到终点的路
for (int i = 0;i < n;i++)
if (s >= v[i])//等号很关键
//根据公式：max{dp(s-v[i])+1},代码max(ans, dp(s – v[i])+1)中的ans记录的是上一个值
ans = max(ans, dp(s – v[i])+1);
return ans;
}

int main()
{

while (scanf(“%d%d”, &n, &s) != EOF)
{
for (i = 0;i < n;i++)
scanf(“%d”, &v[i]);
memset(d, -1, sizeof d);
d[0] = 0;//用于辨别该路能否走到终点
printf(“%d\n”, dp(s));
}
return 0;
}

思考：最小值怎么求？

 代码二：动规搜索优化

#include<bits/stdc++.h>
using namespace std;
int n, s, i;
int d[1000],vis[1000],v[10];
int dp(int s)
{
/*标记是否已访问过*/
if(vis[s])return d[s];
vis[s]=1;
int & ans=d[s];//声明一个引用ans
if (ans!= -1) return ans;
ans = -(1<<30);//设定不能走到终点的路肯定小于能走到终点的路
for (int i = 0;i < n;i++)
if (s >= v[i])//等号很关键
//根据公式：max{dp(s-v[i])+1},代码max(ans, dp(s – v[i])+1)中的ans记录的是上一个值
ans = max(ans, dp(s – v[i])+1);
return ans;
}

int main()
{

while (scanf(“%d%d”, &n, &s) != EOF)
{
for (i = 0;i < n;i++)
scanf(“%d”, &v[i]);
memset(vis,0,sizeof(vis));
memset(d, -1, sizeof d);
d[0] = 0;//用于辨别该路能否走到终点
printf(“%d\n”, dp(s));
}
return 0;
}

代码三：递推写法

#include<bits/stdc++.h>
#define INF (1<<30)
using namespace std;
int n, s, i;
int d[1000],v[10];
int minv[1000],maxv[1000];

int main()
{

while (scanf(“%d%d”, &n, &s) != EOF)
{
for (i = 1;i <=n;i++)
scanf(“%d”, &v[i]);
minv[0]=maxv[0]=0;
for(int 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]);
}
return 0;
}