Coin Change II - Dynamic Programming / Coin Change

Problems
1

https://algo.monster/problems/coin_change_ii

2

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

3

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.

4

I don’t think it is just you. I find bottom-up more challenging too

5

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

6

This is explained in the next paragraph. The order of the loops differs such that our definition of dp(i, s) changes

7

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)
}
8

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)

9

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]
}