[TOC]
# 1 暴力递归、动态规划
## 1.1 暴力递归思维
**==暴力递归实质就是尝试==**
> 概念解释：
> 回溯-表示大问题被拆解为小问题，小问题返回给大问题信息，就是回溯
> 分治：大问题被拆解成小的子问题，就是分治
1、把问题转化为规模缩小了的同类问题的子问题
2、有明确的不需要继续进行递归的条件（base case）
3、有当得到了子问题的结果之后的决策过程
4、不记录每个子问题的解（如果记录每个子问题的解，就是我们熟悉的动态规划）
### 1.1.1 暴力递归下的尝试
#### 1.1.1.1 例一：汉诺塔问题
打印n层汉诺塔从最左边移动到最右边的全部过程
> 汉诺塔圆盘移动，如果杆子上没有圆盘，可以移动到该杆，如果有圆盘则必须移动比该圆盘小的圆盘到该圆盘上
> 思路1：1、先想办法把1到N-1层圆盘移动到中间杆 2、再把N层的圆盘移动到最右侧的杆上 3、把1到N-1个圆盘从中间杆移动到最右侧。结束
> 思路2：忘掉左中右，理解为从from移动到to，from和to都有可能是左中右。所以定义from，to，other三个杆子。1、把1到N-1移动到other上。2、把第N层移动到to上。3、把1到N层从other移动到to上。结束
> 思路3：递归改非递归实现
> N层汉诺塔，从左移动到右最优步数是2^N - 1 步。递归公式 T(N) = T(N-1) + 1 + T(N-1)。化简为等比数列，高中数学内容
尝试是有优劣之分的，譬如思路1和思路二。在动态规划章节，可以用动态规划优化我们的尝试到最优版本
```Java
package class11;
import java.util.Stack;
public class Code01_Hanoi {
// 按照思路1的方法
public static void hanoi1(int n) {
leftToRight(n);
}
// 请把1~N层圆盘 从左 -> 右
public static void leftToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from left to right");
return;
}
leftToMid(n - 1);
System.out.println("Move " + n + " from left to right");
midToRight(n - 1);
}
// 请把1~N层圆盘 从左 -> 中
public static void leftToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from left to mid");
return;
}
leftToRight(n - 1);
System.out.println("Move " + n + " from left to mid");
rightToMid(n - 1);
}
public static void rightToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from right to mid");
return;
}
rightToLeft(n - 1);
System.out.println("Move " + n + " from right to mid");
leftToMid(n - 1);
}
public static void midToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to right");
return;
}
midToLeft(n - 1);
System.out.println("Move " + n + " from mid to right");
leftToRight(n - 1);
}
public static void midToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to left");
return;
}
midToRight(n - 1);
System.out.println("Move " + n + " from mid to left");
rightToLeft(n - 1);
}
public static void rightToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from right to left");
return;
}
rightToMid(n - 1);
System.out.println("Move " + n + " from right to left");
midToLeft(n - 1);
}
// 思路二：暴力递归 from to other
public static void hanoi2(int n) {
if (n > 0) {
func(n, "left", "right", "mid");
}
}
// 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);
}
}
public static class Record {
public boolean finish1;
public int base;
public String from;
public String to;
public String other;
public Record(boolean f1, int b, String f, String t, String o) {
finish1 = false;
base = b;
from = f;
to = t;
other = o;
}
}
// 思路三：非递归实现
public static void hanoi3(int N) {
if (N < 1) {
return;
}
Stack<Record> stack = new Stack<>();
stack.add(new Record(false, N, "left", "right", "mid"));
while (!stack.isEmpty()) {
Record cur = stack.pop();
if (cur.base == 1) {
System.out.println("Move 1 from " + cur.from + " to " + cur.to);
if (!stack.isEmpty()) {
stack.peek().finish1 = true;
}
} else {
if (!cur.finish1) {
stack.push(cur);
stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
} else {
System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
}
}
}
}
public static void main(String[] args) {
int n = 3;
hanoi1(n);
System.out.println("============");
hanoi2(n);
System.out.println("============");
hanoi3(n);
}
}
```
#### 1.1.1.2 例二：字符串子序列问题
1、打印一个字符串的全部子序列
> 子串：必须是连续的，用for循环就行
> 子序列：比子串自由，在原始序列的基础上，以此拿字符但是可以不连续
- 见process1方法代码
2、打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
> 比如aaabcccc就会得到很多相同字面值的子序列，我们把重复字面值的子序列只要一个
- 见process2方法代码
```Java
package class11;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class Code02_PrintAllSubsquences {
public static List<String> subs(String s) {
char[] str = s.toCharArray();
String path = "";
List<String> ans = new ArrayList<>();
process1(str, 0, ans, path);
return ans;
}
// str固定，不变
// index此时来到的位置, 要 or 不要
// 如果index来到了str中的终止位置，把沿途路径所形成的答案，放入ans中
// 之前做出的选择，就是沿途路径path
public static void process1(char[] str, int index, List<String> ans, String path) {
if (index == str.length) {
ans.add(path);
return;
}
String no = path;
process1(str, index + 1, ans, no);
String yes = path + String.valueOf(str[index]);
process1(str, index + 1, ans, yes);
}
public static List<String> subsNoRepeat(String s) {
char[] str = s.toCharArray();
String path = "";
HashSet<String> set = new HashSet<>();
process2(str, 0, set, path);
List<String> ans = new ArrayList<>();
for (String cur : set) {
ans.add(cur);
}
return ans;
}
// str index 用set去重
public static void process2(char[] str, int index,
HashSet<String> set, String path) {
if (index == str.length) {
set.add(path);
return;
}
String no = path;
process2(str, index + 1, set, no);
String yes = path + String.valueOf(str[index]);
process2(str, index + 1, set, yes);
}
public static void main(String[] args) {
String test = "aacc";
List<String> ans1 = subs(test);
List<String> ans2 = subsNoRepeat(test);
for (String str : ans1) {
System.out.println(str);
}
System.out.println("=================");
for (String str : ans2) {
System.out.println(str);
}
System.out.println("=================");
}
}
```
#### 1.1.1.3 例四：字符串全排列问题
1、打印一个字符串的全部排列,process
2、打印一个字符串的全部排列，要求不要出现重复的排列.process2。方法1，可以用HashSet最后去重，该方式是把递归的所有结果进行筛选。方法2可以抛弃重复元素，例如a在0位置已经尝试完毕，再有一个元素也是a要到0位置，那么禁止，该方法是递归的时候事先判断要不要进行下一步递归，更快一点。该方法又叫分支限界
```Java
package class11;
import java.util.ArrayList;
import java.util.List;
public class Code03_PrintAllPermutations {
public static ArrayList<String> permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process(chs, 0, res);
return res;
}
// str[0..i-1]已经做好决定的
// str[i...]都有机会来到i位置
// i到达终止位置，str当前的样子，就是一种结果 -> ans
public static void process(char[] str, int i, ArrayList<String> ans) {
// i来到终点，返回该种答案
if (i == str.length) {
ans.add(String.valueOf(str));
}
// 如果i没有终止，i... 都可以来到i位置
for (int j = i; j < str.length; j++) { // i后面所有的字符都有机会来到i位置
swap(str, i, j);
process(str, i + 1, ans);
// 恢复交换之前的现场
swap(str, i, j);
}
}
public static ArrayList<String> permutationNoRepeat(String str) {
ArrayList<String> res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process2(chs, 0, res);
return res;
}
// str[0..i-1]已经做好决定的
// str[i...]都有机会来到i位置
// i终止位置，str当前的样子，就是一种结果 -> ans
public static void process2(char[] str, int i, ArrayList<String> res) {
if (i == str.length) {
res.add(String.valueOf(str));
return;
}
boolean[] visit = new boolean[26]; // visit[0 1 .. 25] 代表a-z的字符有没有在当前出现过
// i右边的字符都有机会
for (int j = i; j < str.length; j++) {
// str[j] = 'a' -> 0 visit[0] -> 'a'
// str[j] = 'z' -> 25 visit[25] -> 'z'
// 如果没出现过就没有机会
if (!visit[str[j] - 'a']) {
visit[str[j] - 'a'] = true;
swap(str, i, j);
process2(str, i + 1, res);
swap(str, i, j);
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
String s = "aac";
List<String> ans1 = permutation(s);
for (String str : ans1) {
System.out.println(str);
}
System.out.println("=======");
List<String> ans2 = permutationNoRepeat(s);
for (String str : ans2) {
System.out.println(str);
}
}
}
```
#### 1.1.1.4 例六：用递归逆序一个栈(考验脑回路)
给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？
> 思路，先不要想着逆序它，实现一个f函数，f函数的作用是把栈传进去，想办法拿到栈低元素并返回。
```Java
package class11;
import java.util.Stack;
public class Code04_ReverseStackUsingRecursive {
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
// i是栈底元素，f调整之后的栈成为去掉栈底元素后的栈
int i = f(stack);
// 递归调用
reverse(stack);
// 经过base case之后，栈为空，此时压入的就是当前的栈底
stack.push(i);
}
public static int f(Stack<Integer> stack) {
// 弹出栈顶，用result临时变量记住这个栈顶元素
int result = stack.pop();
// 如果栈为空，向上返回弹出的result，此时result就是栈底元素
if (stack.isEmpty()) {
return result;
} else {
// 此时栈不为空，让子问题给我一个临时变量，临时变量就是子问题base case返回的result
int last = f(stack);
// 把我弹出的result再压入栈，向上返回子问题给我的result
stack.push(result);
return last;
}
}
public static void main(String[] args) {
Stack<Integer> test = new Stack<Integer>();
test.push(1);
test.push(2);
test.push(3);
test.push(4);
test.push(5);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
}
```
## 1.2 动态规划模型
> 以下代码有些已经实现了动态递归，看不懂没关系，下一章详细解释。可以先不管，回过头再看
### 1.2.1 从左往右尝试模型
#### 1.2.1.1 数字字符转化问题
> 注：facebook面试题
1、规定1和A对应，2和B对应，3和C对应...。那么一个数字字符比如"111"就可以转化为："AAA","KA","AK"。
给定一个只有数字字符组成的字符串str,返回有多少种转化结果
> 思路：根据从左往右，我们划分多大，来尝试，比如111，我们尝试一个1，为"A",剩下两个1去继续尝试。如果我们两个1尝试，就是"K"。三个1超过26字符，无法尝试。继续如此周而复始
```Java
package class11;
public class Code06_ConvertToLetterString {
public static int number(String str) {
if (str == null || str.length() == 0) {
return 0;
}
// i初始为0，表示0位置往后有多少中转化结果
return process(str.toCharArray(), 0);
}
// str[0...i-1]已经转化完了，固定了
// i之前的位置，如何转化已经做过决定了, 不用再关心
// i... 有多少种转化的结果
public static int process(char[] str, int i) {
// i和字符串长度一样大，右侧没有字符了。找到1中转化是0~n-1位置的转化
if (i == str.length) { // base case
return 1;
}
// i之前的决策，让当前i位置单独面对一个0字符，那么之前决策错误，返回0
// 例如10先转化为A，2位置是0字符无法转化，当前决策无效
// 而10直接转化为J,直接到终止位置，返回一种转化J
if (str[i] == '0') {
return 0;
}
// i位置如果是1或者2，有可能和下一个位置共同转化，因为字符数为0~26
// 反之3~9超过26不需要决策
// str[i] 如果是1，总是有两个选择，因为最大为19，不超过26
if (str[i] == '1') {
int res = process(str, i + 1);
if (i + 1 < str.length) {
res += process(str, i + 2);
}
return res;
}
// str[i] 如果是2，那么有可能有两种选择，需要看是否朝贡国26
if (str[i] == '2') {
int res = process(str, i + 1);
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
res += process(str, i + 2); // (i和i+1)作为单独的部分，后续有多少种方法
}
return res;
}
// str[i] 在3~9的位置，下个位置必须决策一种选择
return process(str, i + 1);
}
public static int dpWays2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[] dp = new int[N+1];
dp[N] = 1;
for(int i = N-1; i >= 0; i--) {
if (str[i] == '0') {
dp[i] = 0;
}
if (str[i] == '1') {
dp[i] = dp[i + 1];
if (i + 1 < str.length) {
dp[i] += dp[i + 2];
}
}
if (str[i] == '2') {
dp[i] = dp[i + 1];
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
dp[i] += dp[i + 2]; // (i和i+1)作为单独的部分，后续有多少种方法
}
}
}
return dp[0];
}
public static int dpWays(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[] dp = new int[N + 1];
dp[N] = 1;
for (int i = N - 1; i >= 0; i--) {
if (str[i] == '0') {
dp[i] = 0;
} else if (str[i] == '1') {
dp[i] = dp[i + 1];
if (i + 1 < N) {
dp[i] += dp[i + 2];
}
} else if (str[i] == '2') {
dp[i] = dp[i + 1];
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
dp[i] += dp[i + 2];
}
} else {
dp[i] = dp[i + 1];
}
}
return dp[0];
}
public static void main(String[] args) {
System.out.println(number("11111"));
System.out.println(dpWays2("11111"));
}
}
```
#### 1.2.1.2 背包价值问题
2、给定两个长度都为N的数组weights和values，weight[i]和values[i]分别代表i号物品的重量和价值。
给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？
```Java
package class11;
public class Code07_Knapsack {
public static int getMaxValue(int[] w, int[] v, int bag) {
return process(w, v, 0, 0, bag);
}
// 第一种尝试
// 不变 ： w[] 重量数组 v[] 价值数组 bag 袋子的总载重
// index... 最大价值
// 0..index-1上做了货物的选择，使得你已经达到的重量是多少 alreadyW
// 如果返回-1，认为没有方案
// 如果不返回-1，认为返回的值是真实价值
public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
// base case
if (alreadyW > bag) {
return -1;
}
// 重量没超
if (index == w.length) {
return 0;
}
// 当前不选择index的货物情况下，后续的价值
// 无需传递当前index的重量，且p1就是总价值
int p1 = process(w, v, index + 1, alreadyW, bag);
// 当前选择了index的货物，把重量加上，继续向下递归
int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
// p2表示要了当前货物之后总价值应该是后续价值加上当前价值
int p2 = -1;
if (p2next != -1) {
p2 = v[index] + p2next;
}
return Math.max(p1, p2);
}
public static int maxValue(int[] w, int[] v, int bag) {
return process(w, v, 0, bag);
}
// 第二种尝试。更经典
// 只剩下rest的空间了，
// index...货物自由选择，但是剩余空间不要小于0
// 返回 index...货物能够获得的最大价值
public static int process(int[] w, int[] v, int index, int rest) {
// base case 1 无效方案
if (rest < 0) {
return -1;
}
// rest >=0。index来到终止位置，当前返回0价值
// base case 2
if (index == w.length) {
return 0;
}
// 有货也有空间。当前index不选择，得到p1总价值
int p1 = process(w, v, index + 1, rest);
int p2 = -1;、
// 选择了index位置，剩余空间减去当前重量
int p2Next = process(w, v, index + 1, rest - w[index]);
// 选择index的总价值，是index...的价值加上个当前index的价值
if(p2Next!=-1) {
p2 = v[index] + p2Next;
}
return Math.max(p1, p2);
}
public static int dpWay(int[] w, int[] v, int bag) {
int N = w.length;
int[][] dp = new int[N + 1][bag + 1];
for (int index = N - 1; index >= 0; index--) {
for (int rest = 1; rest <= bag; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest >= w[index]) {
dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
}
}
}
return dp[0][bag];
}
public static void main(String[] args) {
int[] weights = { 3, 2, 4, 7 };
int[] values = { 5, 6, 3, 19 };
int bag = 11;
System.out.println(maxValue(weights, values, bag));
System.out.println(dpWay(weights, values, bag));
}
}
```
### 1.2.2 范围上的尝试模型
#### 1.2.2.1 玩家抽取纸牌问题
给定一个整形数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌。规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请赶回最后获胜者的分数
> 绝顶聪明学术上的解释：双方玩家都会使得对方玩家在当前单独改变策略时，不会获得更大的收益。
```Java
package class11;
public class Code08_CardsInLine {
// 主函数
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
// 先手在0~length-1和后手在0~length-1上，谁分数大就是获胜者的分数
return Math.max(
f(arr, 0, arr.length - 1),
s(arr, 0, arr.length - 1)
);
}
// L....R 先手函数
// F S L+1..R
// L..R-1
public static int f(int[] arr, int L, int R) {
// base case 当只剩一张牌，且是先手
if (L == R) {
return arr[L];
}
// 当前是先手，选择最好的
return Math.max(
arr[L] + s(arr, L + 1, R),
arr[R] + s(arr, L, R - 1)
);
}
// 后手函数
// arr[L..R]
public static int s(int[] arr, int L, int R) {
// base case 当只剩一张牌，且为后手
if (L == R) {
return 0;
}
// 当前是后手，好的被绝顶聪明的先手选走了
// 相当于是先手的决策剩下的当前牌，留下最差的min
return Math.min(
f(arr, L + 1, R), // 对手挑了 arr[i]
f(arr, L, R - 1) // 对手挑了 arr[j]
);
}
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] f = new int[N][N];
int[][] s = new int[N][N];
for(int i = 0; i < N;i++) {
f[i][i] = arr[i];
}
// s[i][i] = 0;
for(int i = 1; i < N;i++) {
int L =0;
int R =i;
while(L < N && R < N) {
f[L][R] = Math.max(
arr[L] + s[L + 1][ R],
arr[R] + s[L][R - 1]
);
s[L][R] = Math.min(
f[L + 1][R], // arr[i]
f[L][R - 1] // arr[j]
);
L++;
R++;
}
}
return Math.max(f[0][N-1], s[0][N-1]);
}
public static void main(String[] args) {
int[] arr = { 4,7,9,5,19,29,80,4 };
// A 4 9
// B 7 5
System.out.println(win1(arr));
System.out.println(win2(arr));
}
}
```
#### 1.2.2.2 N皇后问题
N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上。
给定一个整数n，返回n皇后的摆法有多少种。
n=1，返回1
n=2或3,2皇后和3皇后问题无论怎么摆都不行，返回0
n=8，返回92
> 最优的N皇后的尝试方法，时间复杂度为N^N，但是process2是用位运算加速了常数项的时间
```Java
package class11;
public class Code09_NQueens {
public static int num1(int n) {
if (n < 1) {
return 0;
}
// record[0] ? record[1] ? record[2]
// record[i] -> i行的皇后，放在了第几列
int[] record = new int[n];
return process1(0, record, n);
}
// 潜台词：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不共斜线
// 目前来到了第i行，在i行准备放皇后
// record[0..i-1]表示之前的行，放了的皇后位置
// n代表整体一共有多少行 0~n-1行
// 返回值是，摆完所有的皇后，合理的摆法有多少种
// 尝试过程
public static int process1(int i, int[] record, int n) {
if (i == n) { // 终止行
return 1;
}
// 没有到终止位置，还有皇后要摆
int res = 0;
// 当前行在i行，尝试i行所有的列 -> j
for (int j = 0; j < n; j++) {
// 当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行共列共斜线，
// 如果是，认为有效，当前可以摆在j列的位置
// 如果不是，认为无效
if (isValid(record, i, j)) {
// 当前存在i行的有效值为j列位置
record[i] = j;
res += process1(i + 1, record, n);
}
}
return res;
}
// record[0..i-1]你需要看，record[i...]不需要看
// 返回i行皇后，放在了j列，是否有效
// a行b列的皇后，和c行d列的皇后会不会冲突，coding的条件是不共行
// 共列的话b==d，共斜线的话|a-c|==|b-d|
public static boolean isValid(int[] record, int i, int j) {
// 之前的某个k行的皇后
for (int k = 0; k < i; k++) {
// k, record[k] i, j
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
return false;
}
}
return true;
}
// 请不要超过32皇后问题
public static int num2(int n) {
if (n < 1 || n > 32) {
return 0;
}
// 如果你是13皇后问题，limit 最右13个1，其他都是0
int limit = n == 32 ? -1 : (1 << n) - 1;
return process2(limit, 0, 0, 0);
}
// limit 划定了问题的规模 -> 固定
// 用位运算加速常数项时间
// colLim 列的限制，1的位置不能放皇后，0的位置可以
// leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
// rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
public static int process2(
int limit,
int colLim,
int leftDiaLim,
int rightDiaLim) {
if (colLim == limit) { // base case
return 1;
}
// 所有可以放皇后的位置，都在pos上
// colLim | leftDiaLim | rightDiaLim -> 总限制
// ~ (colLim | leftDiaLim | rightDiaLim) -> 左侧的一坨0干扰，右侧每个1，可尝试
// 把左侧的去反后的一坨1，移除掉
int pos = limit & ( ~(colLim | leftDiaLim | rightDiaLim) );
int mostRightOne = 0;
int res = 0;
while (pos != 0) {
// 提取出pos中，最右侧的1来，剩下位置都是0
mostRightOne = pos & (~pos + 1);
pos = pos - mostRightOne;
res += process2(limit,
colLim | mostRightOne,
(leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >>> 1);
}
return res;
}
public static void main(String[] args) {
int n = 15;
long start = System.currentTimeMillis();
System.out.println(num2(n));
long end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
start = System.currentTimeMillis();
System.out.println(num1(n));
end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
}
}
```
## 如何尝试一件事？
1、有经验但是没有方法论
2、怎么判断一个尝试
3、难道尝试这件事真的只能拼天赋么，该怎么搞定面试？
4、动态规划是啥？好高端的样子，和尝试有什么关系？
请见下一章，暴力递归到动态规划的转移套路，解决面试中动态规划的问题。
- 第一节 复杂度、排序、二分、异或
- 第二节 链表、栈、队列、递归、哈希表、顺序表
- 第三节 归并排序、随机快排介绍
- 第四节 比较器与堆
- 第五节 前缀树、桶排序以及排序总结
- 第六节 链表相关面试题总结
- 第七节 二叉树基本算法
- 第八节 二叉树的递归思维建立
- 第九节 贪心算法深度剖析
- 第十节 并查集、图相关算法介绍
- 第十一节 暴力递归思维、动态规划思维建立
- 第十二节 用简单暴力递归思维推导动态规划思维
- 第十三节 单调栈和窗口及其更新结构
- 第十四节 类似斐波那契数列的递归
- 第十五节 认识KMP算法与bfprt算法
- 第十六节 认识Manacher(马拉车)算法
- 第十七节 认识Morris遍历
- 第十八节 线段树
- 第十九节 打表技巧和矩阵处理技巧
- 第二十节 组累加和问题整理
- 第二十一节 哈希函数有关的结构和岛问题
- 第二十二节 解决资源限制类题目
- 第二十三节 有序表原理及扩展
- 第二十四节 AC自动机和卡特兰数
- 第二十五节 算法面试专题-链表
- 第二十六节 算法面试专题-二叉树
- 第二十七节 算法面试专题-字符串