day-41 零钱兑换

思路
动态规划的思想，创建一个长度为amount的数组arr，arr[i]表示当amount=i时的最少硬币数

解题过程
arr初始化值为Integer.MAX_VALUE，再令arr[0]=0，arr[coins[j]]=1(0<=j<=coins.length),然后i从1向后遍历（i=coins[j]时跳过），当i-coins[j]>0&&arr[i-coins[j]]!=Integer.MAX_VALUE时，则arr[i]=Math.min(arr[i],arr[i-coins[j]]+1)
最后如果arr[amount]=Integer.MAX_VALUE，返回-1
飞则返回arr[amount]

Code

class Solution {public int coinChange(int[] coins, int amount) {int arr[]=new int[amount+1];Arrays.fill(arr,Integer.MAX_VALUE);int len=coins.length;arr[0]=0;for(int i=0;i<len;i++){if(coins[i]<=amount)arr[coins[i]]=1;}for(int i=1;i<=amount;i++){if(arr[i]!=1){for(int j=0;j<len;j++){if(i-coins[j]>0&&arr[i-coins[j]]!=Integer.MAX_VALUE){arr[i]=Math.min(arr[i],arr[i-coins[j]]+1);}}}}if(arr[amount]!=Integer.MAX_VALUE)return arr[amount];else return -1;}
}作者：菜卷
链接：https://leetcode.cn/problems/coin-change/solutions/2894860/ling-qian-dui-huan-by-ashi-jian-chong-da-m3vm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。