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]$ ~dp[c][v]~ be the number of ways to get $v$ ~v~ with the first $c$ ~c~ coins. Initially, $dp[0][0] = 1$ ~dp[0][0] = 1~. Thus our DP state transition is $dp[c][v] = dp[c-1][v]+dp[c-1][v-A[c]]$ ~dp[c][v] = dp[c-1][v]+dp[c-1][v-A[c]]~, where $A[c]$ ~A[c]~ is the value of the $c^\text{th}$ ~c^\text{th}~ coin.

Time Complexity: $\mathcal O(NT)$ ~\mathcal O(NT)~

Solution 2 — Brute Force

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

Time Complexity: $\mathcal O(N 2^N)$ ~\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)$ ~\mathcal O(2^N)~ subsets of the coins.

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

Comments

There are no comments at the moment.