小白萌新 望前辈能够指点一二 dfs简单的剪枝

代码1:#include<bits/stdc++.h>

using namespace std;

int res=0;

void dfs(int n,int k,int ding){

if(n==0&&k==0) res++;

if(n<=0||k<=0) return ;//剪树枝

for(int i=ding;i<=n;i++){

dfs(n-i,k-1,i);

}

}

int main(){

int n,k; cin>>n>>k;

dfs(n,k,1);

cout<<res<<endl;

return 0;

} 代码2:#include<bits/stdc++.h>

using namespace std;

int n,m;

int ret=0;

void dfs(int c,int sum,int k){

if(c==m&&sum==n) ret++;

if(c>k||sum>n) return ;

for(int i=k;i<=n;i++){

dfs(c+1,sum+i,i);

}

}

int main(){

cin>>n>>m;

dfs(0,0,1);

cout<<ret<<endl;

} 请问代码1和代码2有什么本质的区别吗,为什么代码1正确而代码2 错误 问题链接:https://ac.nowcoder.com/acm/contest/952/A

全部评论
基本没区别,但是你的第二个return 条件 c>m 打成 c>k 了,并且第二种这样求和会导致for循环里i<=n这个条件不能剪枝,导致tle,建议参考第一种的求和方式,应该就能通过了
2 回复 分享
发布于 2024-01-28 17:29 广西

相关推荐

不愿透露姓名的神秘牛友
今天 13:05
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
07-03 16:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务