1. Computer Science Engineering (CSE)
  2. Design and Analysis of Algorithms
  3. You are given infinite coins of denomina...

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» B. dynamic programming
Explanation: the coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can