Money Systems chapter 2.3 dp

dpdp始终是让我头疼，开始看着像背包问题，想了会列个状态方程 dp[n]=dp[n]+dp[money[i]];

后来一看不对应该是dp[n]=dp[n]+dp[n-money[i]];看来01背包问题还是没搞清楚,后的循环也有问题,我开始的外循环是总钱数,里循环才是硬币种类,

应该反过来.

 1 /*
 2 
 3 ID: hubiao cave
 4 
 5 PROG: money
 6 
 7 LANG: C++
 8 
 9 */
10 
11 
12 
13 
14 #include<iostream>
15 
16 #include<fstream>
17 
18 #include<string>
19 
20 using namespace std;
21 
22 
23 
24 int main()
25 
26 {
27 
28 
29     ifstream fin("money.in");
30 
31     ofstream fout("money.out");
32     int money[26];
33     int N,V;
34     long long dp[10002]={0};
35     fin>>V>>N;
36     for(int i=1;i<=V;i++)
37     {
38         fin>>money[i];
39 
40     }
41     dp[0]=1;
42     for(int i=1;i<=V;++i )
43     {
44         for(int j=1;j<=N;++j)
45         { 
46             if(j>=money[i])
47                 dp[j]=dp[j]+dp[j-money[i]];
48         }
49     }
50 
51     fout<<dp[N]<<endl;
52     
53     
54 
55     return 0;
56 
57 
58 }