确定将一定数量的钱比如100，换成1，2，5，10，20，50元的组合问题（2）
常用的递归解法package test;public class CoinToSum2 {private static final int[] COINS = new int[] { 1, 2, 5, 10, 20, 50 };private static final int SUM = 100;private static int cnt = 0;public static void main(String[] args) {System.out.println(System.currentTimeMillis());calc(0, 0, "");System.out.println("total " + cnt + " solutions. ");System.out.println(System.currentTimeMillis());// 110 ms}private static void calc(int sum, int coinIndex, String pre) {if (SUM == sum) {++cnt;}for (int i = coinIndex; i < COINS.length; i++) {if (SUM - sum >= 0) {calc(sum + COINS, i, pre + " " + COINS);}}}}这个消耗时间大概在110ms,比第1个逊色多了。。。而且代码晦涩难懂、不好理解
页:
[1]