1. Coin Change

You are given coins of different denominations and a total amount of moneyamount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return-1.

Example 1:
coins =[1, 2, 5], amount =11
return3(11 = 5 + 5 + 1)

Example 2:
coins =[2], amount =3
return-1.

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

public class Solution {
    public int coinChange(int[] coins, int amount) {

        int[] dp = new int[amount + 1];
        int total= 1;

        while(total <= amount) {

            int min = Integer.MAX_VALUE;
            for(int coin: coins){
                int diff = total - coin;
                if(diff == 0 ||( diff >0 && dp[diff] != -1))
                    min = Math.min(min, dp[diff] + 1);
            }

            dp[total ++] = min == Integer.MAX_VALUE? -1: min;
        }

        return dp[amount];
    }
}

public class Solution {
    public int coinChange(int[] coins, int amount) {

        if(amount == 0 || coins.length == 0) return 0;

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;
        for(int coin: coins) {

            for(int i = coin; i <= amount; i ++) {
                dp[i] = Math.min(dp[i], dp[i - coin] == Integer.MAX_VALUE? Integer.MAX_VALUE: dp[i - coin] + 1);
            }
        }

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

2. Coin Change II

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

public class Solution {
    public int change(int amount, int[] coins) {

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

        for(int coin: coins){
            for(int j = coin; j <= amount; j ++)
                dp[j] += dp[j - coin]; 
        }

        return dp[amount];
    }
}

3. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations 
that add up to a positive integer target.

Example;
nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

public class Solution {
    public int combinationSum4(int[] nums, int target) {

        int[] dp = new int[target + 1];

        dp[0] = 1;

        for(int i = 1; i <= target; i ++){

            for(int num: nums){
                if(num <= i)
                    dp[i] += dp[i - num];
            }
        }

        return dp[target];
    }
}

public int combinationSum4(int[] nums, int target) {
    if (target == 0) {
        return 1;
    }
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            res += combinationSum4(nums, target - nums[i]);
        }
    }
    return res;
}

leetcode 494