DFS
- 思路：
- 从初始状态出发，下一步可能有多种状态；选其中一个状态深入，到达新的状态；直到无法继续深入，回退到前一步，转移到其他状态，然后再深入下去。最后，遍历完所有可以到达的状态，并得到最终的解。
- DFS通常使用递归来实现
- 弊端：
- 递归容易超时
- 大部分DFS搜索的题目都需要用到回溯的思路，其难度主要在于扩展子结点时如何构造停止递归并返回的条件。
递归
递归方法就是直接或间接地调用其自身
注意：
避免进入死循环
容易超时
递归 <——> 非递归，相互转化
回溯法
- 回溯法是一种采用深度优先方式进行搜索的算法，当搜索到某一步时，如果发现原先的选择不是最优选择或者达不到目标，就退回一步重新选择。
- 剪枝函数：（在回溯中用于减少子结点扩展的函数）
- 1、约束函数：是问题的可行解吗？
- 2、限界函数：确定是问题的可行解，但，是问题的最优解吗？
- 解题步骤：
- 1、如何递归
- 2、如何剪枝与回溯
一、计算阶乘（递归）
阶乘函数：
比如
- 3！=6
- 3！= 3*2*1 = 6
- 4！=24
- 4！= 4*3*2*1 = 24
- 5！=120
- 5！= 5*4*3*2*1 = 120
分析：
package no1_1;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
System.out.println(factorial(n));
}
public static int factorial(int n) {
if(n==0) {
return 1;
}else {
return n*factorial(n-1);
}
}
}二、数字游戏（回溯）
给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
分析：
package no1_1;
import java.util.Scanner;
public class Main {
//main()方法是静态方法，它只能调用静态方法，所以dfs()也是静态方法
//因为两个方法都是静态方法，所以它们共用的属性sum,N等都得是静态的
static int sum;
static int N;
static int arr1[];
static boolean flag = true;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
N = input.nextInt();
sum = input.nextInt();
int array[] = new int[N];
int usedArray[] = new int[N + 1];
//开始递归
dfs(0, array, usedArray, flag);
}
public static void dfs(int step, int arr[], int usedArray[], Boolean flag) {
//首先检查当前步数是否等于N，如果是，则表示已经生成了一个完整的排列(最顶层，有N个数的数组)
if (step == N) {
//复制该排列到新数组中
int arr1[] = new int[N];
for (int i = 0; i < N; i++) {
arr1[i] = arr[i];
}
//从上往下，计算该排列最终得到的数字
for (int i = 1; i < N; i++) {
for (int j = 0; j < N - i; j++) {
arr1[j] = arr1[j] + arr1[j + 1];
}
}
//某排列计算出的数字与题目符合
if (arr1[0] == sum) {
//把该排列输出到控制台
for (int x : arr) {
System.out.print(x + " ");
}
//停止递归
flag = false;
//回溯，但不再递归
return;
} else
//条件不满足，
//回溯，继续递归生成下一步的排列
return;
}
//继续递归，生成可能的排列
if (flag == true) {
//最初序列arr[i]，为1～N的一个排列
//在递归生成排列时，使用usedArray数组来标记已经使用过的数字，避免重复使用
for (int i = 1; i <= N; i++) {
if (usedArray[i] == 0) {
arr[step] = i;
usedArray[i] = 1;
dfs(step + 1, arr, usedArray, flag);
usedArray[i] = 0;//取消标记
}
}
}
return;
}
}
