暴力递归算法面试题

001什么是暴力递归？

暴力递归是把问题转化为规模缩小的同类问题的子问题 ，有明确的不需要继续进行递归的条件(base case)，有当得到了子问题的结果之后的决策过程并且不记录每一个子问题的解。

002汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。
游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。
操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

思想
假设只有一个盘子

如果有两个盘子

// 1~i 圆盘 目标是from -> to， other是另外一个
public static void func(int N, String from, String to, String other) {
    if (N == 1) { // base
        System.out.println("Move 1 from " + from + " to " + to);
    } else {
        func(N - 1, from, other, to);
        System.out.println("Move " + N + " from " + from + " to " + to);
        func(N - 1, other, to, from);
    }
}

003字符串打印

打印一个字符串的全部子序列，包括空字符串
有字符串“abc”，字符串长度为3，下标分别是0,1,2。则决策的过程一共有三个，令初始序列为空字符串。分别是：
0：此时有两种情况，要不要'a'，如果要，子序列变为“a”；如果不要则还是空字符串；
1：此时有两种情况，要不要‘b’，加上上一步的两种这里就有4种情况，这里不一一列举；
2：此时有两种情况，要不要‘c’，加上上一步的四种情况这里就有8种情况。

public class PrintAllSubsquences {
    public static void pringAllSub(char[] str, int i, String res) {
        if (i == str.length) {
            System.out.println(res);
            return;
        }
        //两种情况
        pringAllSub(str, i + 1, res);
        pringAllSub(str, i + 1, res + str[i]);
    }
    public static void main(String[] args) {
        String str = "abc";
        pringAllSub(str.toCharArray(), 0, "");
    }
}

004N皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

思路
1. 准备一个数组record[i]，record[i] 表示 i行的皇后，放在了第几列
2. 如果第一个皇后的在i1行j1列，第二个皇后在i1行j2列，那么应该满足的条件是
       不能共斜线：|i1-i2|不等于|j1-j2|   
       不能共行： i1不等于i2   
       不能共列：j1不等于j2

public class NQueens {
    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n]; // record[i] -> i行的皇后，放在了第几列
        return process1(0, record, n);
    }
    // 返回值是，摆完所有的皇后，合理的摆法有多少种
    public static int process1(int i, int[] record, int n) {
        if (i == n) { // 终止行
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) { // 当前行在i行，尝试i行所有的列  -> j
            // 当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行共列或者共斜线，
            // 如果是，认为有效
            // 如果不是，认为无效
            if (isValid(record, i, j)) {
                record[i] = j;
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }
    // 返回i行皇后，放在了j列，是否有效
    public static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) { // 之前的某个k行的皇后
            if ((j == record[k]) ||(Math.abs(record[k] - j) == Math.abs(i - k))) {
                return false;
            }
        }
        return true;
    }
}

005爬楼梯问题

小明走楼梯，一次可以跨两个台阶，也可以跨一个台阶，求有n个台阶，一共有多少种跨发？
从问题中我们可以分析出，如果迈上最后一个台阶，可以是一步，也可以是两步。

分析：

可以理解为：
f(n)=f(n-1)+f(n-2)
同理：
f(n-1)=f(n-1-1）+f(n-1-2)
f(n-2)=f(n-2-1)+f(n-2-2）
. …
…
f(4)=f(3)+f(2)
f(3)=f(2)+f(1)
f(2)=2
f(1)=1

int getNum(int n) {
    if (n <= 0)return 0;	
    if (n == 1) return 1;
    if (n == 2) return 2;
    int arr = new int[n+1];
    arr[1] = 1;
    arr[2] = 2;
    for (int i = 3; i <= n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    int ret = arr[n];
    return ret;
}