关于一些基础的dp——硬币的那些事（dp的基本引入）

1.最少硬币问题大体题意：

有n种硬币，面值分别是v1,v2......vn，数量无限，输入一个非负整数s，选用硬币使其和为s，要求输出最少的硬币组合。

我们可以这样分析：

定义一个名为Min[s]的数组来表示是金额s所对应的最少硬币的组合，所以对我们来说，只要是在程序中查到Min[i]的大小就可以知道最少的硬币组合是多少了。

以面值为{1，5，10，25，50}为例子来讲一下，方便以后备赛。

假如我们输入的s是100，当全用1coin的时候，如图：(画的很拙劣，抱歉）

那么第一个格子里指的就是当金额为0的时候所需要的硬币数是0，那当金额为1的时候Min[1]=Min[1-1]+1，以此类推,当然，这是只使用硬币面值为1的时候。

当我们加入了面值5，就变成了这样子：

我们可以看到，到了5的时候，选择就变成了两种——一个是5个1元的硬币，另一个是直接一个5元的硬币，可以这么理解：

Min[5]=min(Min[5],Min[5-5]+1),这样才能保证硬币数是最小的。

我们还有其他面值的硬币，当然也要一一的引入。

所以说，我们在dp中将Min[i]这种记录问题最优解的数据叫做“状态”，从Min【i-1】，Min【i-5】这种式子叫做状态转移，在问题中，我们可以清晰的看见动态规划往往是利用问题前面的状态，也就是利用子问题的关联性去解决问题，这是dp的一大特点。

本题题解如下：

#include<bits/stdc++.h>
 using namespace std;
 int Min[251];//每个金额所对应的最少的硬币数 
 int coin[5]={1,5,10,25,50};//5种金额 
 int Min_path[251]={0}; 
 void ans()
 {
     for(register int k=0;k<251;k++)
     Min[k]=INT_MAX;//定义初始值是无穷大 
     Min[0]=0;
     for(register int j=0;j<5;j++)
     
         for(register int i=coin[j];i<251;i++)
         {
             Min_path[i]=coin[j];
             Min[i]=min(Min[i],Min[i-coin[j]]+1);
        }
} 
/*void print_ans(int *coin_path,int s)//打印组合 
{
    while(s)
    {
        cout<<Min_path[s]<<' ';
        s=s-Min_path[s];
    }
}*/
 int main()
{
    ios::sync_with_stdio(false);
    int s;
    ans();//打表 
    cin>>s;
    cout<<Min[s]<<endl;
    //print_ans(Min_path,s);
     return 0;
} 

但是对于所有硬币问题，就不能这么解了。

2.所有硬币问题大体题意如下（HDUOJ2069，但是HDUOJ进不去了）：

有n种硬币，面值依旧是前面那些巴拉巴拉，到最后就不一样了，要求输出所有硬币组合。

我们这一局采用dp来解，用dp[i][j]来表示当金额为i的时候最少需要j枚硬币。

dp[0][0]是0，那dp[1][1]就是dp[1-1][1-1]+1,画图表示一下：

那我们可以一次类推dp[i][j]=min(dp[i][j],dp[i-coin[k]][j-1]

可以看到，dp[i][j]纵坐标的结果相加就是最少硬币的组合。

代码如下：

#include<bits/stdc++.h>
 using namespace std;
 int ans[251]; 
 int coin[5]={1,5,10,25,50};
 int dp[251][101];
 void solve()
 {
     dp[0][0]=1;//0元0个硬币算是一种方案 
     for(int i=0;i<5;i++)
     {
         for(int j=1;j<101;j++)//硬币数不超过100 
         {
             for(int k=coin[i];k<251;k++)
             {
                 dp[k][j]+=dp[k-coin[i]][j-1];
            }
        }
    }
 }
 int main()
 {
     int s;
     solve();
    cin>>s; 
    for(int i=0;i<251;i++)
    {
        for(int j=0;j<101;j++)
        {
            ans[i]+=dp[i][j];
        }
    }
    cout<<ans[s]<<endl;
 }

 

这就是基础的dp引入，硬币问题就解决了。

sdutoj

有一个最少硬币问题：https://acm.sdut.edu.cn/onlinejudge3/problems/1725?from=%2Fsets%2F17

但这个就不是dp的简单引入了，这个属于多重背包啦~~~