We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Coin Change Problem
  5. Discussions

The Coin Change Problem

  • orange_ao
     + 0 comments
    1. Set up: sort the coins in ascending manner.
    2. Define state: dp[i][j]: # of ways to get number i, using coins values as largest as the j-th coin. (i.e. the coins chosen to construct number i cannot exceed c[j])

    3. State transition: for each coin c[j] and fix to be the next (also largest) coin from the last step (i.e. i-c[j])

      • Starting point: number of ways using c[j] as the largest always >= using the second largest coin c[j-1]

        dp[i][j] = dp[i][j-1]

      • If i no additional ways
      • If i==c[j]: 1 new way in addition to using at largest c[j-1], i.e. using c[j] directly to get number i

        dp[i][j]+=1

      • If i>c[j]: first get i-c[j] in dp[i-c[j]][j] ways, then get i by adding c[j] -> dp[i-c[j]][j] new ways

        dp[i][j] += dp[i-c[j]][j] ** why no duplications? for example, dp[4][] = dp[1][] + dp[3][], without [] specified, dp[1]=1 means (1+3); dp[3]=2 means (1+1+1; 3+1), where (1+3) is double-counted. If when we use a new coin, and make it the largest that can be used, then dp[4-1][1]=1 (i.e. 1+1+1).

    4. Edge cases:

      • dp[i][0] = 1 if i%c[0]==0 else 0
    def getWays(n, coins):
    coins = sorted(coins)
    print(coins)
    dp=[[0]*len(coins) for i in range(n+1)]
 
    for i in range(1,n+1):
        print("0 : ", dp[0])
        # visited = {c:False for c in coins}
        dp[i][0]=1 if i%coins[0]==0 else 0
        for j in range(1,len(coins)):
            dp[i][j]=dp[i][j-1] 
            if i<coins[j]: 
                continue
            if i==coins[j]:
                dp[i][j]+=1
            dp[i][j]=dp[i][j]+dp[i-coins[j]][j]
        print(i,": ", dp[i])   
    
    return dp[n][len(coins)-1]