Editorial for A Coin Problem

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.

Author: Ninjaclasher

This is a very classical dynamic programming problem.

Let $dp[x]$ ~dp[x]~ denote whether it is possible to make a sum of $x$ ~x~ using the given coins.

$dp[x]$ ~dp[x]~ would be true if any of $dp[x-c_i]$ ~dp[x-c_i]~ is true.

Thus, after computing the DP table, we can check $dp[S]$ ~dp[S]~ to determine whether we can make a sum of $S$ ~S~ or not.

Time Complexity: $\mathcal{O}(SN)$ ~\mathcal{O}(SN)~

Comments

There are no comments at the moment.