零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2] , amount = 3 输出: -1
说明:
你可以认为每种硬币的数量是无限的。
问题：输入{1,2147483647};
做题的时候一直遇到一个问题，Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2147483648
说明Int溢出了。得到的结果一直是- 2147483647。 因为i+coins[j]=1+2147483647 >=Integer.MAX_VALUE;
解决办法是如果溢出了，if(i+coins[j]<0) break;
这里便发现了如果溢出，那么一定是用负数表示的。
x = 2147483647
x+1 = -2147483648
x+2 = -2147483647
当最大值加上 1 时，结果反而变成表示范围中最小的值；当最大值加上 2 时，结
果变成表示范围中次小的值，这就是数据类型的溢出。
算法思路：利用动态规划的思想，在1-amount之间建立一个下标索引，nums表示钱数所需要的最少硬币数量。
首先对已有硬币进行标记，下标都为1。同时注意：当硬币的面值大于amount时，将不会被标记。
开始从1遍历至amount。
如果当前遍历的面值不能用硬币凑出，那么就跳出，说明无法取到这个面值。比如{2，5，10} 永远无法取到1，3，7，9。这些都是不需要判断的。
遍历的面值再加上硬币的面值，nums[i+coins[j]]表示当前面值所需最小硬币数量。
需要添加如下几个判断条件：
1.遍历的钱数i+coins[j]一定要小于amount。
2.当前所需硬币数比原来需要的硬币数量更少，那么更新nums数组。
1class Solution { 2 public int coinChange(int[] coins, int amount) { 3 if(amount==0)return 0; 4 long[] nums=new long[amount+1]; 5 for(int i=0;i<coins.length;i++){ 6 if(coins[i]<=amount)nums[coins[i]]=1; 7 } 8 for(int i=1;i<=amount;i++){ 9 if(nums[i]==0)continue; 10 for(int j=0;j<coins.length;j++){ 11 int temp=i+coins[j]; 12 if(temp<0) break; //这里在验证{1,2147483647} 反复出现了错误，因为i+coins[j]已经溢出，溢出是用-22147483647表示，溢出则跳出循环 13 if(temp<=amount&&(nums[temp]==0||1+nums[i]<nums[temp]))nums[temp]=1+nums[i]; 14 } 15 } 16 if(nums[amount]==0)return -1;//这里如果凑不出amount的面值，那么就不需要判断了。 17 return nums[amount]; 18 } 19}