超详细思路（以注释形式写在代码里）+代码

#include <bits/stdc++.h>
using namespace std;

int dp[45005]; // DP数组，dp[j]表示（√/×）凑出金额j
int a[105];    // 存储输入的货币面值
//和我的dp说去吧 
void solve(){
    // 初始化DP数组为0
    memset(dp, 0, sizeof(dp));
    int n;
    cin >> n;
    // 读入货币面值
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 将货币面值从小到大排序,实则贪心 
    sort(a + 1, a + 1 + n);
    
    int ans = 0; // 记录必要货币数量
    dp[0] = 1;   // 初始化（金额0总是可以凑出，必须夯） 
    
    // 遍历每种货币
    for (int i = 1; i <= n; i++){
        // 如果当前面值已经被其他货币组合表示，则忽略
        if (dp[a[i]] != 0) continue;
        // else当前货币是必要的
        ans++;
        // 完全背包-->更新DP数组
        // 从当前货币面值开始，更新能凑出的所有金额
        for (int j = a[i]; j <= 25000; j++){
            dp[j] |= dp[j - a[i]]; // 状态转移
        }
    }
    cout << ans << endl;
}

int main(){
    int T;
    cin >> T;
    while (T--){
        solve(); 
    }
}