Sveip for å vise menyen

Problem D. Coin Change

Imagine you got N cents as combination of some coins, and the last added coin was C. Then, number of possible combinations dp[N] is equal to dp[N-C]. Consider that you can reach N cents by adding either c[0], c[1], ... ,c[m-1] cents, so number of possible combinations is:

dp[N] = dp[N-c[0]] + dp[N-c[1]] + ... + dp[N-c[m-1]]

Note that value of N-c[i] must be non-negative. Let's use tabulation: for values j from coin up to N: update dp[j] with adding dp[j-coin]; repeat for each coin.


              12345678910
            
def coinChange(n , coins):
  dp = [0 for _ in range(n+1)]
  dp[0] = 1
  for i in range(len(coins)):
    for j in range(coins[i], n+1):
      dp[j] += dp[j-coins[i]]
  return dp[n]
 
print(coinChange(14, [1,2,3,7]))
print(coinChange(100, [2,3,5,7,11]))

Bytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 4

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Problem D. Coin Change

dp[N] = dp[N-c[0]] + dp[N-c[1]] + ... + dp[N-c[m-1]]

Note that value of N-c[i] must be non-negative. Let's use tabulation: for values j from coin up to N: update dp[j] with adding dp[j-coin]; repeat for each coin.


              12345678910
            
def coinChange(n , coins):
  dp = [0 for _ in range(n+1)]
  dp[0] = 1
  for i in range(len(coins)):
    for j in range(coins[i], n+1):
      dp[j] += dp[j-coins[i]]
  return dp[n]
 
print(coinChange(14, [1,2,3,7]))
print(coinChange(100, [2,3,5,7,11]))

Bytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 4

Bytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor