一、题目

二、思路

三、代码

package redbook3;import java.util.Arrays;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int[] coins;        while (in.hasNext()) {            int n = in.nextInt();            coins = new int[n];            for (int i = 0; i < n; i++) {                coins[i] = in.nextInt();            }            int total = in.nextInt();            System.out.println(coinChange(coins, total));        }        in.close();    }    public static int coinChange(int[] coins, int amount) {        int[] dp = new int[amount + 1];        Arrays.fill(dp, amount + 1);        dp[0] = 0;        for (int i = 1; i <= amount; i++) {            for (int coin : coins) {                if (i >= coin) {                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);                }            }        }        return dp[amount] >= amount + 1 ? -1 : dp[amount];    }    }

---------------------------------------------

参考链接：

http://blog.csdn.net/wunengbiao/article/details/78127841