暴力递归就是尝试
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件（base case）
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
一定要学会怎么去尝试，因为这是动态规划的基础
汉诺塔问题
打印 n 层汉诺塔从最左移动到最右的全部过程
思路：
所有的过程都可以简化为：
- 初始的情况为
- 左：1 ~ n
- 中：0
- 右：0
- 把除了第 n 层以外的从左柱子移动到中间的柱子
- 把第 n 层从左柱子移动到右柱子，此时 n 移动完成。现在的情况为
- 左：0
- 中：1 ~ (n - 1)
- 右：n
- 把除了第 n-1 层以外的从中间柱子移动到左柱子
- 把第 n-1 层从中间柱子移动到右柱子，此时 n-1 移动完成。现在的情况为
- 左：1 ~ (n - 2)
- 中：0
- 右：n、(n - 1)
重复
步骤 2 ~ 步骤 5直到所有移动完成public class Hanoi {static int num;static int hanoi(int n) {num = 0;return process(n, "左", "右", "中");}static int process(int i, String right, String left, String mid) {if (i == 1) {System.out.println("1\t" + right + " => " + left);return 1;} else {// 把 i 以外都放到中间的柱子上num += process(i - 1, right, mid, left);System.out.println(i + "\t" + right + " => " + left);// 把 i 以外都从中间的柱子放到左边的柱子上num += process(i - 1, mid, left, right);}return num;}public static void main(String[] args) {System.out.println(hanoi(3));}}
结果
1 左 => 右 2 左 => 中 1 右 => 中 3 左 => 右 1 中 => 左 2 中 => 右 1 左 => 右 6字符串子序列
打印一个字符串的全部子序列，包括空字符串
// 输入
abc
// 输出
abc,ab,ac,bc,a,b,c,空
思路：abc每个字母都有是否要选择
public class PrintAllSubsquence {
private static String s;
static void printAllSubsquence(String str) {
s = str;
process("", -1, false);
}
static void process(String cur, int i, boolean flag) {
if (i == s.length() - 1) {
if (flag) cur += s.charAt(i);
System.out.println("".equals(cur) ? "空" : cur);
return;
}
if (flag) cur += s.charAt(i);
process(cur, i + 1, true);
process(cur, i + 1, false);
}
public static void main(String[] args) {
printAllSubsquence("abc");
}
}
结果
abc
ab
ac
a
bc
b
c
空
字符串全排列
给定一个字符串，返回这个字符串的全部排列，要求不重复
// 输入
abc
// 输出
abc, acb, bac, bca, cab, cba
思路：
import java.util.ArrayList;
import java.util.List;
public class AllPermutations {
static List<String> allPermutations(String str) {
List<String> list = new ArrayList<>();
process(0, str.toCharArray(), list);
return list;
}
static void process(int index, char[] chars, List<String> list) {
if (index == chars.length) {
list.add(new String(chars));
}
for (int i = index; i < chars.length; i++) {
swap(i, index, chars);
process(index + 1, chars, list);
// 这里一定要换回来
swap(i, index, chars);
}
}
private static void swap(int i, int j, char[] chars) {
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
}
public static void main(String[] args) {
System.out.println(allPermutations("abc"));
}
}
结果
[abc, acb, bac, bca, cba, cab]
上面的代码已经可以完成没有重复字母的字符串全排列，但如果字符串是类似 “aabc”就会出现重复，如下
[aabc, aacb, abac, abca, acba, acab, aabc, aacb, abac, abca, acba, acab, baac, baca, baac, baca, bcaa, bcaa, caba, caab, cbaa, cbaa, caba, caab]
要在该代码基础上增加去重的功能，只需要在做交互时保证要交互的两个字母不同即可
当然，如果直接放到 set 中就可以去重，但是和原先的代码复杂度相同。增加判断的话可以在逻辑上减少很多递归分支，性能上会提升很多
import java.util.ArrayList;
import java.util.List;
public class AllPermutations {
static List<String> allPermutations(String str) {
List<String> list = new ArrayList<>();
process(0, str.toCharArray(), list);
return list;
}
static void process(int index, char[] chars, List<String> list) {
if (index == chars.length) {
list.add(new String(chars));
}
boolean[] visit = new boolean[26];
for (int i = index; i < chars.length; i++) {
if (!visit[chars[i] - 'a']) {
visit[chars[i] - 'a'] = true;
swap(i, index, chars);
process(index + 1, chars, list);
// 这里一定要换回来
swap(i, index, chars);
}
}
}
private static void swap(int i, int j, char[] chars) {
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
}
public static void main(String[] args) {
System.out.println(allPermutations("aabc"));
}
}
结果
[aabc, aacb, abac, abca, acba, acab, baac, baca, bcaa, caba, caab, cbaa]
拿纸牌
给定一个整型数组 arr，代表数值不同的纸牌排成一条线。玩家 A 和玩家 B 依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家 A 和玩家 B 都绝顶聪明。请返回最后获胜者的分数。
【举例】
arr = [1,2,100,4]
开始时，玩家A只能拿走 1 或 4。如果开始时玩家 A 拿走 1，则排列变为 [2,100,4]，接下来玩家 B 可以拿走 2 或 4，然后继续轮到玩家A……如果开始时玩家A拿走4，则排列变为 [1,2,100]，接下来玩家 B 可以拿走 1 或 100，然后继续轮到玩家A…… 玩家 A 作为绝顶聪明的人不会先拿 4，因为拿 4 之后，玩家 B 将拿走100。所以玩家A会先拿1，让排列变为 [2,100,4]，接下来玩家 B 不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。
arr=[1,100,2]
开始时，玩家 A 不管拿 1 还是 2，玩家 B 作为绝顶聪明的人，都会把100拿走。玩家B会获胜,分数为100。所以返回100。
思路：
由于AB两人的设定为“聪明绝顶”，所以在拿纸牌时一定会出现如下状况
- A 先手拿牌，保证自己
所拿牌 + 剩下的牌中自己能拿到的牌最大 B 后手拿牌，保证
剩下的牌 A 能拿到的最小。由于后手拿牌，这个地方只能去限制 A，而不是去保证自己在接下来的拿牌中能拿到最大，因为如果自己能拿到最大的，A 一定能拿到public class CardsInLine { static int cardsInLine(int[] cards) { if (cards == null || cards.length == 0) return 0; return Math.max(first(cards, 0, cards.length - 1), secend(cards, 0, cards.length - 1)); } /** * 先手拿牌 */ static int first(int[] cards, int L, int R) { if (L == R) return cards[L]; return Math.max(cards[L] + secend(cards, L + 1, R), cards[R] + secend(cards, L, R - 1)); } /** * 后手拿牌 */ static int secend(int[] cards, int L, int R) { if (L == R) return 0; return Math.min(first(cards, L + 1, R), first(cards, L, R - 1)); } public static void main(String[] args) { System.out.println(cardsInLine(new int[]{1, 2, 100, 4})); System.out.println(cardsInLine(new int[]{1, 100, 2})); } }结果
101 100栈的逆序
给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归
思路：
定义两个函数：
- 函数一：返回栈底元素
- 函数二：将返回的栈底元素逆序放入栈中 ```java import java.util.Stack;
public class ReverseStack {
static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) return;
int num = process(stack);
reverse(stack);
stack.push(num);
}
static int process(Stack<Integer> stack) {
Integer num = stack.pop();
if (stack.isEmpty()) {
return num;
} else {
int next = process(stack);
stack.push(num);
return next;
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println(stack);
reverse(stack);
System.out.println(stack);
}
}
结果
[1, 2, 3, 4, 5] [5, 4, 3, 2, 1]
<a name="vO4iH"></a>
# 字符串转化
规定1和A对应、2和B对应、3和C对应...<br />那么一个数字字符串比如“111”，就可以转化为“AAA”、“KA”和“AK”。<br />给定一个只有数字字符组成的字符 str，返回有多少种转化结果。
思路：<br />遍历字符串，求出下标 i 之后字符串有多少种转化方式，然后相加。注意点：
- 0 是没有单独的转化的，只能是组成成为 10，如果是 01，02，03 这种也是不能转化的
- 1 和其他的数字都能组合转化
- 2 和其他的数字组合时必须要小于等于 26
```java
public class ConvertToLetterString {
static int convertToLetterString(String str) {
if (str == null || str.length() == 0) return 0;
return process(str.toCharArray(), 0);
}
/**
* 在 i 位置之前如何转化已经有结果了
*
* @param chars
* @param i
* @return 在 i 之后的位置有多少种转化的结果
*/
static int process(char[] chars, int i) {
if (i == chars.length) {
// 来到了最后，之前刚刚转化了一种情况
return 1;
}
if (chars[i] == '0') {
// 单个 0 是不能被转化的
return 0;
}
if (chars[i] == '1') {
int res = process(chars, i + 1); // i 视为转化部分，求后续的转化结果
if (i + 1 < chars.length) {
res += process(chars, i + 2); // (i i+1) 视为转化部分，求后续的转化结果
}
return res;
}
if (chars[i] == '2') {
int res = process(chars, i + 1); // i 视为转化部分，求后续的转化结果
if (i + 1 < chars.length && (chars[i + 1] >= '0' && chars[i + 1] <= '6')) {
// (i i+1) 视为转化部分且不能超过 26，求后续的转化结果
res += process(chars, i + 2);
}
return res;
}
return process(chars, i + 1);
}
public static void main(String[] args) {
System.out.println(convertToLetterString("111"));
}
}
结果
3
装东西
给定两个长度都为 N 的数组 weights 和 values，weights[i] 和 values[i] 分别代表 i 号物品的重量和价值。给定一个正数 bag，表示一个载重 bag 的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
思路：每个物品都分成 放入包中 和 不放入包中 两种情况
public class Knapsack {
static int[] weights;
static int[] values;
static int bag;
static int knapsack(int[] weights, int[] values, int bag) {
Knapsack.weights = weights;
Knapsack.values = values;
Knapsack.bag = bag;
return process(0, 0, 0);
}
/**
* @param i 下标
* @param sumV 总的价值
* @param sumW 总的重量
* @return
*/
static int process(int i, int sumV, int sumW) {
if (i == weights.length) {
return sumV;
}
int sum1 = sumV;
// 装 i
if (sumW + weights[i] <= bag) {
sum1 = process(i + 1, sumV + values[i], sumW + weights[i]);
}
int sum2 = sumV;
// 不装 i
if (i + 1 < weights.length) {
sum2 = process(i + 1, sumV, sumW);
}
return Math.max(sum1, sum2);
}
public static void main(String[] args) {
int[] weights = new int[]{1, 2, 3, 4, 5, 6};
int[] values = new int[]{2, 3, 4, 2, 2, 12};
int knapsack = knapsack(weights, values, 6);
System.out.println(knapsack);
}
}
结果
12
另一种写法：
public class Knapsack1 {
static int[] weights;
static int[] values;
static int bag;
static int knapsack(int[] weights, int[] values, int bag) {
Knapsack1.weights = weights;
Knapsack1.values = values;
Knapsack1.bag = bag;
return process(0, 0);
}
/**
* 第 i 物品是否要放入包中
*
* @param i 下标
* @param alreadyWeight 放入包中的总重
* @return
*/
static int process(int i, int alreadyWeight) {
// 总重量超过 i 物品不放入
if (alreadyWeight > bag) {
return -values[i - 1];
}
if (i == weights.length) return 0;
return Math.max(
// 放入 i 物品
values[i] + process(i + 1, alreadyWeight + weights[i]),
// 不放 i 物品
process(i + 1, alreadyWeight)
);
}
public static void main(String[] args) {
int[] weights = new int[]{1, 2, 3, 4, 5, 6};
int[] values = new int[]{2, 3, 4, 2, 2, 12};
int knapsack = knapsack(weights, values, 6);
System.out.println(knapsack);
}
}
N 皇后
N 皇后问题是指在 N * N 的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。给定一个整数 n，返回 n 皇后的摆法有多少种。
n=1，返回 1。
n=2 或 3，2皇后和3皇后问题无论怎么摆都不行，返回0。
n=8，返回92。
思路：
使用一个二维数组记录皇后的位置，确保每一个皇后不同行、不同列，也不在同一条斜线上
优化：
使用一个一维数组就可以记录皇后的位置，如 record[2] = 3 代表了在 [2,3] 位置（第 2 行第 3 列）上存在皇后
public class NQueens {
static int getNum(int n) {
if (n < 1) return 0;
int[] record = new int[n];
return process(0, record, n);
}
/**
* @param i 第 i 行
* @param record 保存皇后的位置
* @param n 棋盘
* @return 有多少摆法
*/
private static int process(int i, int[] record, int n) {
if (i == n) return 1;
int res = 0;
for (int j = 0; j < n; j++) {
if (isValid(record, i, j)) {
record[i] = j;
res += process(i + 1, record, n);
}
}
return res;
}
// 检查当前 [i,j] 是否也其他的皇后 不同行、不同列，也不在同一条斜线上
private static boolean isValid(int[] record, int i, int j) {
// 在一维数组中天然不同行
for (int k = 0; k < i; k++) {
if (
// 不同列
j == record[k] ||
// 不同斜线
Math.abs(record[k] - j) == Math.abs(i - k)
) {
return false;
}
}
return true;
}
public static void main(String[] args) {
for (int i = 1; i < 9; i++) {
System.out.println(i + "\t" + getNum(i));
}
}
}
结果
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
以上算法已经解决了N皇后问题，但是复杂度为 
，效率很低，如何能够优化呢？
思路：使用位运算来优化以上算法
使用二进制的每一位来代替 record 数组
public class NQueens {
static int getNum(int n) {
// 由于使用 位运算 来优化，如果超过 32 位需要用 long 类型
if (n < 1 || n > 32) return 0;
// 得到一个前 n 位为 1 的二进制数
int limit = n == 32 ? -1 : (1 << n) - 1;
return process(limit, 0, 0, 0);
}
/**
* @param limit
* @param colLim 列的限制，1 不能放皇后，0 能放
* @param leftDiaLim 左斜线的限制，1 不能放皇后，0 能放
* @param rightDiaLim 右斜线的限制，1 不能放皇后，0 能放
* @return
*/
private static int process(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
if (colLim == limit) return 1;
// colLim | leftDiaLim | rightDiaLim => 就是总的限制
// ~(总的限制) => 总限制求反
// limit & 总限制求反 => 就是获取到 除了所有限制之外其他的能放皇后的位置
int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
int res = 0;
// 轮询依次在每个位置放皇后
while (pos != 0) {
// 最右侧的 1
int mostRightOne = pos & (~pos + 1);
pos = pos - mostRightOne;
res += process(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
}
return res;
}
public static void main(String[] args) {
for (int i = 1; i < 9; i++) {
System.out.println(i + "\t" + getNum(i));
}
}
}
若有收获，就点个赞吧
0 人点赞
