暴力递归与动态规划
- 暴力递归
-
- 习题1 打印n层汉诺塔从最左边移动到最右边的全部过程
- 习题2 给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。 如何实现?
- 习题3 打印一个字符串的全部子序列，要求不要出现重复的排列
- 习题4 打印一个字符串的全部排列，要求不要出现重复的排列
- 动态优化
-
- 习题5 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种给定四个参数 N、M、K、P，返回方法数。
- 习题6 给定一个整型数组arr，代表数值不同的纸牌排成一条线玩家A和玩家B依次拿走每张纸牌规定玩家A先拿，玩家B后拿但是每个玩家每次只能拿走最左或最右的纸牌玩家A和玩家B都绝顶聪明请返回最后获胜者的分数。
- 习题7 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
- 习题8 规定1和A对应、2和B对应、3和C对应...26和Z对应那么一个数字字符串比如"111”就可以转化为:"AAA"、"KA"和"AK"给定一个只有数字字符组成的字符串str，返回有多少种转化结果
- 习题9 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来返回需要至少多少张贴纸可以完成这个任务。例子：str= "babac"，arr = {"ba","c","abcd"}ba + ba + c 3 abcd + abcd 2 abcd+ba 2所以返回2
- 习题10 给定两个字符串str1和str2，返回这两个字符串的最长公共子序列长度比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”最长公共子序列是“123456”，所以返回长度6
- 习题11 给定一个字符串str，返回这个字符串的最长回文子序列长度比如 ： str = “a12b3c43def2ghi1kpm”最长回文子序列是“1234321”或者“123c321”，返回长度7
- 习题12 请同学们自行搜索或者想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域给你三个 参数 x，y，k返回“马”从(0,0)位置出发，必须走k步最后落在(x,y)上的方法数有多少种?
- 习题13 给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发假设所有人拿到咖啡之后立刻喝干净，返回从开始等到所有咖啡机变干净的最短时间三个参数：int[] arr、int N，int a、int b
- 习题14 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和返回最小距离累加和
- 习题15 arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，即便是值相同的货币也认为每一张都是不同的，返回组成aim的方法数例如：arr = {1,1,1}，aim = 2第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2一共就3种方法，所以返回3
- 习题16 arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的方法数例如：arr = {1,2}，aim = 4方法如下：1+1+1+1、1+1+2、2+2一共就3种方法，所以返回3
- 习题17 arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，认为值相同的货币没有任何不同，返回组成aim的方法数例如：arr = {1,2,1,1,2,1,2}，aim = 4方法：1+1+1+1、1+1+2、2+2一共就3种方法，所以返回3
- 习题18 给定5个参数，N，M，row，col，k表示在N*M的区域上，醉汉Bob初始在(row,col)位置Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位任何时候Bob只要离开N*M的区域，就直接死亡返回k步之后，Bob还在N*M的区域的概率
- 习题19 给定3个参数，N，M，K怪兽有N滴血，等着英雄来砍自己英雄每一次打击，都会让怪兽流失[0～M]的血量到底流失多少？每一次在[0～M]上等概率的获得一个值求K次打击之后，英雄把怪兽砍死的概率
- 习题20 arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数
- 习题21 给定一个正数n，求n的裂开方法数，规定：后面的数不能比前面的数小比如4的裂开方法有：1+1+1+1、1+1+2、1+3、2+2、45种，所以返回5
- 习题22 给定一个正数数组arr，请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近返回：最接近的情况下，较小集合的累加和
- 习题23 给定一个正数数组arr，请把arr中所有的数分成两个集合如果arr长度为偶数，两个集合包含数的个数要一样多如果arr长度为奇数，两个集合包含数的个数必须只差一个请尽量让两个集合的累加和接近返回：最接近的情况下，较小集合的累加和
- 习题24 N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列， 也不在同一条斜线上给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0n=8，返回92
暴力递归
暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件(base case)
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解
习题1 打印n层汉诺塔从最左边移动到最右边的全部过程
public static void hanoi1(int n) {
leftToRight(n);
}
// 请把1~N层圆盘 从左 -> 右
public static void leftToRight(int n) {
if (n == 1) { // base case
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);
}
public static void hanoi2(int n) {
if (n > 0) {
func(n, "left", "right", "mid");
}
}
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);
}
习题2 给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。 如何实现?
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int i = f(stack);
reverse(stack);
stack.push(i);
}
// 栈底元素移除掉
// 上面的元素盖下来
// 返回移除掉的栈底元素
public static int f(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int last = f(stack);
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());
}
}
习题3 打印一个字符串的全部子序列，要求不要出现重复的排列
// s -> "abc" ->
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 固定参数
// 来到了str[index]字符，index是位置
// str[0..index-1]已经走过了！之前的决定，都在path上
// 之前的决定已经不能改变了，就是path
// str[index....]还能决定，之前已经确定，而后面还能自由选择的话，
// 把所有生成的子序列，放入到ans里去
public static void process1(char[] str, int index, List<String> ans, String path) {
if (index == str.length) {
ans.add(path);
return;
}
// 没有要index位置的字符
process1(str, index + 1, ans, path);
// 要了index位置的字符
process1(str, index + 1, ans, path + String.valueOf(str[index]));
}
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;
}
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 = "acccc";
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("=================");
}
习题4 打印一个字符串的全部排列，要求不要出现重复的排列
public static List<String> permutation1(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}
char[] str = s.toCharArray();
ArrayList<Character> rest = new ArrayList<Character>();
for (char cha : str) {
rest.add(cha);
}
String path = "";
f(rest, path, ans);
return ans;
}
public static void f(ArrayList<Character> rest, String path, List<String> ans) {
if (rest.isEmpty()) {
ans.add(path);
} else {
int N = rest.size();
for (int i = 0; i < N; i++) {
char cur = rest.get(i);
rest.remove(i);
f(rest, path + cur, ans);
rest.add(i, cur);
}
}
}
public static List<String> permutation2(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}
char[] str = s.toCharArray();
g1(str, 0, ans);
return ans;
}
public static void g1(char[] str, int index, List<String> ans) {
if (index == str.length) {
ans.add(String.valueOf(str));
} else {
for (int i = index; i < str.length; i++) {
swap(str, index, i);
g1(str, index + 1, ans);
swap(str, index, i);
}
}
}
public static List<String> permutation3(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}
char[] str = s.toCharArray();
g2(str, 0, ans);
return ans;
}
public static void g2(char[] str, int index, List<String> ans) {
if (index == str.length) {
ans.add(String.valueOf(str));
} else {
boolean[] visited = new boolean[256];
for (int i = index; i < str.length; i++) {
if (!visited[str[i]]) {
visited[str[i]] = true;
swap(str, index, i);
g2(str, index + 1, ans);
swap(str, index, i);
}
}
}
}
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 = "acc";
List<String> ans1 = permutation1(s);
for (String str : ans1) {
System.out.println(str);
}
System.out.println("=======");
List<String> ans2 = permutation2(s);
for (String str : ans2) {
System.out.println(str);
}
System.out.println("=======");
List<String> ans3 = permutation3(s);
for (String str : ans3) {
System.out.println(str);
}
}
动态优化
1.什么暴力递归可以继续优化？
有重复调用同一个子问题的解，这种递归可以优化
如果每一个子问题都是不同的解，无法优化也不用优化
2.暴力递归和动态规划的关系
某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
但不是所有的暴力递归，都一定对应着动态规划
3.如何找到某个问题的动态规划方式？
1）设计暴力递归：重要原则+4种常见尝试模型！重点！
2）分析有没有重复解：套路解决
3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决
4）看看能否继续优化：套路解决
4.面试中设计暴力递归过程的原则
1）每一个可变参数的类型，一定不要比int类型更加复杂
2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数
3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可
4）可变参数的个数，能少则少
5.常见的4种尝试模型
1）从左往右的尝试模型
2）范围上的尝试模型
3）多样本位置全对应的尝试模型
4）寻找业务限制的尝试模型
习题5 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种给定四个参数 N、M、K、P，返回方法数。
public static int ways1(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
return process1(start, K, aim, N);
}
// 机器人当前来到的位置是cur，
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
// 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
public static int process1(int cur, int rest, int aim, int N) {
if (rest == 0) { // 如果已经不需要走了，走完了！
return cur == aim ? 1 : 0;
}
// (cur, rest)
if (cur == 1) { // 1 -> 2
return process1(2, rest - 1, aim, N);
}
// (cur, rest)
if (cur == N) { // N-1 <- N
return process1(N - 1, rest - 1, aim, N);
}
// (cur, rest)
return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
}
public static int ways2(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = -1;
}
}
// dp就是缓存表
// dp[cur][rest] == -1 -> process1(cur, rest)之前没算过！
// dp[cur][rest] != -1 -> process1(cur, rest)之前算过！返回值，dp[cur][rest]
// N+1 * K+1
return process2(start, K, aim, N, dp);
}
// cur 范: 1 ~ N
// rest 范：0 ~ K
public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
if (dp[cur][rest] != -1) {
return dp[cur][rest];
}
// 之前没算过！
int ans = 0;
if (rest == 0) {
ans = cur == aim ? 1 : 0;
} else if (cur == 1) {
ans = process2(2, rest - 1, aim, N, dp);
} else if (cur == N) {
ans = process2(N - 1, rest - 1, aim, N, dp);
} else {
ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
}
dp[cur][rest] = ans;
return ans;
}
public static int ways3(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
dp[aim][0] = 1;
for (int rest = 1; rest <= K; rest++) {
dp[1][rest] = dp[2][rest - 1];
for (int cur = 2; cur < N; cur++) {
dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
}
dp[N][rest] = dp[N - 1][rest - 1];
}
return dp[start][K];
}
public static void main(String[] args) {
System.out.println(ways1(5, 2, 4, 6));
System.out.println(ways2(5, 2, 4, 6));
System.out.println(ways3(5, 2, 4, 6));
}
习题6 给定一个整型数组arr，代表数值不同的纸牌排成一条线玩家A和玩家B依次拿走每张纸牌规定玩家A先拿，玩家B后拿但是每个玩家每次只能拿走最左或最右的纸牌玩家A和玩家B都绝顶聪明请返回最后获胜者的分数。
// 根据规则，返回获胜者的分数
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int first = f1(arr, 0, arr.length - 1);
int second = g1(arr, 0, arr.length - 1);
return Math.max(first, second);
}
// arr[L..R]，先手获得的最好分数返回
public static int f1(int[] arr, int L, int R) {
if (L == R) {
return arr[L];
}
int p1 = arr[L] + g1(arr, L + 1, R);
int p2 = arr[R] + g1(arr, L, R - 1);
return Math.max(p1, p2);
}
// // arr[L..R]，后手获得的最好分数返回
public static int g1(int[] arr, int L, int R) {
if (L == R) {
return 0;
}
int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
return Math.min(p1, p2);
}
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] fmap = new int[N][N];
int[][] gmap = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
fmap[i][j] = -1;
gmap[i][j] = -1;
}
}
int first = f2(arr, 0, arr.length - 1, fmap, gmap);
int second = g2(arr, 0, arr.length - 1, fmap, gmap);
return Math.max(first, second);
}
// arr[L..R]，先手获得的最好分数返回
public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
if (fmap[L][R] != -1) {
return fmap[L][R];
}
int ans = 0;
if (L == R) {
ans = arr[L];
} else {
int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
ans = Math.max(p1, p2);
}
fmap[L][R] = ans;
return ans;
}
// // arr[L..R]，后手获得的最好分数返回
public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
if (gmap[L][R] != -1) {
return gmap[L][R];
}
int ans = 0;
if (L != R) {
int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
ans = Math.min(p1, p2);
}
gmap[L][R] = ans;
return ans;
}
public static int win3(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] fmap = new int[N][N];
int[][] gmap = new int[N][N];
for (int i = 0; i < N; i++) {
fmap[i][i] = arr[i];
}
for (int startCol = 1; startCol < N; startCol++) {
int L = 0;
int R = startCol;
while (R < N) {
fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
L++;
R++;
}
}
return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
}
public static void main(String[] args) {
int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
System
发布评论