有没有可能通过暴力破解之外的方法解题？
本题除了暴力破解的方法之外，我本想用排列组合的方法去提高一下效率，
比如将输入的整数n拆分成m个5和剩下的余数；于是5元钱可以用4种方法兑换，余数0,1,2,3,4也有固定的兑换方法次数，
但m个5之间的组合方式我无法求出，于是失败了。
有没有大佬能告诉我这有没有可能求出来？还是有其他不同的方法？
2020-01-22 19:18 江西师范大学 Java
关注
全部评论
WJack
惠州学院 安卓
用动态规划！ int dp(int s){
int dp[3][201];
int money[3]={1,2,5};
for(int i=0;i<=200;i++){
dp[0][i]=1;
}
dp[1][0]=1;
dp[2][0]=1;
for(int i=1;i<3;i++){
for(int s=1;s<=200;s++){
if(s-money[i]<0)dp[i][s]=dp[i-1][s];
else dp[i][s]=dp[i-1][s]+dp[i][s-money[i]];
}
}
return dp[2][s];
}
int main(){
int n;
cin>>n;
cout<<dp(n);
}
PeterWinchester
西北工业大学 C++
算了吧，会超时。 PeterWinchester
西北工业大学 C++
可以，深搜！
相关推荐
蔚来一面234人在聊
查看12道真题和解析 点赞 评论 收藏
分享