Why is this memoize solution not working?


  • 0
    M

    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:

    [484,395,346,103,329]
    4259

    public class Solution {
            
            
            HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
            
            public int coinChange(int[] coins, int amount) {
                
                
                Arrays.sort(coins);
                
                int result = coinChange(coins,0,amount);
                
                if(result < Integer.MAX_VALUE-1)
                {
                    return result;
                }
                else
                return -1;
                
            }
            
            
            private int min(int a, int b)
            {
                return a<b?a:b;
            }
            
            public int coinChange(int[] coins, int start, int amount)
            {
                
                if(map.containsKey(amount))
                {
                    //System.out.println(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));
                }
                
                
                map.put(amount,count);
                return count;
            }
                
            
        }

Log in to reply
 

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