# Coin Change II - Dynamic Programming / Coin Change

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 `i`th 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]
``````