以前見過這類問題，都是用母函數給水過去的，這個應該也能用母函數水過（猜測）。母函數復雜度高，記得見過一種更高效的DP方式，非常神奇只是改變了一下dp的順序就把重復給去掉了。一種一直遞推到v種，這樣更新是無重復的,這樣遞推是假設最后一個是c[i]，以前的狀態中都沒有含有c[i]的情況。

1 /* 2 ID: cuizhe 3 LANG: C++ 4 TASK: money 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <cmath> 10 #include <algorithm> 11 using namespace std; 12 long long dp[10001],c[30]; 13 int main() 14 { 15 int i,n,j,v; 16 freopen("money.in","r",stdin); 17 freopen("money.out","w",stdout); 18 scanf("%d%d",&v,&n); 19 for(i = 1;i <= v;i ++) 20 scanf("%d",&c[i]); 21 sort(c+1,c+v+1); 22 dp[0] = 1; 23 for(i = 1;i <= v;i ++) 24 { 25 for(j = c[i];j <= n;j ++) 26 { 27 dp[j] += dp[j-c[i]]; 28 } 29 } 30 printf("%lld\n",dp[n]); 31 return 0; 32 }

轉載于:https://www.cnblogs.com/naix-x/archive/2012/11/13/2767430.html

總結

以上是生活随笔為你收集整理的USACO 2.3 Money Systems(DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。