[Java] Shortest and Easy-To-Understand DP solution, O(mn) time, O(n) space


  • 0
    Z

    The idea is simple, think of the optimal structure in terms of the suboptimal problem:

    1. If the function int coinChange(int[] coins, int m, int amount) means the minimum number of coins used with mth coin.
    2. Then we can think of the problem in terms of its suboptimal structures
      • The minimum number of coins needed without mth is coinChange(coins, m - 1, amount)
      • The minimum number of coins needed with mth is coinChange(coins, m, amount - coins[m]) + 1
    3. Therefore, if we sort the coin by value, the overall minimum result is for every coin[m] included, min(coinChange(coins, m, amount - coins[m]) + 1), since the "not included" case is considered already in previous iterations.

    The code below is the iterative solution, slightly different from the recursive thinking process:

       public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.sort(coins);
        Arrays.fill(dp, -1); //initialize dp table, if it is -1, means no previous coin combination can make the change
        dp[0] = 0; //base case
        
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                //if the amount without coin can be made, then we add this coin, so the count + 1
                if (dp[j - coin] != -1) {
                    dp[j] = dp[j] == -1 ? dp[j - coin] + 1 : Math.min(dp[j], dp[j - coin] + 1);
                }
            }
        }
        return dp[amount];
        
       }

Log in to reply
 

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