Here is another minor memory optimsation which uses single vector instead of two
using namespace std;
int coin_game(std::vector<int> coins, int amount) {
vector<int>dp(amount + 1, 0);
dp[0] = 1;
for (int c : coins){
for (int s = 1; s <= amount; s++) {
if (s - c >= 0) {
dp[s] += dp[s-c];
}
}
}
return dp[amount];
}
I don’t know if this is only me. So far I am able to clearly understand all the bottom-up approaches and even optimise them, but I am struggling to come up with them without help. I can come up with the top-down solution + memoization but not the bottom up
You may think that with our top-down recursive solution, we would first loop through all amounts then coins. However, that would be incorrect.
I don’t see why the order of iteration can make any difference. In either case we fill the DP table by looking only at previous rows and previous columns.
I don’t think it is just you. I find bottom-up more challenging too
Can you explain this line?
dp[i][s] += dp[i][s - coins[i - 1]] # then, try the ith item (if it’s valid to use)
I would have imagined
dp[i][s] += dp[i-1][s - coins[i - 1]] +1
This is explained in the next paragraph. The order of the loops differs such that our definition of dp(i, s) changes
Here’s Bottom-Up solution in Js using one array:
function coinGame(coins, amount) {
const ways = [1].concat(range(amount))
for (const coin of coins) {
for (let i = 0; i <= amount; i++) {
if (coin <= i) {
ways[i] += ways[i - coin]
}
}
}
return ways[amount]
}
function range(n) {
return Array.from({ length: n }).fill(0)
}
Sharing my approach for the problem:
The idea is a classic DP’s “pick or skip” approach on sequences (the same for Coin Change problem).
You pick a coin(5) and if the remaining == 0 → you return “1 way”
If you cannot pick the coin anymore (ex another 5, remaining will be < 0), you skip the current coin and move to the next (i - 1)
return pick + skip number of ways
base case:
- If you ended up on i == 0 (I am going backward from N to 0) and remaining == 0 → return 1
- if you ended up on i == 0 and remaining % coins[0] == 0 → means that we can form from coins[0] required remaining sum → return 1
class Solution:
def change(self, amount: int, coins: List[int]) → int:
simplify base case
N = len(coins)
dp = [1] + [0] * amount
for coin in coins:
for remainder in range(coin, amount + 1):
dp[remainder] += dp[remainder - coin]
return dp[amount]
1d dp
N = len(coins)
dp = [0] * (amount + 1)
for remainder in range(amount + 1):
dp[remainder] = 1 if remainder % coins[0] == 0 else 0
for i in range(1, N):
for remainder in range(coins[i], amount + 1):
dp[remainder] += dp[remainder - coins[i]]
return dp[amount]
2D dp bottom-up
N = len(coins)
dp = [[0] * (amount + 1) for _ in range(N)]
for remainder in range(amount + 1):
dp[0][remainder] = 1 if remainder % coins[0] == 0 else 0
for remainder in range(amount + 1):
for i in range(1, N):
pick = 0
if remainder - coins[i] >= 0:
pick = dp[i][remainder - coins[i]]
skip = dp[i - 1][remainder]
dp[i][remainder] = pick + skip
return dp[N - 1][amount]
top-down
@cache
def dfs(i, remainder):
if i == 0:
if t == 0 or remainder % coins[0] == 0:
return 1
return 0
pick = 0
if remainder - coins[i] >= 0:
pick = dfs(i, remainder - coins[i])
skip = dfs(i - 1, remainder)
return pick + skip
N = len(coins)
return dfs(N - 1, amount)
Hi, I use tabulation. But once I try to use coin iteration as inside loop, the result is not correct. Can anyone help me figure out what did I miss?
var change = function(amount, coins) {
var N = coins.length
var dp = [1, ...Array(N).fill(0)] // 1-indexed
for(var i = 1; i <= amount; i++) {
for(var coin of coins) {
dp[i] += (i - coin) >= 0 ? dp[i - coin] : 0
}
}
return dp[amount]
}
a simple js version
function coinGame(coins, amount) {
const dp = new Array(amount + 1).fill(0)
dp[0] = 1
for(const item of coins){
for(let j= item; j<= amount+ 1;j++){
dp[j]+=dp[j-item]
}
}
return dp[amount];
}