蓝桥杯-dfs(一)

本文介绍: dfs-剪枝

📑前言

本文主要是【算法】——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+"+");
		}
	}
}