Blind 75
Coin Change
- Problem
- LC 322
- Category
- DP
- File
- blind75_LC322CoinChange.java
- Path
- pkg5leetcode/blind75/blind75_LC322CoinChange.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC322CoinChange.java
- Approach
- Bottom-up DP min coins for each amount 1..amount.
- Complexity
- Time O(amount * coins), Space O(amount)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Coin Change | LC 3225 * APPROACH: Bottom-up DP min coins for each amount 1..amount.6 * COMPLEXITY: Time O(amount * coins), Space O(amount)7 */8import java.util.*;9 10public class blind75_LC322CoinChange {11 static int coinChange(int[] coins, int amount) {12 int[] dp = new int[amount + 1];13 Arrays.fill(dp, amount + 1);14 dp[0] = 0;15 for (int a = 1; a <= amount; a++)16 for (int c : coins)17 if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);18 return dp[amount] > amount ? -1 : dp[amount];19 }20 21 public static void main(String[] args) {22 check(coinChange(new int[]{1, 2, 5}, 11) == 3, "case1");23 check(coinChange(new int[]{2}, 3) == -1, "case2");24 System.out.println("all tests passed");25 }26 27 static void check(boolean cond, String name) {28 if (!cond) throw new AssertionError("FAILED: " + name);29 System.out.println(" PASS " + name);30 }31}