World's most popular travel blog for travel bloggers.

[Answers] Question regarding coin change algorithm (DP and greedy)

, , No Comments
Problem Detail: 

The question goes something like this:

Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy approaches would compare?

Intuitively I want to answer that DP will be faster because greedy runs the same number of comparisons regardless of the relationship between the elements in V. But DP is a recursive call on previous elements, so the fact that there is always a ratio of p between each denomination of V would suggest that DP will end up making less recursive calls. Can anyone confirm my answer or tell me why I'm wrong?

Asked By : Aisha Ashwal

Answered By : Aisha Ashwal

In terms of running time, the greedy algorithm is still going to be faster than the DP algorithm. DP will always produce the optimal solution regardless of values in V. Greedy, on the other hand, takes advantage of extra structure present in some value choices that allow it to effectively ignore possible ways of getting to the goal value. A coin system where the values are powers of p would allow the greedy algorithm to also consistently produce the optimal solution.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback