322.CoinChange

标签：Output int coins 322 amount ans Input CoinChange

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Note:

You may assume that you have an infinite number of each kind of coin.

ans[i]表示凑齐钱数i时需要的最小零钱数目 class Solution {    public int coinChange(int[] coins, int amount) {        int[] ans = new int[amount+1];        for (int i = 0; i < amount+1; i++)           ans[i] = amount + 1;//注意，初始化的时候不能设成Integer.MAX_VALUE,后面要有ans[i-coins[j]]+1的操作，会溢出称为Integer.MIN_VALUE        ans[0] = 0;       for(int i = 0; i < coins.length; i++){           for(int j = 1; j < ans.length; j++){              if(coins[i] <= j)                  ans[j] = Math.min(ans[j],ans[j-coins[i]]+1);           }       }        return ans[amount] == (amount+1) ? -1 : ans[amount];    } }

标签：Output,int,coins,322,amount,ans,Input,CoinChange
From： https://www.cnblogs.com/MarkLeeBYR/p/16943680.html