Question

Suppose you are given infinite coins of N 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. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?

(a) O(N)

(b) O(S)

(c) O(N^2)

(d) O(S*N)

I have been asked this question during an online interview.

I'd like to ask this question from Coin Change Problem in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

The correct choice is (b) O(S)

For explanation: To get the optimal solution for a sum S, the optimal solution is found for each sum less than equal to S and each solution is stored. So, the space complexity is O(S).