Google Dynamic Programming Problem - Coin Change - Leetcode 322

Показать описание

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

Рекомендации по теме

Комментарии

Master Data Structures & Algorithms For FREE at AlgoMap.io!

GregHogg

For a very formal but brief explanation: in a dynamic programming solution, we first must identify the sub problems we are using. Given n, and the set of coins M, our optimal solution is dependent on the number of coins needed to make n-m amount, for n-m>=0. But notice if n-m is 0, we trivially return an empty multiset. This is important, because for all m in M they must be greater than 0. So we define a recurrence relation OPT(n, M) = Empty if n=0, or min(OPT(n-m, M) union m) since we need to include the coin we just subtracted off.

petrosgeorgiou

Run the loop on the amount modulus the highest valued coin and add that to the quotient of the amount divided by the highest coin. We can avoid looping for anything below two of the highest coin's value.
Also types in a duck typed language? What if you want to use non primitive int? There are other number types people might want to use.

overclucker

The rough idea is that the minimum number of coins required to make the target is one more than the minimum of the minimum number of coins to make the target minus each of the coin values.

f(n) = 1 + min f(n-c)

where f(0) = 0 and f(n) is undefined for negative n. If the target is N, then f(N) is the solution.

The method in the video is just a tabulation of this, meaning you build an array a such that a[n] = f(n) for all 0 <= n <= N, by setting a[0] = f(0) = 0 and calculating each consecutive entry using the recursive formula. The order of evaluation ensures that there is no actual recursion taking place, because all prior values will have been calculated already.

alxjones

If I had an infinite amount of coins I wouldn't need a job, so no need to solve typical problems in job application interviews. Problem solved!

f.herumusu

Great example, bit of a missed opportunity to talk about the differences with greedy though

subatomicmolecules

Easier approach: convert the number to binary and count the bits that = 1

kintr

bro i spent a whole day on this s... dude, just nailed it in 1 min

givehuggy

I was thinking you start a loop from the right of the array after you sort it, you integer divide amount by current coin, call that quotient, add quotient to the number of coins needed and do amount -= coin value * quotient

When the loop is over just check if amount is equal to 0 to see if its possible

hehexd

Can we just loop the coins from end and divide the target and update the target to be the reminder of the division

Omargamingandtech

Real-world coinage systems are chosen so that greedy algorithms work.

davidgillies

What, do I understand badly or it should be solved just by using modulus and starting with the biggest coin less or equal to the sum?

jaimeduncan

Instead is using dp data structure... Can we use @cache decorator in python ? And then simple recursion

sid._.

There are some fringe cases (not with these options) where you can't just keep using the highest available. Try making 12 from [1, 3, 6, 7].

manudude