四刷 06/2022
Version #1 DP
写了一个bug就是如果当前的i - coin >= 0的时候，还有可能i - coin是不能被组成的值
需要先check是不是Integer.MAX_VALUE
Time O(amount * #coins)
Space O(amount)
Runtime: 37 ms, faster than 36.73% of Java online submissions for Coin Change.
Memory Usage: 44.8 MB, less than 72.04% of Java online submissions for Coin Change.
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.sort(coins);
for (int i = 1; i <= amount; i++) {
dp[i] = Integer.MAX_VALUE;
for (int coin : coins) {
if (coin > i) {
break;
}
if (dp[i - coin] == Integer.MAX_VALUE) {
continue;
}
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
三刷
上来直接想到dfs了，看答案清一色的dp“Then we observed that this algorithm may compute coinChange of same amount for many times, which are kind of duplicate, if we can store "amount->fewest_coin_count" into hashtble, then we don't need to recompute again. Actually, this is DP (dynamic programming), aka. Memorization. So the final solution is to add hashtbl implementation to the previous solution and problem solved, this is of upper time complexity O(n^c), which is polynomial”
//dp[i] - minimum coins needed to current amount
Version #3 Memorized Recursion -> DP
虽然是recursion的方法但是完全是dp的思想，memorized recursion的原因是因为amount不是连续值，如果用dp[]会浪费空间，所以用HashMap
非常慢
5.68 %
class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) return -1;
// key-amount, value-minCoins
Map<Integer, Integer> visited = new HashMap<>();
return dfsHelper(coins, amount, visited);
}
// min #coins for current amount
private int dfsHelper(int[] coins, int amount, Map<Integer, Integer> visited) {
if (visited.containsKey(amount)) return visited.get(amount);
if (amount == 0) return 0;
int min = Integer.MAX_VALUE;
for (int coin : coins) {
if (coin > amount) continue;
int next = dfsHelper(coins, amount - coin, visited);
if (next != -1) {
min = Math.min(1 + next, min);
}
}
min = min == Integer.MAX_VALUE ? -1 : min;
visited.put(amount, min);
return min;
}
}
Version #2 DFS
Time depth = #coins
branch for each level -> residual / denomination -> say average m
Time O(m^#coins)
Space depth of system stack -> O(#coins)
99.65 %
class Solution {
private int min;
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0) return -1;
// index 0(5) 1(2) 3(1)
// count[index] 0 0 0
Arrays.sort(coins);
min = Integer.MAX_VALUE;
dfsHelper(coins.length - 1, coins, amount, 0);
return min == Integer.MAX_VALUE ? -1 : min;
}
private void dfsHelper(int denoIndex, int[] coins, int amount, int count) {
if (amount == 0) {
min = Math.min(min, count);
}
if (denoIndex < 0) return;
if (denoIndex == 0) {
if (amount % coins[denoIndex] != 0) return;
min = Math.min(min, count + amount / coins[denoIndex]);
return;
}
for (int i = amount / coins[denoIndex]; i >= 0; i--) {
// System.out.println(coins[denoIndex] + " " + count[denoIndex]);
if (count + i >= min) return;
dfsHelper(denoIndex - 1, coins, amount - coins[denoIndex] * i, count + i);
}
}
}
Version #1 DP
三刷
95.33 %
class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0) {
return -1;
}
// dp[i] = min coins need for amount i
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
int min = Integer.MAX_VALUE;
for (int coin : coins) {
if (i - coin >= 0 && dp[i - coin] != -1) {
min = Math.min(min, dp[i - coin] + 1);
}
}
dp[i] = min == Integer.MAX_VALUE ? -1 : min;
}
return dp[amount];
}
}
二刷
85.51 %
class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) return -1;
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int coin : coins) {
if (coin <= amount) dp[coin] = 1;
}
for (int i = 1; i <= amount; i++) {
if (dp[i] == 1) continue;
int min = Integer.MAX_VALUE;
for (int coin : coins) {
if (coin <= i) min = Math.min(dp[i - coin], min);
}
if (min == Integer.MAX_VALUE) {
dp[i] = min;
} else {
dp[i] = min + 1;
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
一刷
比较机智地sort了coins
sort #coins * log # coins
dp space amount
dp time #coins * amount
Space O(amount)
#coins - n
Time O(n^2 * amount * logn)
sort是为了方便当面值大于curr的时候直接breakd
但是增加了时间复杂度
主要取决于amount和denominations之间的关系
87.05 %
public class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount <= 0) return 0;
int[] dp = new int[amount + 1];
Arrays.sort(coins);
//dp[0] = 0;
//dp[i] - minimum coins needed to current amount
for (int coin : coins) {
if (coin == amount) return 1;
if (coin < amount) dp[coin] = 1;
else break;
}
for (int curr = 1; curr <= amount; curr++) {
if (dp[curr] != 0) continue;
int min = Integer.MAX_VALUE;
for (int c = 0; c < coins.length; c++) {
if (curr - coins[c] <= 0) break;
else {
int prev = dp[curr - coins[c]];
if (prev == -1) continue;
min = Math.min(min, prev + 1);
}
}
dp[curr] = min == Integer.MAX_VALUE ? -1 : min;
}
return dp[amount];
}
}
No comments:
Post a Comment