Thinking process

Can I use a coin with same values multiple times?

• Yes

What is the model of this problem?

• given possible values of items
• you have infinite number of items with same values
• given a target value
• find the minimum number of items you need to use to that all items sum up to this target value?

Can I construct a state for which an optimal solution is found and with the help of which we can find the optimal solution for the next state?

• dp[i] => the minimum number of coins which sum up to i

Time Complexity

O(amount * n) with O (amount) extra space

public class Solution {
    //dp[i] = 
    public int coinChange(int[] coins, int amount) {
        //validate input
        if (coins == null || coins.length == 0 || amount < 0) return -1;

        int[] min = new int[amount + 1];
        min[0] = 0;

        for (int i = 1; i <= amount; ++i) {
            min[i] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < coins.length; ++j) {
                if (coins[j] <= i && min[i - coins[j]] < Integer.MAX_VALUE) {
                    min[i] = Math.min(min[i], min[i - coins[j]] + 1);
                }
            }
        }

        return min[amount] != Integer.MAX_VALUE ? min[amount] : -1;
    }
}