問(wèn)題描述

There are four types of common coins in US currency:
quarters (25 cents)
dimes (10 cents)
nickels (5 cents)
pennies (1 cent)

There are 6 ways to make change for 15 cents:
A dime and a nickel;
A dime and 5 pennies;
3 nickels;
2 nickels and 5 pennies;
A nickel and 10 pennies;
15 pennies.

How many ways are there to make change for a dollar
using these common coins? (1 dollar = 100 cents).

問(wèn)題說(shuō)明

1 dollar = 100 cents 创泄，現(xiàn)在有一美元需要兌換零錢蜂林。上面說(shuō)明有四種單位， quarters (25 cents) dimes (10 cents) nickels (5 cents) pennies (1 cent)想诅。 可以參看上面15 cents 有6種兌換方案窃蹋。需要計(jì)算 1dollar 一共有多少種兌換方案 蒜危。
兌換方案舉例：
100pennies 是一種
2 quarters + 50pennies 是一種

看到這道題后總是逃不過(guò)原來(lái)的習(xí)慣---想典尾，一定要全部想明白了再做墨技。結(jié)果導(dǎo)致想了半天惩阶，也沒(méi)有開(kāi)始做】弁簦看起B(yǎng)ob Deng 說(shuō)的沒(méi)錯(cuò)琳猫，需要每天一小時(shí)。TDD是需要刻意訓(xùn)練的私痹。

測(cè)試用例

import static org.junit.Assert.assertEquals;

public class CountCoinsTest {
    int[] coins = {25,10,5,1};
    @Test
    public void should_0_0(){
        int count = CountCoins.makeChange(0);
        assertEquals(0,count);
    }

    @Test
    public void should_2_5(){
        int count = CountCoins.makeChange(5);
        assertEquals(2,count);
    }
    @Test
    public void should_6_15(){
        int count = CountCoins.makeChange(15);
        assertEquals(6,count);
    }
    @Test
    public void should_13_25(){
        int count = CountCoins.makeChange(25);
        assertEquals(13,count);
    }

    @Test
    public void should_18_30(){
        int count = CountCoins.makeChange(30);
        assertEquals(18,count);
    }
    @Test
    public void should_242_100(){
        int count = CountCoins.makeChange(100);
        assertEquals(242,count);
    }

   
}

實(shí)現(xiàn)類

public class CountCoins {

    public static int makeChange(int amount) {
        int ways = 0;
        if (amount < 1) return 0;
        for (int quarters = 0; quarters <= amount; quarters += 25) {
            for (int dimes = 0; dimes <= amount; dimes += 10) {
                for (int nickels = 0; nickels <= amount; nickels += 5) {

                    int pennies = amount - quarters - dimes - nickels;
                    if (pennies < 0) break;
//                    System.out.println(quarters + "  " + dimes + "  " + nickels + " " + pennies);
                    ways++;

//                    for (int pennies = 0; pennies <= amount; pennies++) {
//
//                        if (quarters + dimes + nickels + pennies == amount) {
//                            System.out.println(quarters + "  " + dimes + "  " + nickels + " " + pennies);
//                            ways++;
//                            break;
//                        }
//                    }
                }
            }
        }

        return ways;
    }
}

以上是對(duì)該題的一種簡(jiǎn)單的實(shí)現(xiàn)方法脐嫂，比較直觀。也可以參考武可寫的紊遵，遠(yuǎn)程異步結(jié)對(duì) - Count Coins 可以對(duì)本題以及TDD有更好的認(rèn)識(shí)账千。