/* * 假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝， * 用这些硬币组合够成一个给定的数值n。例如n=200，那么一种可能的组合 * 方式为 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100. * 问总共有多少种可能的组合方式？ * 2、华为面试题 * 1分2分5分三种硬币，组成已一角/共有多少解法 * 3.cc150 给出 1 5 10 25 有多少种方法 * * 思路: 1、输入总价，返回一个函数包含(总价，数组，最大的下标) * 2、判断下标是否等于0 则返回1 * 3、定义有有多少种解法 进行一个for循环 */
此问题简单的来想，可以有明确的递推关系。我们可以选择用递归来做。（首先讲递推，递归在后面）
思路：
假定现已给定四种面值，给定n。
我们可以对于每种面值的硬币，从大到小，选择要或者不要。
如果要剩下多少，如果不要剩下多少，将剩下的钱进行下一次递归，同时换一种面值的硬币。
这样就可以算出各种情况下要凑齐n所需的解法。
- 如果要凑的n为0，那么无论用那种面值，都是一种解法
- 如果用的面值为1，无论n为多少，都是一种凑法
- 当n小于5时，无论用多少种面值（1必须要），都是一种凑法
下图为每种n对应的用不同硬币的凑法，四行从上到下对应1，5，10，25面值，每一列为从1到n。具体的解释都在代码注释里。
#include<stdio.h> #include<string.h> //#include<iostream> //using namespace std; const int coins[4] = {1, 5, 10, 25}; int main(){ int n; scanf("%d",&n); const int N = n; int a[4][N+1]; memset(a,0,sizeof(a)); for(int i = 0; i < 4; i++) a[i][0] = 1; //面值为0的凑出来的部分，初始化为1 for(int i = 0; i <= n; i++) a[0][i] = 1; //用面值为1凑出来的都初始化为1 for(int i = 1; i < 4; i++){ // 硬币的种类 for(int j = 1; j <= n; j++){ // 总金额 for(int k = 0; k*coins[i] <= j; k++){// 在选择k个当前最大面值的硬币情况下的种类数 a[i][j] += a[i-1][j-k*coins[i]]; // x+y+z+1（在选择了k个当前面值的情况下，剩余的总金额的解法） } } } // for(int i = 0; i < 4; i++){ // for(int j = 0; j <= n; j++){ // cout << a[i][j] << " "; // } // cout << endl; // } printf("%d\n",a[3][n]); return 0; }
由这个思路，我们可以利用递归，减小因开辟二维数组带来的空间开销。
对于当前的状态，我们都可以转化为是否要当前面值、要几张的解法，加上是否要下一个面值……一直到最后。
#include<stdio.h> const int coins[4] = {1, 5, 10, 25}; int countWaysCore(int n, int cur){ //n表示输入的要凑的数，cur为coins的下标，用于递归时选择当前面值 //cur每次递归递减，出口条件为cur=0 if(cur == 0) return 1; //如果cur=0，只有一种凑法 int res = 0; //如果不是0，用res记录要返回的结果 for(int i = 0; i*coins[cur] <= n; i++){ //此循环表示是否选当前面值的硬币，选几张。 int left = n-i*coins[cur]; //left表示剩余的n，用于下一次递归 res += countWaysCore(left,cur-1); //res记录当前解法，递归完所有层，res迭代为总解法 } return res; } int countWays(int n){ if(n <= 0) return 0; return countWaysCore(n,3); } int main(){ int n; while(~scanf("%d",&n)){ printf("%d\n",countWays(n)); } return 0; }
