You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using

Mr. Dubey • 87.94K Points
Coach

Q. You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using

(A) greedy algorithm

(B) dynamic programming

(D) backtracking

Correct Answer - Option(B)
Views: 899
Filed under category Design and Analysis of Algorithms

 the coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can

You must be Logged in to update hint/solution