算法题：硬币问题

问题描述

有n种硬币，面值为别为a[1],a[2],a[3]……a[n]，每种都有无限多。给定非负整数s，可以选取多少个硬币使得面值和恰好为s？输出硬币数目最小值和最大值

输入格式

第1行n
第2行s
第3到n+2行为n种不同的面值

输出格式

第1行为最小值
第2行为最大值

样例

输入

3 
6 
1 
2 
3

输出

2
6

数据范围

1≤n≤100 1≤s≤10000 1≤a[i]≤s

解决方案

思路

有向无环图&动态规划

代码

#include <iostream>

using namespace std;

int n, s;
int a[105];
int dp_max[10005];
int dp_min[10005];

int dfs_min(int x) {

    if (dp_min[x])
        return dp_min[x];

    if (x == 0)
        return dp_min[x] = 0;

    int ans = 0x3f3f3f3f;
    for (int i = 0; i < n; ++i) {
        if (x >= a[i])
            ans = min(ans, dfs_min(x - a[i]) + 1);

    }

    return dp_min[x] = ans;
}

int dfs_max(int x) {
    if (dp_max[x])
        return dp_max[x];

    if (x == 0)
        return dp_max[x] = 0;

    int ans = -0x3f3f3f3f;
    for (int i = 0; i < n; ++i) {
        if (x >= a[i])
            ans = max(ans, dfs_max(x - a[i]) + 1);
    }

    return dp_max[x] = ans;
}

int main() {

    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    cout << dfs_min(s) << endl;
    cout << dfs_max(s) << endl;

    return 0;
}