有没有可能通过暴力破解之外的方法解题?

本题除了暴力破解的方法之外,我本想用排列组合的方法去提高一下效率,
比如将输入的整数n拆分成m个5和剩下的余数;于是5元钱可以用4种方法兑换,余数0,1,2,3,4也有固定的兑换方法次数,
但m个5之间的组合方式我无法求出,于是失败了。
有没有大佬能告诉我这有没有可能求出来?还是有其他不同的方法?
全部评论
用动态规划! 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); }
2 回复
分享
发布于 2020-02-03 00:15
可以,深搜!
点赞 回复
分享
发布于 2020-01-24 19:52
联想
校招火热招聘中
官网直投
算了吧,会超时。
点赞 回复
分享
发布于 2020-01-24 19:58

相关推荐

头像
03-18 09:09
Java
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务