第17章 深搜的剪枝策略

1、找数字

算法分析

枚举每个位置选0还是选1，若长度超过19，则break
注意：第一个位置一定选1，其中dfs(num，cnt，len)，num该参数可以去掉，cnt必须用弄类型，long的最大值有19位

时间复杂度

import java.util.Scanner;

public class Main {
    static int n;
    static long ans = Long.MAX_VALUE;
    static void dfs(int num,long cnt,int len)
    {
        if(len >= 19) 
        {
            return;
        }
        if(cnt % n == 0) 
        {
            ans = Math.min(ans, cnt); 
            return;
        }
                //选0
        dfs(0,cnt * 10,len + 1);
        //选1
        dfs(1,cnt * 10 + 1,len + 1);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        
        dfs(1,1,1);
        System.out.println(ans);
    }
}

2、Betsy的旅行

算法分析

image.png

从该点出发，往四周进行深度优先搜索，搜索过程中，并记录当前走了多少步，若最后一步已经到达，并且还是在左下角，则ans++

由于该题目数据过小，直接搜索会卡一个数据，超时，因此使用打表的方法直接输出，把1到7的结果全部存起来，当n == 7时，会跑个4分钟左右，就懒得剪枝了hh

时间复杂度

时间复杂度不好分析

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 9;
    static int n;
    static int ans = 0;
    static int[] dx = new int[] {0,-1,0,1};
    static int[] dy = new int[] {-1,0,1,0};
    static int nums;//总方格数
    static boolean[][] st = new boolean[N][N];
    static void dfs(int x,int y,int cnt)
    {
        if(cnt == nums)
        {
            if(x == n - 1 && y == 0) ans ++;
            return;
        }
        for(int i = 0;i < 4;i ++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(st[a][b]) continue;
            st[a][b] = true;
            dfs(a,b,cnt + 1);
            st[a][b] = false;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        nums = n * n;
        st[0][0] = true;
        dfs(0,0,1);
        System.out.println(ans);
    }
}

Java代码 最终版

import java.util.Scanner;

public class Main {
    static int[] ans = new int[] {0,1,1,2,8,86,1770,88418};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        System.out.println(ans[n]);
    }
}