算法动态规划（七）-背包问题4
输入：[1,2,5] , 11输出：3。1+5+5=11输入：[2],3输出：-1；
🙋解法一：记忆化递归
🙇思路：
Map<Integer,Integer> map = new HashMap<>();public int coinChange(int[] coins, int amount) {if(amount <= 0){return 0;}return find_h(coins,amount);}private int find_h(int[] nums,int amount){if(amount <0){return -1;}if(amount == 0){return 0;}if(map.containsKey(amount)){return map.get(amount);}int count=Integer.MAX_VALUE;for(int num:nums){if(num > amount){continue;}int solu=find_h(nums,amount-num);if(solu>=0){count = Math.min(count,solu+1);}}if(count == Integer.MAX_VALUE){count =-1;}map.put(amount,count);return map.get(amount);}
🙋解法二：动态规划【自上而下】
🙇思路：
状态定义：F(S)，凑齐总金额S，需要的最小硬币数。
状态转移方程：F(S) = F(S-coins[i]) + 1。
public int coinChange(int[] coins, int amount) {if (amount < 1) return 0;return coinChange_h(coins, amount,new int[amount+1]);}private int coinChange_h(int[] coins, int amount,int[] count) {if (amount < 0) return -1;if (amount == 0) return 0;if (count[amount] != 0) return count[amount];int min = Integer.MAX_VALUE;for (int coin : coins) {int res = coinChange_h(coins, amount - coin,count);if (res >= 0 )min = Math.min(1 + res,min);}count[amount] = min == Integer.MAX_VALUE ? -1:min;return count[amount];}
🙋解法三：动态规划【自下而上】
🙇思路：
状态定义：dp[j]，凑齐总金额j，需要的最小硬币数。
状态转移方程：dp[i][j]= min(dp[i][j],dp[i](j-coins[i]) + 1)。凑齐总金额j需要的最小硬币数，当地i个硬币选或者不选两种情况。
public int coinChange_2(int[] coins, int amount) {if (amount < 1) return 0;int[] dp = new int[amount+1];Arrays.fill(dp,amount+1);//这儿解释下为啥默认填充amount+1，凑齐amount最多也就是面值为1的数总计用amount个，// 所以最少个数一定是<amount+1的dp[0]=0;for(int j=1;j<=amount;j++){for(int num:coins){if(num <= j){dp[j]=Math.min(dp[j],dp[j-num]+1);}}}return dp[amount]==amount+1?-1:dp[amount];}
复杂度分析
时间复杂度：O(SN)：这里S是总金额，N是提供的不同面额数，即数组长度。我们要计算O(S)个不同总金额，对每次的总金额需要N个面额来转移状态，一共需要O(SN)的时间复杂度。
空间复杂度：O(S)，我们使用了一个S+1的dp数组。
不积跬步，无以至千里。
文章有帮助的话，点个转发、在看呗
。
谢谢支持哟 (*^__^*)
END
👇