暴力递归
暴力递归就是尝试
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件（base case）
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
汉诺塔
第一步：1-N-1层从from到other
第二步：N层从from到to
第三步：1-N-1层从other到to
public static void func(int i, String start, String end, String other) {
if (i == 1) {
System.out.println(" Move 1 from " + start + " to " + end);
} else {
func( i - 1, start, other, end);
System.out.println(" Move " + i + " from " + start + " to " + end);
func( i - 1, other, end, satrt);
}
}
非递归版本
public static hanoi() {
String from;
}
范围上尝试的模型
谁赢了
public static int win1(int[] arr) {
if(arr == null || arr.length == 0) {
return 0;
}
return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
//先手函数
public static int f(int[] arr, int i, int j){
if( i == j){ //base case只有一张牌
return arr[i];
}
return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j -1));
}
//后手函数
public static int s(int[] arr, int i, int j){
if( i == j){//base case
return 0;
}
return Math.min(f(arr, i + 1, j), f(arr, i, j -1));//对手一定让你得到更小的那个
}
栈的逆序
要求不使用额外数据结构
public static void reverse() {
if (stack.isEmpty()) {
return;
}
int i = f(stack);
reverse(stack);
stack.push(i);
}
//f函数将栈最后一个数返回，其他数保持先前次序
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;
}
}
从左往右模型
字符转化
1对应A，2对应B，以此类推
思路：每次决定i位置，i位置前面的i-1个确定，i位置有两种可能，一种单独，一种和后面的一起决定，要想一起，i位置只能是1或者2
因为数字的范围是1 ---- 26
//i之前的位置，如何转化已经做过决定了，str[0. i - 1]不管
//i...有多少种转化的结果
public static int process(char[] str, int i) {
if (i == str.length){//base case
return 1;
}
//i位置单独面对'0'，不可以，直接返回0
if (str[i] == '0') {
return 0;
}
if (str[i] == '1') {
int res = process(str, i + 1);//i单独有多少种
if (i + 1 < str.length) {
res += process(str, i + 2);//i和i + 1一起有多少种
}
return res;
}
if (str[i] == '2') {
int res = process(str, i + 1);//i单独有多少种
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {//i+1不能超过6
res += process(str,i + 2);//i和i + 1一起有多少种
}
return res;
}
//str[i] == '3-9'
return process(str, i + 1);
}
子序列(子集)问题
注意子串和子序列的区别
子串是必须连续的，两个for循环即可
//i是当前来到i位置
public static void process(char[] str, int i, List<Character> res) {
if( i == str.length) {
printList(res);
return;
}
List<Character> resKeep = copyList(res);
resKeep.add(str[i]);
process(str, i + 1, resKeep);//要当前字符的路
List<Character> resNoInclude = copyList(res);
process(str, i + 1, resNoInclude);//不要当前字符的路
}
//优化版
public static void process(char[] str, int i) {
if( i == str.length) {
System.out.println(String.valueOf(str));
return;
}
process(str, i + 1);
char tmp = str[i];
str[i] = 0;
process(str, i + 1);
str[i] = tmp;
}
进阶问题：不出现重复字面值的子序列
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);
}
全排列
//主函数调用时，process(chs, 0, res)
//str[i...]范围上，所有的字符都可以在i位置去尝试
//str[0-i]是之前做的选择
public staic void process(char[] str, int i, ArrayList<String> res) {
if (i == str.length) {
res.add(String,valueOf(str));
}
for (int j = i; j < str.length; j++) {//[i...]i及其后的所有位置都有机会来到i位置
swap(str, i, j);
process(str, i + 1, res);
swap(str, i, j);
}
}
//进阶版-没有重复的全排列(也可以用上述的全排列方法，只不过最后加进HashSet中)
//str[i...]范围上，所有的字符都可以在i位置去尝试
//str[0-i]是之前做的选择
//请把所有的字符串形成的全排列，加入到res中
public static void process(char[] str, int i, ArrayList<String> res) {
if( i == str.length) {
res.add(String.valueOf(str));
}
boolean[] visit = new boolean[26];//代替哈希表，代表从a-z的26个字符是否出现过
for (int j = i; j < str.length; j++) {
if (!visit[ str[j] - 'a'] ) {//判断i位置是否放过该字符，0位置代表a，25位置代表z
visit[str[j] - 'a'] = true;//没放过，进来之后就标记为放过，代表i位置放过str[j]
swap(str, i, j);
process(str, i + 1, res);
swap(str, i, j);
}
}
}
背包问题
两个数组，一个weights,一个values，代表物体的重量和价值，给定一个正数bag代表载重bag的袋子，问能装的最大价值
//不变量：w[] v[] bag
//求index...最大值
//0...index - 1已经选择完毕，现在的重量是alreadyW
//返回-1认为没有方案
public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
if (alreadyW > bag) {
return -1;
}
if (index == w.length) {
return 0;
}
int p1 = process(w, v, index + 1, alreadyW, bag);
int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
int p2 = -1;
if(p2next != -1) {
p2 = v[index] + p2next;
}
return Math.max(p1, p2);
}
//经典写法
public static int process(int[] w, int[] v, int index, int rest) {
if (rest <= 0) {
return 0;
}
if (index == w.length) {
return 0;
}
int p1 = process(w, v, index + 1, rest);
int p2 = Integer.MIN_VALUE;
if (rest >= w[index]) {
p2 = v[index] + process(w, v, index + 1, rest - w[index]);
}
return Math.max(p1, p2);
}
//经典写法改
public static int process2(int[] w, int[] v, int index, int rest) {
if (rest < 0) {
return -1;
}
if (index == w.length) {
return 0;
}
//来到此处rest一定不 < 0，p1一定不为-1
int p1 = process(w, v, index + 1, rest);
int p2 = -1;
int p2next = process(w, v, index + 1, rest - w[index]);
if (p2next != -1) {
p2 = v[index] + p2next;
}
return Math.max(p1, p2);
}
欧拉信封
N个人，每个人寄出一封信，接受一封信，有多少种可能（不能自己给自己寄信）
N = 1，0种
N = 2，1种
N = 3，2中
从小问题开始推到大问题，推出递推公式
f(N) = (N - 1) * ( f(N - 2) + f(N - 1) )
动态规划
暴力递归为什么暴力：存在大量重复计算浪费时间，如经典的斐波那契数列问题
f(7) = f(6) + f(5) = f(5) + f(4) + f(4) + f(3)
动态规划关键在于空间换时间
题目一
/**
* 递归版本
* @param N 全部1到N个位置
* @param cur 当前位置
* @param rest 剩余步数
* @param P 目标位置
* @return
*/
public static int func1(int N, int cur, int rest, int P) {
//当剩余步数为0时，如果停在P上，那么之前的移动就是有效的，返回1，否则返回0
if (rest == 0) {
return cur == P ? 1 : 0;
}
//在一位置时只能向右走
if (cur == 1) {
return func1(N, 2, rest - 1, P);
}
//在N位置时只能向左走
if (cur == N) {
return func1(N, N - 1, rest - 1, P);
}
//在当前位置可以向左走，也可以向右走，向左和向右是总数
return func1(N, cur - 1, rest - 1, P) +
func1(N, cur + 1, rest - 1, P);
}
动态规划版本
//记忆化搜索
public static int ways(int N, int M, int K, int P) {
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
int[][] dp = new int[N + 1][K + 1];
for (int row = 0; row <= N; row++) {
for (int col = 0; col <= K; col++) {
dp[row][col] = -1;
}
}
return func1(N, M, K, P, dp);
}
public static int func1(int N, int cur, int rest, int P, int[][] dp) {
if (dp[cur][rest] != -1) {
return dp[cur][rest];
}
if (rest == 0) {
dp[cur][rest] = cur == P ? 1 : 0;
return dp[cur][rest];
}
if (cur == 1) {
dp[cur][rest] = func1(N, 2, rest - 1, P, dp);
return dp[cur][rest];
}
if (cur == N) {
dp[cur][rest] = func1(N, N - 1, rest - 1, P, dp);
return dp[cur][rest];
}
dp[cur][rest] = func1(N, cur - 1, rest - 1, P, dp) +
func1(N, cur + 1, rest - 1, P, dp);
return dp[cur][rest];
}
题目二背包问题
二维表的两个参数分别是：index和可用空间
暴力递归版本参考上一个小节
public static int dpway(int[] w, int[] v, int bag) {
int N = w.length;
int[][] dp = new int [N+1][bag+1];
//dp[N][...]全部为0
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 +1][rest] + v[index], dp[index][rest]);
}
}
}
return dp[0][bag];
}
public static int dpway(int[] w, int[] v, int bag) {
int N = w.length;
int[][] dp = new int [N+1][bag+1];
//dp[N][...]全部为0
for(int index = N - 1; index >= 0; index--) {
for(int rest = 0; rest <= bag; rest++) {
int p1 = dp[index + 1][rest];
int p2 = -1;
if (rest - w[index] >= 0) {
p2 = v[index] + dp[index + 1][rest - w[index]];
}
dp[index][rest] = Math.max(p1,p2);
}
}
return dp[0][bag];
}
题目三字符转化
//i之前的位置，如何转化已经做过决定了，str[0. i - 1]不管
//i...有多少种转化的结果
public static int process(char[] str, int i) {
if (i == str.length){//base case,且不能设置为str.length - 1
return 1;
}
//i位置单独面对'0'，不可以，直接返回0
if (str[i] == '0') {
return 0;
}
int[] dp = new int[];
for (int i = N - 1; i >= 0; i-- ) {
if (str[i] == '1') {
dp[i] = dp[i + 1];//i单独有多少种
if (i + 1 < str.length) {
dp[i] += dp[i + 2];//i和i + 1一起有多少种
}
}
if (str[i] == '2') {
dp[i] = dp[i + 1];//i单独有多少种
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {//i+1不能超过6
dp[i] += dp[i + 2];//i和i + 1一起有多少种
}
}
}
return dp[0];
}
题目四谁赢了
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];
}
for (int i = 1; i < N; i++) {
int row = 0;
int col = i;
while (col < N) {
s[row][col] = Math.max(
arr[i] + s[i + 1, j],
arr[j] + s[i, j -1]
);
f[row][col] = Math.min(
f[i + 1, j],
f[i, j -1]
);
row++;
col++;
}
}
return Math.max(s[0][N - 1], f[0][N - 1]);
}
题目五
一个数组，用这个数组中的数凑成目标aim的方法数
public static int way1(int[] arr, int aim) {
if (arr.length == 0 || aim < 0) {
return 0;
}
return process(arr,0,aim);
}
public static int process(int[] arr, int index, int rest) {
if (rest < 0) {
return 0;
}
if (index == arr.length) {
return rest == 0 ? 1 : 0;
}
int result = 0;
result += process(arr, index, rest - arr[index]);
result += process(arr, index + 1, rest);
//这里递归的过程还有一种写法，当用此方法时，可以省略rest < 0的条件，因为for循环中保证了它不会发生
/*
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
result += process(arr,index + 1, rest - zhang * arr[index]);
}*/
return result;
}
//记忆化搜索
public static int way2(int[] arr, int aim) {
if (arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < aim + 1; j++) {
dp[i][j] = -1;
}
}
return process2(arr,0,aim, dp);
}
public static int process2(int[] arr, int index, int rest, int[][] dp) {
if (dp[index][rest] != -1) {
return dp[index][rest];
}
if (index == arr.length) {
dp[index][rest] = rest == 0 ? 1 : 0;
return dp[index][rest];
}
int result = 0;
result += process(arr, index, rest - arr[index]);
result += process(arr, index + 1, rest);
//这里递归的过程还有一种写法，当用此方法时，可以省略rest < 0的条件，因为for循环中保证了它不会发生
/*
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
result += process(arr,index + 1, rest - zhang * arr[index]);
}*/
dp[index][rest] = result;
return result;
}
//经典动态规划
public static int way3(int[] arr, int aim) {
if (arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int i = N - 1; i >= 0; i--) {
for (int rest = 0; rest <= aim; rest++) {
int result = 0;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
result += dp[index + 1][rest - zhang * arr[index] ];
}
dp[i][rest] = result;
}
}
return dp[0][aim];
}
//动态规划更加优化版本
public static int way4(int[] arr, int aim) {
if (arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int i = N - 1; i >= 0; i--) {
for (int rest = 0; rest <= aim; rest++) {
dp[i][rest] = dp[i + 1][rest];
if (rest - arr[i] >= 0) {
dp[i][rest] += dp[i][rest - arr[i] ];
}
}
}
return dp[0][aim];
}
题目六最小贴纸数
public static int minS(String rest, String[] arr) {
if (rest.equals("")) {
return 0;
}
//搞定rest的第一张贴纸是什么？
int next = 0;
for (String first : arr) {
rest
int cur = minS()
}
return next + 1;
}
