Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Вивчайте Problem D. Coin Change | Solutions
Dynamic Programming

Свайпніть щоб показати меню

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

Switch to desktopПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів
Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 3. Розділ 4
Ми дуже хвилюємося, що щось пішло не так. Що трапилося?

Запитати АІ

expand
ChatGPT

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

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

Switch to desktopПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів
Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 3. Розділ 4
Switch to desktopПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів
Ми дуже хвилюємося, що щось пішло не так. Що трапилося?
some-alt