基本上还是01背包，首先注意必须正好花光钱，所以初始化时除了dp[0]以外其他都要设置成inf，然后因为求方案数，所以基本方程为dp[i] = dp[i-x] + dp[i]，再根据inf进行一些特殊处理即得解
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 const int maxm = 10000 + 500; 6 const int inf = 0x7fffffff >> 1; 7 int dp[maxm]; 8 int n, m; 9 int x; 10 11 int main () { 12 scanf("%d %d", &n, &m); 13 for (int i = 1; i <= m; i++) dp[i] = inf; 14 dp[0] = 1; 15 for (int i = 1; i <= n; i++) { 16 scanf("%d", &x); 17 for (int j = m; j >= x; j--) { 18 if (dp[j - x] == inf) continue; 19 if (dp[j] == inf) dp[j] = dp[j-x]; 20 else dp[j] += dp[j-x]; 21 } 22 } 23 if (dp[m] == inf) printf("0"); 24 else printf("%d", dp[m]); 25 return 0; 26 }