Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<string.h>
- int coins[100];
- int n;
- int impossible = 10000;
- int dp[1000];
- int decompose(int s) {
- if (dp[s] != -1)
- return dp[s];
- if (s == 0)
- return 0;
- int best = impossible;
- if (s < coins[n-1]) {
- dp[s] = impossible;
- return impossible;
- }
- for (int i = 0; i < n; i++) {
- if (s >= coins[i]) {
- int res = decompose(s - coins[i]) + 1;
- if (res < best)
- best = res;
- }
- }
- dp[s] = best;
- return best;
- }
- int main() {
- int s;
- memset(dp, -1, sizeof(dp));
- scanf("%d %d", &s, &n);
- for (int i = 0; i < n; i++)
- scanf("%d", &coins[i]);
- int result = decompose(s);
- printf("%d", (result == impossible)?-1:result);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement