322.Coin Change

This question on LeetCode is a typical DP problem. Unfortunately, I always have a hard time solving DP problems. Therefore, practicing with this coin-change question would be the best way for me to become more familiar with DP.

Question

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

Brute force

The first solution comes to me is not DP but brute force solution. However, this solution will exactly get Time Limit Exceeded, proving that the medium question is not way too easy.

class Solution {
    private static int minVal;
    public int coinChange(int[] coins, int amount) {
        minVal = Integer.MAX_VALUE;
        coinChangeDFS(coins, amount, 0);
        return minVal == Integer.MAX_VALUE ? -1 : minVal;
    }
    
    private void coinChangeDFS(int[] coins, int amount, int count) {
        if(amount == 0) {
            minVal = Math.min(minVal, count);
            return;
        }   
        
        count++;

        for(int i = 0; i < coins.length; i++) {
            if(amount - coins[i] >= 0)
                coinChangeDFS(coins, amount - coins[i], count);
        }
    }
}

Dynamic Programming

We initialize the dp array to take its value as the fewest number of coins while every index of dp array represents the amounts. And, we start from the smallest amount 1 to the target amount.
As in, the test case is that coins array is [1, 2, 3] and the target amount is 6.
First, we initialize the dp array with target amount plus 1, and then we iterate through the dp array to determine the minimum number of coins required for every index. For example, We can approach this question by following these steps:

// Step 1
F(6) = min(F(6-1), F(6-2), F(6-3)) + 1

// step 2
F(5) = min(F(5-1), F(5-2), F(5-3)) + 1
F(4) = min(F(4-1), F(4-2), F(4-3)) + 1
// F(0) represent that we make up that amount totally
// the fewest number of coins will be 3 + 3
F(3) = min(F(3-1), F(3-2), F(3-3)) + 1

// O(N*M), where N is the value of amount and M is the length of the input array coins
class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}