# 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 ____________

+1 vote
326 views
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

(c) Divide and conquer

(d) Backtracking

This question was addressed to me by my school principal while I was bunking the class.

Query is from Coin Change Problem in chapter Dynamic Programming of Data Structures & Algorithms II

+1 vote
by (962k points)
selected by

The correct option is (b) Dynamic programming

Best explanation: The coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can be found by finding optimal solutions for subproblems). So, dynamic programming can be used to solve the coin change problem.

+1 vote