检查多少个面值无法被其他面值组合出来

记忆化搜索

#include <bits/stdc++.h>
using namespace std;
int T;
int n;
int a[105];
bool book[25000 + 5][105]; // 如果算过了，存值
bool vis[25000 + 5][105];  // 表示每个 num no 有没有被算过
// 不使用 a[no] 的情况下，能不能表示出来 num
bool f(int num, int no)
{
    if (vis[num][no])
        return book[num][no];
    vis[num][no] = true;
    if (num == 0)
        return book[num][no] = true;
    for (int i = 1; i <= n; i++)
    {
        // 不能用自己
        if (i == no || a[i] > num)
            continue;
        // 检查 num-a[i] 能不能被表示出来
        if (f(num - a[i], no))
            return book[num][no] = true;
    }
    return book[num][no] = false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        int maxAi = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            maxAi = max(maxAi, a[i]);
        }
        for (int i = 0; i <= maxAi; i++)
            for (int j = 1; j <= n; j++)
                vis[i][j] = false;
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (!f(a[i], i))
                ans++;
        cout << ans << "\n";
    }
    return 0;
}

经典 dp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXAI = 25000;
int t, n;
int a[MAXN + 5];
bool dp[MAXAI + 5];
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int maxAi = a[n]; // 记录最大的面额
        int ans = 0;      // 记录简化后的货币系统大小（面额的数量）
        // dp[x] 表示 x 能否凑出来
        for (int i = 0; i <= maxAi; i++)
            dp[i] = false;
        dp[0] = true;
        // 从小到大枚举每个货币
        for (int i = 1; i <= n; i++)
        {
            // 当前货币的面额为 a[i]
            if (dp[a[i]] == true)
                continue;
            // 选择当前货币
            ans++;
            for (int j = a[i]; j <= maxAi; j++)
                dp[j] = dp[j] || dp[j - a[i]];
        }
        cout << ans << "\n";
    }
    return 0;
}