动态规划：零钱兑换
一.给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算是否可以凑成总金额。如果可以组成总金额，返回1，不能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出：1
示例 2:
输入: coins = [ 2, 5], amount = 3
输出：-1
解题思路：
1.F(S)表示，是否能组成金额S。
2.若能组成，F(S) = 1；不能组成，F(S) = -1；F(0) = 0。
3.可推出关系式：F(S) = F(S-C)，C为coins数组里面的硬币面值。
4.新建一个数组，保存已经计算过的值，避免重复计算。
示例：
int[] coins = {1,2,5};amount = 11
F(11) = F(11-1) = F(11-2) = F(11-5)
F(10) = F(10-1) = F(10-2) = F(10-5)
.....
硬币兑换.jpg
/**
* 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算是否可以凑成凑成总金额
* 如果没有任何一种硬币组合能组成总金额，返回 -1。
*
*/
public class CoinChange17 {
public static void main(String[] args) {
int[] coins = {2,5};
int amount = 3;
System.out.println(coinChange(coins,amount,new int[amount+1]));
}
/**
*
* @param coins 硬币数组
* @param amount 兑换金额
* @param cache 用来存放已经计算过的金额。0表示没有计算过；1表示计算过，可以兑换；-1表示计算过，不能兑换。
* @return
*/
public static int coinChange(int[] coins,int amount,int[] cache){
if(amount < 0){
return -1;
}
if(amount == 0){
return 1;
}
//如果金额amount已经计算过了，则无需重复计算，直接从缓存数组中返回
if(cache[amount] != 0){
return cache[amount];
}
int result = -1;
for(int coin:coins){
int currentResult = coinChange(coins,amount-coin,cache);
//如果有一个硬币可以兑换，则返回真
if(currentResult == 1){
result = 1;
}
}
cache[amount] = result;
return result;
}
}
二.给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
解题思路：
1.F(S)表示，金额为S(S>0)时，所需的最少的硬币个数。C为最后一个放入硬币的面值。
2.可推出关系式：F(S) = F(S-C) + 1;
3.为了避免重复计算，新建一个数组保存已经计算过的值。
示例：
int[] coins = {1,2,5};amount = 11
F(11) = min{F(11-1)+1,F(11-2)+1,F(11-5)+1}
F(10) = min{F(10-1)+1,F(10-2)+1,F(10-5)+1}
...
F(0) = 0
硬币兑换 2.jpg
class Solution {
public static int coinChange(int[] coins, int amount) {
return mergeCoinChange(coins,amount,new int[amount+1]);
}
public static int mergeCoinChange(int[] coins, int amount, int[] cache){
if(amount == 0){
return 0;
}
if(amount < 0){
return -1;
}
//如果当前金额已经计算过了，直接返回结果。
if(cache[amount] != 0){
return cache[amount];
}
int minCount = Integer.MAX_VALUE;
for(int coin:coins){
//如果amount-coin<0，返回-1
int result = mergeCoinChange(coins,amount-coin,cache);
if(result>=0 && result < minCount){
minCount = result + 1;
}
}
//说明coins不能组成当前金额amount
if(minCount == Integer.MAX_VALUE){
cache[amount] = -1;
}else {
cache[amount] = minCount;
}
return cache[amount];
}
}
三.给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算是否可以凑成总金额，每个硬币只能使用一次。如果可以组成总金额，返回 1，如果不可以组成总金额，返回 1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: -1
示例 2:
输入: coins = [1, 2, 5], amount = 8
输出: 1
解题思路：
1.创建一个二维数组states[coins.length][amount+1]。
2.每一行记录决策是否将当前硬币放入组合的结果状态，总共有coins.length次决策。
3.每一列表示，决策之后，硬币的面值总和。
示例：int[] coins = {1,2,5};amount = 8
第一次决策之后，states[0][0]=true，表示第一枚硬币不放入组合；states[0][1]=true，表示第一枚硬币放入组合。
第二次决策之后，states[1][0] = true，states[1][2] = true，states[1][1] = true，states[1][3] = true。如下表。
第三次。。。
硬币兑换3.jpg
最后遍历第9列，若存在states[i][8] = true，则可以组成金额；若不存在states[i][8] = true，则不能组成金额。
package DynamicProgramming;
/**
* 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算是否可以凑成凑成总金额
* 每种金额最多只能使用一次。
* 如果没有任何一种硬币组合能组成总金额，返回 -1。
*
*/
public class CoinChange18 {
public static void main(String[] args) {
int[] coins = {2};
System.out.println(coinChange(coins,3));
}
public static int coinChange(int[] coins,int amount){
boolean[][] states = new boolean[coins.length][amount+1];
if(coins.length == 0){
return -1;
}
//初始化第一行元素
states[0][0] = true;
if(coins[0] <= amount){
states[0][coins[0]] = true;
}
//从第二行开始遍历
for(int i=1; i<coins.length; i++){
for(int j=0; j<amount+1; j++){
//每一行的状态，都是基于上一行的结果来的。
if(states[i-1][j]){
//放入硬币
if(j+coins[i] <= amount){
states[i][j+coins[i]] = true;
}
//不放硬币
states[i][j] = true;
}
}
}
//判断是否可以凑成金额amount
for(int k=0;k<coins.length;k++){
if(states[k][amount]){
return 1;
}
}
return -1;
}
}
