📑前言
本文主要是【算法】——dfs使用的文章，如果有什么需要改进的地方还请大佬指出⛺️
🎬作者简介：大家好，我是听风与他🥇
☁️博客首页：CSDN主页听风与他
🌄每日一句：狠狠沉淀，顶峰相见
dfs-剪枝
- 整数n划分成k份的方案
package 搜索;
import java.util.Scanner;
public class dfs_剪枝 {
static int ans;//记录总次数
static int cnt;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int k = sc.nextInt();
ans=0;
cnt=0;
dfs(n, k, 1, "");
System.out.println("方案数"+ans);
System.out.println("调用次数"+cnt);
}
}
/**
* 整数n划分成k份的方案
* @param n 待划分的数
* @param k 份数
* @param min 要保证唯一 1 1 5 和 5 1 1 是等价的，构建非降序，min是目前被拆分使用的最大的数
* @param fanan 记录详细划分的方案数
*/
public static void dfs(int n,int k,int min,String fanan) {
cnt++;//只要进入dfs,调用次数就+1
if(k==1 && min<=n) {
ans++;
System.out.println(fanan+n);
return;
}
if(min*k>n) return;
for(int i=min;i<=n;i++) {
dfs(n-i, k-1, i, fanan+i+"+");
}
}
}
dfs-整数划分
package 搜索;
public class dfs_整数划分 {
public static void main(String[] args) {
// TODO Auto-generated method stub
dfs(4, 0, 0, "");
}
/**
* DFS模拟整数的划分
* @param n 要拆分的原始的数
* @param nowget 目前已经得到的值，到n就game over
* @param maxused 实时的记录目前拆分已经用到的最大值 4 = 3 + 1
* @param ans 具体的拆分方案
*/
public static void dfs(int n,int nowget,int maxused,String ans) {
if(nowget==n) {
System.out.println(ans.substring(0, ans.length()-1));
return;
}
for(int i=1;i<=n-nowget;i++) {
//目标累加到n,已经累加到了nowget
if(i>=maxused)dfs(n, nowget+i, i, ans+i+"+");
}
}
}
📑文章末尾
