Coin change dynamic-programming question top-down memoization approach

Question

I'm currently working on the coin change dynamic-programming question on leetcode -- https://leetcode.com/problems/coin-change/.

Here is the question statement:

You are given coins of different denominations and a total amount of money amount. 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:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

I tried to implemented a top-down memoization approach, where I keep an array of length amount, where each index represents the minimum amount of coins I can use to make that amount.

Here is my code in Java:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        int min = coinChange(coins, amount, dp);

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private int coinChange(int[] coins, int amount, int[] dp) {
        if (amount < 0) {
            return Integer.MAX_VALUE;
        }
        if (amount == 0) {
            return 0;
        }

        if (dp[amount] != Integer.MAX_VALUE) {
            return dp[amount];
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int val = coinChange(coins, amount - coins[i], dp);

            if (val != Integer.MAX_VALUE) {
                min = Math.min(min, val + 1);
            }
        }

        dp[amount] = min;
        return min;
    }
}

I thought this was the correct approach to dynamic-programming for this problem, however I'm getting Time Limit Exceeded on leetcode.

Is this a wrong approach do dynamic programming? If so, can you please explain where it is wrong?

Thank you so much in advance.

Answer 1

Your dp[amount] array will still go for recursion for all those amount for which it does not have solution i.e. if dp[amount] is less than 0, this will return INT_MAX, dp[amount] will INT_MAX. But you are checking that if dp[amount] !=INT_MAX then only return dp[amount] value. That is why TTE.

Answer 2

This is my version of the solution. This is easy to understand as well!

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        Arrays.fill(dp, 0);

        int min = coinChange(coins, amount, dp);
        return min;
    }

    private int coinChange(int[] coins, int amount, int[] dp) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }

        if (dp[amount]!=0) {
            return dp[amount];
        }

        int minimum = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int val = coinChange(coins, amount - coins[i], dp);

            if (val >= 0 && val < minimum) {
                minimum = val + 1;
            }
        }
        dp[amount] = (minimum == Integer.MAX_VALUE) ? -1 : minimum;
        return dp[amount];
    }
}