滑动窗口系列4-Leetcode322题零钱兑换-限制张数-暴力递归到动态规划再到滑动窗口

这个题目是Leecode322的变种，322原题如下：

我们这里的变化是把硬币变成可以重复的，并且只有coins数组中给出的这么多的金币，也就是说有数量限制： 

package dataStructure.leecode.practice;import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;public class CoinsChange {public static int coinChange(int[] coins, int amount) {if(amount == 0) return 0;int nums = process(coins, 0, amount);return nums == Integer.MAX_VALUE? -1 : nums;}/*** 最傻的递归* @param coins* @param curIndex* @param restAmount* @return*/public static int process(int[] coins, int curIndex, int restAmount) {if(restAmount == 0) return 0;if(curIndex == coins.length) return Integer.MAX_VALUE;//两种可能性：用当前位置的数字或者不用当前位置的数字int p1 = process(coins, curIndex + 1, restAmount);int ans = p1;int p2 = process(coins, curIndex + 1, restAmount - coins[curIndex]);if(p2 != Integer.MAX_VALUE) {ans = Math.min(ans, p2 + 1);}return ans;}/*** 最傻的递归改的动态规划* @param coins* @return*/public static int coinChangeDp(int[] coins, int amount) {int N = coins.length;int[][] dp = new int[N + 1][amount + 1];for(int j = 1; j <= amount; j++) {dp[N][j] = Integer.MAX_VALUE;}for(int curIndex = N - 1; curIndex >= 0; curIndex --) {for(int restAmount = 0; restAmount <= amount; restAmount ++) {//两种可能性：用当前位置的数字或者不用当前位置的数字int p1 = dp[curIndex + 1][restAmount];int ans = p1;if(restAmount - coins[curIndex] >= 0) {int p2 = dp[curIndex + 1][restAmount - coins[curIndex]];if(p2 != Integer.MAX_VALUE) {ans = Math.min(ans, p2 + 1);}}dp[curIndex][restAmount] = ans;}}return dp[0][amount];}public static int coinChange2(int[] coins, int amount) {if(amount == 0) return 0;CoinsInfo coinsInfo = getCoinsInfo(coins);int nums = process2(coinsInfo.values, coinsInfo.nums, 0, amount);return nums == Integer.MAX_VALUE? -1 : nums;}public static CoinsInfo getCoinsInfo(int[] coins) {//使用HashMap做频次的统计HashMap<Integer, Integer> count = new HashMap<>();//Arrays.sort(coins);//遍历coins的每个硬币并进行统计for (int coin : coins) {if(count.containsKey(coin)) {count.put(coin,count.get(coin) + 1);} else {count.put(coin, 1);}}//初始化values和nums数组，分别表示金额和数量，二者长度相等且一一对应int[] values = new int[count.size()];int[] nums = new int[count.size()];//根据count进行填充，从0下标开始填充int curIndex = 0;for (Integer value : count.keySet()) {//当前下标的value和num设置values[curIndex] = value;//这里要++，这样下次循环就可以进行下一个面值的统计了nums[curIndex ++] = count.get(value);}return new CoinsInfo(values, nums);}/*** 改进的递归-把coins按照面值进行分类，如果有很多重复的可以大大提高效率* @param values* @param nums* @param curIndex* @param restAmount* @return*/public static int process2(int[] values, int[] nums, int curIndex, int restAmount) {if(restAmount == 0) return 0;if(curIndex == values.length) return Integer.MAX_VALUE;//当前面值的钱可以用0个到nums[curIndex]个int ans = process2(values, nums, curIndex + 1, restAmount);for(int num = 1; num <= nums[curIndex]; num ++) {int nextMin = process2(values, nums, curIndex + 1, restAmount - num *values[curIndex]);if(nextMin != Integer.MAX_VALUE) {ans = Math.min(ans, nextMin) + num;}}return ans;}public static int coinChangeDp2(int[] coins, int amount) {if(amount == 0) return 0;CoinsInfo coinsInfo = getCoinsInfo(coins);int[] values = coinsInfo.values;int[] nums = coinsInfo.nums;int N = values.length;//动态规划数组int[][] dp = new int[N + 1][amount + 1];/*if(restAmount == 0) return 0;if(curIndex == values.length) return Integer.MAX_VALUE;*///根据递归中的上面两个if初始化动态规划数组, int默认是0所以第一个if忽略for(int j = 1; j <= amount; j++) {dp[N][j] = Integer.MAX_VALUE;}//对于普遍位置进行赋值for(int curIndex = N - 1; curIndex >= 0; curIndex --) {for(int restAmount = 0; restAmount <= amount; restAmount ++) {//当前面值的钱可以用0个到nums[curIndex]个int ans = dp[curIndex + 1][restAmount];for(int num = 1; num <= nums[curIndex]; num ++) {int nextMin = dp[curIndex + 1][restAmount - num *values[curIndex]];if(nextMin != Integer.MAX_VALUE) {ans = Math.min(ans, nextMin) + num;}}//斜率优化的相关分析,假设values数组为[1,2,3,5] nums为[4,2,2,1], amount = 15;//那我们推算dp[1][8] = dp[2][8] dp[2][6] + 1 dp[2][4] + 2中取最小值//而dp[1][6] = dp[2][6] dp[2][4] + 1 dp[2][2] + 2中的最小值//此时的dp[1][8]并不能根据dp[1][6]和dp[2][8]计算出，因为dp[1][6]用到的dp[2][2]+2在dp[1][8]中并没有，而这个可能就是最小值}}int result = dp[0] [amount];return result == Integer.MAX_VALUE? -1 : result;}public static int coinChangeSlideWindow(int[] coins, int aim) {if(aim == 0) return 0;CoinsInfo coinsInfo = getCoinsInfo(coins);int[] values = coinsInfo.values;int[] nums = coinsInfo.nums;int N = values.length;//动态规划数组int[][] dp = new int[N + 1][aim + 1];/*if(restAmount == 0) return 0;if(curIndex == values.length) return Integer.MAX_VALUE;*///根据递归中的上面两个if初始化动态规划数组, int默认是0所以第一个if忽略for(int j = 1; j <= aim; j++) {dp[N][j] = Integer.MAX_VALUE;}//对于普遍位置进行赋值for(int curIndex = N - 1; curIndex >= 0; curIndex --) {//使用窗口内最小值的更新结构，对于每个面值的货币尝试的方位是0~（目标金额和货币金额达的最小值-1）//比如如果面值是30，而目标值是100，那我们进行以下的尝试:(0 30 60 90) (1 31, 61, 91) ...(29, 59, 89)//而对于面值100，目标值30，我们进行:(0) (1)...(29)这些尝试//mod代表我们当前准备尝试多少组，例如上面的面值是30，而目标值是100，我们mod就从0到29，一共30组for(int mod = 0; mod < Math.min(aim+1, coins[curIndex]); mod ++) {//创建一个最小值窗口，放的是当前的金额LinkedList<Integer> window = new LinkedList<>();//mod是当前组的第一个位置，先进去，暂时是窗口最小值window.add(mod);//先把dp[curIndex][mod]的初始值设置为dp[curIndex + 1][mod]dp[curIndex][mod] = dp[curIndex + 1][mod];//在小于目标金额的情况下，每次加当前面值，类似0 30 60 90,不超过目标金额for(int curAmount = mod + coins[curIndex]; curAmount <= aim; curAmount += coins[curIndex]) {//如果窗口不为空且窗口最后的数是Integer的最大值或者最后的值+补偿金额大于当前的数量（下一行的dp值）while(!window.isEmpty() && (dp[curIndex+1][window.peekLast()] == Integer.MAX_VALUE || window.peekLast() + composite(window.peekLast(), curAmount, coins[curIndex]) >= dp[curIndex + 1][curAmount])) {window.pollLast();}//把当前金额（dp里的列）window.addLast(curAmount);//当前钱数-货币金额*货币数量刚好是可用的，如果再加一个就不行了，计算当前值或者计算下一个值的时候就都不能用了int overdue = curAmount - coins[curIndex] * (nums[curIndex] + 1);if(window.peekFirst() == overdue) {window.pollFirst();}dp[curIndex][curAmount] = dp[curIndex + 1][window.peekFirst()] + composite(window.peekFirst(), curAmount, coins[curIndex]);}//斜率优化的相关分析,假设values数组为[1,2,3,5] nums为[4,2,2,1], amount = 15;//那我们推算dp[1][8] = dp[2][8] dp[2][6] + 1 dp[2][4] + 2中取最小值//而dp[1][6] = dp[2][6] dp[2][4] + 1 dp[2][2] + 2中的最小值//此时的dp[1][8]并不能根据dp[1][6]和dp[2][8]计算出，因为dp[1][6]用到的dp[2][2]+2在dp[1][8]中并没有，而这个可能就是最小值}}int result = dp[0] [aim];return result == Integer.MAX_VALUE? -1 : result;}private static int composite(int preAmount, int curAmount, int coinAmount) {return (curAmount - preAmount)/ coinAmount;}public static void main(String[] args) {int[] coins = {2,5,3,2,5,2};int amount = 15;int nums = coinChange(coins, amount);System.out.println(nums);int numsDp = coinChangeDp(coins, amount);System.out.println(numsDp);int nums2 = coinChange2(coins, amount);System.out.println(nums2);int numsDp2 = coinChange2(coins, amount);System.out.println(numsDp2);int numsWindow = coinChangeSlideWindow(coins, amount);System.out.println(numsWindow);}
}class CoinsInfo {int[] values;int[] nums;public CoinsInfo(int[] values, int[] nums) {this.values = values;this.nums = nums;}
}