Editorial for Summer Institute '17 Contest 1 P8 - Mo' Money


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: d, Kirito

There are three possible solutions to this problem:

Solution 1 — Dynamic Programming

This problem can be solved with dynamic programming. Let dp[c][v] be the number of ways to get v with the first c coins. Initially, dp[0][0] = 1. Thus our DP state transition is dp[c][v] = dp[c-1][v]+dp[c-1][v-A[c]], where A[c] is the value of the c^\text{th} coin.

Time Complexity: \mathcal O(NT)

Solution 2 — Brute Force

Notice that N is rather small. Thus we can generate all \mathcal O(2^N) subsets of the coins, and count how many of these subsets sum to T.

Time Complexity: \mathcal O(N 2^N)

Solution 3 — Recursion

Write a recursive function that has two parameters, the current index and the sum so far. This function will iterate through all \mathcal O(2^N) subsets of the coins.

Time Complexity: \mathcal O(2^N)


Comments

There are no comments at the moment.