Question

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

Answer 1

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.