Slow Java solution although using cache?


  • 0
    R

    Hello,

    I don't understand why this solution is so slow (beats 0.14%), although I put in a cache every function's call result.
    What is the difference with a solution like the Approach #2 ? https://leetcode.com/articles/coin-change/
    Both are exploring all possibilities, caching their results.

    public class Solution {
        
        public Integer[][] cache;
        
        public int coinChange(int[] coins, int amount) {
            cache = new Integer[coins.length][amount + 1];
            int result = coinChangeRec(coins, amount, 0);
            return result;
        }
        
        public int coinChangeRec(int[] coins, int amount, int index)
        {
            if (index == coins.length && amount != 0)
                return -1;
            if (amount == 0)
                return 0;
            if (cache[index][amount] != null)
                return cache[index][amount];
            int result = -1;
            for (int i = 0; i * coins[index] <= amount; ++i)
                {
                    Integer local = coinChangeRec(coins, amount - i * coins[index], index + 1);
                    if (local != -1)
                        if (result == -1)
                            result = i + local;
                        else
                            result = Math.min(result, i + local);
                }
            cache[index][amount] = result;
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.