**Problem description:**Lisa has a bunch of coins,The total is N,also There are some coins with different denominations(you can set the amount of sort),can you help lisa Put together coins with a total of N? If not,Lisa will look down on you.
My SolSolution:
include[HTML_REMOVED]
define INF 0x3f3f3f3f
using namespace std;
const int N=1e6+10;
int sort[N];int des;int sum;
int main(){
cin>>des;int dp[des]; //the des of sum you decide
for(int i=des;i>0;i–){
dp[i]=INF;
}
int p;//the sort you want add
cin>>p;
for(int i=p;i>0;i– ){
cin>> sort[i];
dp[sort[i]]=1;
}dp[0]=0;//ini
//matching
for(int i=1;i<=des;i){
int j=p;
while(j&&((i-sort[j])<=des)&&((i-sort[j])>0)){
dp[i]=min(dp[i],dp[i-sort[j]]+1);j–;
}
// for(int j=1,i-sort[j]<=des&&i-sort[j]>0;j<=p;j){
// dp[i]=min(dp[i],dp[i-sort[j]]+1);
// }
}
if(dp[des]!=INF)
cout << dp[des] << endl;
else cout<<”Your wishes cannot be fulfilled”;
}
/sample input
10
5
1 3 5 6 8
/
/sample output
2
/