动态规划（四）——所有硬币问题

一、所有硬币问题

3.1硬币数量不限制

有n种硬币，面值为v1，v2……vn，数量无限。输入非负整数s，选用硬币，使其和为s，输出所有可能的硬币组合数量。

定义一个记录状态的数组int dp[]，dp[i]表示金额i所对应的组合方案数。需要找到dp[i]和dp[i-1]的递推关系。

同样是用1,5,10,25,50五种面值的硬币：

1. 第一步：只用1分硬币。
   dp[0] = 1设为初始值，其余为0。
   dp[1] = dp[1]+dp[0] = 0+1。
   对于其他dp[i]也有dp[i] = dp[i]+dp[i-1]，这称为状态转移方程。
   2. 第二步：加上5分硬币。
      i>=5时，dp[i] = dp[i]+dp[i-5]
   3. 第三步：继续处理其他面值硬币的情况。
      同理有dp[i] = dp[i]+dp[i-10]，dp[i] = dp[i]+dp[i-25]，dp[i] = dp[i]+dp[i-50]

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const int money = 200;    //定义最大金额
const int num = 5;        //五个硬币
int type[num] = {1,5,10,25,50};        //五种面值
int dp[money];

void solve() {
  dp[0] = 1;
  for (int i = 0; i < num; i++) {
    for (int j = type[i]; j < money; j++) {
      dp[j] = dp[j]+dp[j-type[i]];
    }
  }
}
int main() {
  fio
  int s;
  solve();
  while (cin >> s) {
    cout << dp[s] << endl;
  }
}

3.2硬币数量限制

HDOJ2069-硬币找零

问题描述
假设有5种硬币：50美分，25美分，10美分，5美分和1美分。我们希望以给定的金额使用这些硬币进行更改。

例如，如果我们有11美分，则可以用一枚10美分硬币和一枚1美分硬币，或两枚5美分硬币和一枚1美分硬币，或一枚5美分硬币和六枚1美分硬币进行组合或11个1分硬币。因此，使用上述硬币，有四种方法可以组合11分钱。

编写一个程序，以查找以美分计的任何金额进行组合的不同方式的总数，硬币数量num<=100。

输入项
输入文件包含任意数量的行，每行包含一个数字（≤250），以分币为单位。

输出量
对于每条输入线，输出一条线，其中包含使用上述5种硬币进行更改的不同方式的数量。

样本输入

11
26

样本输出

4
13

这道题要求硬币不能多于100个，因此我们可以建立一个转移矩阵，定义状态为dp[i][j]。其中横向是金额（i<=250），纵向是硬币数（j<=100）。

1. 第一步：只用一分硬币。
   type[5] = {1,5,10,25,50}
   初始化dp[0][0] = 1，其他为0，从dp[0][0]推导后面的状态。
   例如dp[1][1]是dp[0][0]进行金额+1、硬币数量+1后的状态转移，状态转移后组合方案数量不变，即dp[0][0] = dp[1][1] = 1。
   dp[1][1] = dp[1][1]+dp[0][0]= dp[1][1]+dp[1-1][1-1]
   =>
   dp[1][1] = dp[1][1]+dp[1-type[0]][1-1]
   => dp[i][j] = dp[i][j]+dp[1-type[0] ][j-1]
   对所有dp[i][j]执行如上操作，看图可观察到红色剪头的规律。
   2. 第二步：加上五分硬币。
      当i>=5时，dp[i][j] = dp[i][j]+dp[i-5][j-1]。
      dp[i][j] = dp[i][j]+dp[i-type[1]][j-1]。
      
2. 第三步：处理其他面值的硬币
   dp[i][j] = dp[i][j] + dp[i-type[k]][j-1]，k=2，3，4

矩阵元素dp[i][j]的含义是用j个硬币实现金额i的方案数量。
例如表中dp[6][6]=1，表示用6个硬币凑出6分钱，只有一种方案，即6个1分钱，表中空格即0表示没有方案。
该表中纵坐标相加，就是某金额对应的方案总数。

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const int coin = 101;
const int money = 251;    //定义最大金额
const int num = 5;        //五个硬币
int type[num] = {1,5,10,25,50};        //五种面值
int dp[money][coin];

void solve() {
  dp[0][0] = 1;
  for (int i = 0; i < num; i++) {
    for (int j = 1; j < coin; j++) {
      for (int k = type[i]; k < money; k++) {
        dp[k][j] += dp[k-type[i]][j-1];
      }
    }

  }
}

int main() {
  fio
  int ans[money] = {0};
  int s;
  solve();
  for (int i = 0; i < money; i++) 
    for (int j = 0; j < coin; j++)
      ans[i] += dp[i][j];
  while (cin >> s) {
    cout << ans[s] << endl;
  }
}