322. Coin Change

有点类似 perfect squares那道题-279.

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount+1];
        for (int i=1; i<=amount; i++) {
            int min_tmp = Integer.MAX_VALUE;
            for (int j=0; j<coins.length; j++) {
                // if the amount can be found in the coins array;
                if(i == coins[j]) {
                    min_tmp = 1;
                    break;
                // if cannot be found, but can keep on minus the coins value;
                } else if (i > coins[j] && dp[i-coins[j]] > 0 && dp[i-coins[j]]+1 < min_tmp)
                    min_tmp = dp[i-coins[j]]+1;
            }
            dp[i] = min_tmp == Integer.MAX_VALUE ? -1 : min_tmp;
        }
        return dp[amount];
    }
}