虽然也是一道dp的入门题，但就是想不到，或者说不会实现。dp还是要多做题。
链接：https://www.luogu.org/problemnew/show/P1164
可以定义状态dp[i][j]表示考虑前i道菜，刚好花费j元的方案数。那么对于某个花费的方案数，这个花费加上一道菜的价格产生的新的花费的方案数，两个应该是相等的。则dp[i][j]+=dp[i-1][j-a[i]]就可以求出方案数。同样的，可以将空间占用降到一维。
1 #include<cstdio> 2 const int maxn=105,maxm=1e4+5; 3 int n,m,a[maxn],dp[maxm]; 4 int main() { 5 scanf("%d%d",&n,&m); 6 for(int i=1;i<=n;++i) scanf("%d",&a[i]); 7 dp[0]=1; 8 for(int i=1;i<=n;++i) 9 for(int j=m;j>=a[i];--j) 10 dp[j]+=dp[j-a[i]]; 11 printf("%d",dp[m]); 12 return 0; 13 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9589409.html
