package com.jiucaiyuan.net.question;
/**
* @Author jiucaiyuan 2022/6/5 11:33
* @mail services@jiucaiyuan.net
*/
public class CoinAmount {
/**
* 暴力递归
* 给一个正数数组，每个数表示一枚硬币的面值，给定一个数值，从硬币中选择得到这个金额的最少硬币数
* 比如指定硬币有[1,4,7,2,4,3,5,1,3]
* 指定金额10，那么最少硬币数是7+3，两枚硬币，返回2
*
* @param arr 硬币，arr.length硬币个数，arr[index]表示index硬币金额
* @param amount 组合最终的金额
* @return 组合最终金额的最少硬币数
*/
public static int minCoinsCountV1(int[] arr, int amount) {
return processV1(arr, 0, amount);
}
public static int processV1(int[] arr, int index, int rest) {
//超额了
if (rest < 0) {
return -1;
}
//金额正好
if (rest == 0) {
return 0;
}
//钱还有，但是硬币没了
if (index == arr.length) {
return -1;
}
//钱还有，硬币也还有
//当前硬币不选择，往后尝试
int p1 = processV1(arr, index + 1, rest);
//当前硬币选择，往后尝试
int p2Next = processV1(arr, index + 1, rest - arr[index]);
//如果后续尝试后，发现金额超了，不能组成目标金额
if (p1 == -1 && p2Next == -1) {
return -1;
}
//如果
if (p1 == -1) {
return p2Next + 1;
}
if (p2Next == -1) {
return p1;
}
return Math.min(p1, p2Next + 1);
}
/**
* 暴力递归添加缓存，去掉重复计算，空间换时间
* <p>
* 给一个正数数组，每个数表示一枚硬币的面值，给定一个数值，从硬币中选择得到这个金额的最少硬币数
* 比如指定硬币有[1,4,7,2,4,3,5,1,3]
* 指定金额10，那么最少硬币数是7+3，两枚硬币，返回2
*
* @param arr 硬币，arr.length硬币个数，arr[index]表示index硬币金额
* @param amount 组合最终的金额
* @return 组合最终金额的最少硬币数
*/
public static int minCoinsCountV2(int[] arr, int amount) {
int[][] dp = new int[arr.length + 1][amount + 1];
for (int i = 0; i <= arr.length; i++) {
for (int j = 0; j <= amount; j++) {
dp[i][j] = -2;//-2表示没有计算过 -1表示计算过，无效
}
}
return processV2(arr, 0, amount, dp);
}
;
public static int processV2(int[] arr, int index, int rest, int[][] dp) {
//超额了
if (rest < 0) {
return -1;
}
if (dp[index][rest] != -2) {
return dp[index][rest];
}
if (rest == 0) {
//金额正好
dp[index][rest] = 0;
} else if (index == arr.length) {
//钱还有(amount > 0)
// 没硬币了
dp[index][rest] = -1;
} else {
//硬币也还有
//当前硬币不选择，往后尝试
int p1 = processV2(arr, index + 1, rest, dp);
//当前硬币选择，往后尝试
int p2Next = processV2(arr, index + 1, rest - arr[index], dp);
//如果后续尝试后，发现金额超了，不能组成目标金额
if (p1 == -1 && p2Next == -1) {
dp[index][rest] = -1;
} else if (p1 == -1) {
dp[index][rest] = p2Next + 1;
} else if (p2Next == -1) {
dp[index][rest] = p1;
} else {
dp[index][rest] = Math.min(p1, p2Next + 1);
}
}
return dp[index][rest];
}
/**
* 动态规划版本
* <p>
* 给一个正数数组，每个数表示一枚硬币的面值，给定一个数值，从硬币中选择得到这个金额的最少硬币数
* 比如指定硬币有[1,4,7,2,4,3,5,1,3]
* 指定金额10，那么最少硬币数是7+3，两枚硬币，返回2
*
* @param arr 硬币，arr.length硬币个数，arr[index]表示index硬币金额
* @param amount 组合最终的金额
* @return 组合最终金额的最少硬币数
*/
public static int minCoinsCountV3(int[] arr, int amount) {
int[][] dp = new int[arr.length + 1][amount + 1];
for (int i = 0; i <= arr.length; i++) {
dp[i][0] = 0;
}
for (int col = 1; col <= amount; col++) {
dp[arr.length][col] = -1;
}
for (int index = arr.length - 1; index >= 0; index--) {
for (int rest = 1; rest <= amount; rest++) {
//过程改自递归调用的process方法
int p1 = dp[index + 1][rest];
int p2Next = rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : -1;
if (p1 == -1 && p2Next == -1) {
dp[index][rest] = -1;
} else if (p1 == -1) {
dp[index][rest] = p2Next + 1;
} else if (p2Next == -1) {
dp[index][rest] = p1;
} else {
dp[index][rest] = Math.min(p1, p2Next + 1);
}
}
}
return dp[0][amount];
}
//for test
public static int[] generateRandomArray(int length, int max) {
int[] arr = new int[(int) (Math.random() * length) + 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * max) + 1;
}
return arr;
}
public static void main(String[] args) {
int[] array = {4, 9, 10, 4};
minCoinsCountV2(array, 17);
int len = 10;
int max = 10;
int testTimes = 100000;
for (int i = 0; i < testTimes; i++) {
int[] arr = generateRandomArray(len, max);
int amount = (int) (Math.random() * 3 * max) + max;
System.out.println("------------------------------" + i);
System.out.println(print(arr) + "<----->" + amount);
int minCoinsCountV1 = minCoinsCountV1(arr, amount);
int minCoinsCountV2 = minCoinsCountV2(arr, amount);
int minCoinsCountV3 = minCoinsCountV3(arr, amount);
System.out.println(minCoinsCountV1 + "<----->" + minCoinsCountV2 + "<----->" + minCoinsCountV3);
if (minCoinsCountV1 != minCoinsCountV2 || minCoinsCountV1 != minCoinsCountV3) {
System.out.println("goooooooood!");
break;
}
}
}
private static String print(int[] arr) {
StringBuffer sb = new StringBuffer();
for (int a : arr) {
if (sb.length() == 0) {
sb.append("[").append(a);
} else {
sb.append(",").append(a);
}
}
sb.append("]");
return sb.toString();
}
}