A clear recursive and DP method in Java


  • 1
    A
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount <= 0) {
            return 0;
        }
        int[] min = new int[amount + 1];
        Arrays.fill(min, Integer.MAX_VALUE);
        min[0] = 0;
        helper(amount, coins, min);
        return min[amount];
    }
    
    
    public void helper(int amount, int[] coins, int[] min) {
        if (amount == 0) {
            return;
        }
        /*
        test if min[amount] has alreay been explored
        min[i] = -1: explored, but no combination for it. 
        min[i] = Integer.MAX_VALUE: not explored.
        */
        if (min[amount] != Integer.MAX_VALUE) {
            return;
        }
        int min_count = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (amount - coin >= 0) {
                helper(amount - coin, coins, min);
                if (min[amount - coin] != -1 && min[amount - coin] + 1 < min_count) {
                    min_count = min[amount - coin] + 1;
                }
            }
        }
        min[amount] = (min_count == Integer.MAX_VALUE ? -1 : min_count);
    }

Log in to reply
 

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