[打卡]开始dp

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int coin[5]={1,2,5,7,10};
 8     int num;
 9     while(cin>>num){
10         vector<int> dp(num+1,-1);
11         dp[0]=0;
12         for(int i=0; i<num; ++i)
13             for(int j=0; j<5; ++j)
14                 if(coin[j]<=i&&dp[i-coin[j]]!=-1)
15                     if(dp[i]==-1 || dp[i]>dp[i-coin[j]]+1)
16                         dp[i]=dp[i-coin[j]]+1;
17         cout << dp[num-1] <<endl;
18     }
19             
20     return 0;
21 }