search

yokostan / Leetcode-Solutions

Doing exercise on Leetcode. Carry on!
0 stars 3 forks source link

Leetcode #322. Coin Change #259

Open yokostan opened 5 years ago

yokostan commented 5 years ago 
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        int[] dp = new int[amount + 1];
        int sum = 1;

        while (sum <= amount) {
            int min = -1;
            for (int coin : coins) {
                if (sum >= coin && dp[sum - coin] != -1) {
                    int temp = dp[sum - coin] + 1;
                    min = min < 0 ? temp : (temp < min ? temp : min);
                }
            }
            dp[sum] = min;
            sum++;
        }
        return dp[amount];
    }
}
yokostan commented 5 years ago

A little optimization:

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        int[] dp = new int[amount + 1];
        int sum = 1;

        while (sum <= amount) {
            int min = -1;
            for (int coin : coins) {
                if (sum >= coin && dp[sum - coin] != -1) {
                    int temp = dp[sum - coin] + 1;
                    min = min == -1 ? temp : Math.min(temp, min);
                }
            }
            dp[sum] = min;
            sum++;
        }
        return dp[amount];
    }