Why is this memoize solution not working?

  • 0

    The idea is simple:

    Consider the current coin or
    Do not consider the current coin. The brute force solution works. Memoization does not. Any help will be appreciated. And fails for the following case:


    public class Solution {
            HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
            public int coinChange(int[] coins, int amount) {
                int result = coinChange(coins,0,amount);
                if(result < Integer.MAX_VALUE-1)
                    return result;
                return -1;
            private int min(int a, int b)
                return a<b?a:b;
            public int coinChange(int[] coins, int start, int amount)
                    return map.get(amount);
                if(amount == 0)
                return 0;
                int count = Integer.MAX_VALUE-1;
                if(start<coins.length && coins[start]<=amount)
                count = min(coinChange(coins, start, amount-coins[start])+1, coinChange(coins,start+1,amount));
                return count;

Log in to reply

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