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] denote whether it is possible to make a sum of x using the given coins.

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

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

Time Complexity: \mathcal{O}(SN)


Comments

There are no comments at the moment.