Pyyhkäise näyttääksesi valikon

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

Vaihda työpöytään todellista harjoitusta vartenJatka siitä, missä olet käyttämällä jotakin alla olevista vaihtoehdoista

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 3. Luku 4

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

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

Vaihda työpöytään todellista harjoitusta vartenJatka siitä, missä olet käyttämällä jotakin alla olevista vaihtoehdoista

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 3. Luku 4

Vaihda työpöytään todellista harjoitusta vartenJatka siitä, missä olet käyttämällä jotakin alla olevista vaihtoehdoista