硬币凑法

硬币凑法"/>

硬币凑法

我们有8种不同面值的硬币

/*

• 假设我们有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分三种硬币，组成已一角/共有多少解法
• 3150 给出 1 5 10 25 有多少种方法
  */

package _7递归;public class c硬币表示 {
public static void main(String[] args) {int res=countWays(15);System.out.println(res);
}public static int countWays(int n) {//输入面值if(n<=0) {//如果小于零return 0;}//定义总价    数组面值        下标return countWaysCore(n,new int[] {1,2,5,10,20,50,100,200},7);}//代入private static int countWaysCore(int n,int[]coins,int cur) {if(cur==0) {return 1;}int res=0;//要么不选， 可以选1 2  3 4 for(int i=0;i*coins[cur]<=n;i++) {//100 25 *4 iint shenyu=n-i*coins[cur];//取大的多少个res+=countWaysCore(shenyu,coins,cur-1);//递归+}return res;  }
}