11-暴力递归与动态规划.md

[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和思路二。在动态规划章节，可以用动态规划优化我们的尝试到最优版本

```Go
package main

import "fmt"

// hanoiV1 汉诺塔问题 递归版本1
func hanoiV1(n int) {
	leftToRight(n)
}

// leftToRight 请把1~N层圆盘 从左 -> 右
func leftToRight(n int) {
	if n == 1 {
		fmt.Println("Move 1 from left to right")
		return
	}

	leftToMid(n -1)
	fmt.Println(fmt.Sprintf("Move  %d  from left to right", n))
	midToRight(n - 1)
}

// leftToMid 请把1~N层圆盘 从左 -> 中
func leftToMid(n int) {
	if n == 1 {
		fmt.Println("Move 1 from left to mid")
		return
	}

	leftToRight(n - 1)
	fmt.Println(fmt.Sprintf("Move  %d  from left to mid", n))
	rightToMid(n - 1)
}

func rightToMid(n int) {
	if n == 1 {
		fmt.Println("Move 1 from right to mid")
		return
	}
	rightToLeft(n - 1)
	fmt.Println(fmt.Sprintf("Move  %d  from right to mid", n))
	leftToMid(n - 1)
}

func midToRight(n int) {
	if n == 1 {
		fmt.Println("Move 1 from mid to right")
		return
	}
	midToLeft(n - 1)
	fmt.Println(fmt.Sprintf("Move  %d  from mid to right", n))
	leftToRight(n - 1)
}

func midToLeft(n int) {
	if n == 1 {
		fmt.Println("Move 1 from mid to left")
		return
	}
	midToRight(n - 1)
	fmt.Println(fmt.Sprintf("Move  %d  from mid to left", n))
	rightToLeft(n - 1)
}

func rightToLeft(n int) {
	if n == 1 {
		fmt.Println("Move 1 from right to left")
		return
	}
	rightToMid(n - 1)
	fmt.Println(fmt.Sprintf("Move  %d  from right to left", n))
	midToLeft(n - 1)
}

// 思路二：暴力递归 版本2 from to other
func hanoiV2(n int) {
	if n > 0 {
		f(n, "left", "right", "mid");
	}
}

// 1~i 圆盘 目标是from -> to， other是另外一个
func f(n int, from, to, other string) {
	if n == 1 { // base
		fmt.Println(fmt.Sprintf("Move 1 from %s  to %s", from, to))
	} else {
		f(n - 1, from, other, to)
		fmt.Println(fmt.Sprintf("Move %d from %s  to %s", n, from, to))
		f(n - 1, other, to, from)
	}
}
```

#### 1.1.1.2 例二：字符串子序列问题

1、打印一个字符串的全部子序列

> 子串：必须是连续的，用for循环就行

> 子序列：比子串自由，在原始序列的基础上，以此拿字符但是可以不连续

```Go
package main

import "fmt"

// 子序列问题 递归版本1 打印一个字符串的全部子序列
func subsV1(s string) []string {
	chars := []byte(s)
	path := ""
	ans := make([]string, 0)
	processV1(chars, 0, ans, path)
	return ans
}

// str固定，不变
// index此时来到的位置, 要  or 不要
// 如果index来到了str中的终止位置，把沿途路径所形成的答案，放入ans中
// 之前做出的选择，就是沿途路径path
func processV1(chars []byte, index int, ans []string, path string) {
	if index == len(chars) {
		ans = append(ans, path)
		return
	}

	no := path
	processV1(chars, index + 1, ans, no)
	yes := fmt.Sprintf("%s%s", path, string(chars[index]))
	processV1(chars, index + 1, ans, yes)
}
```



2、打印一个字符串的全部子序列，要求不要出现重复字面值的子序列

> 比如aaabcccc就会得到很多相同字面值的子序列，我们把重复字面值的子序列只要一个

```Go
package main

import "fmt"

// 子序列问题 版本2 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
func subsV2(s string) []string {
	chars := []byte(s)
	path := ""
	set := make(map[string]string, 0)
	processV2(chars, 0, set, path)
	ans := make([]string, 0)
	for curK := range set {
		ans = append(ans, curK)
	}
	return ans
}

func processV2(chars []byte, index int, set map[string]string, path string) {
	if index == len(chars) {
		set[path] = ""
		return
	}
	no := path
	processV2(chars, index + 1, set, no)
	yes := fmt.Sprintf("%s%s", path, string(chars[index]))
	processV2(chars, index + 1, set, yes)
}
```

#### 1.1.1.3 例四：字符串全排列问题

1、打印一个字符串的全部排列,process

2、打印一个字符串的全部排列，要求不要出现重复的排列.process2。

方法1，可以用HashSet最后去重，该方式是把递归的所有结果进行筛选。

方法2可以抛弃重复元素，例如a在0位置已经尝试完毕，再有一个元素也是a要到0位置，那么禁止，该方法是递归的时候事先判断要不要进行下一步递归，更快一点。该方法又叫分支限界


```Go
package main

// 字符串全排列问题
func permutation(str string) []string {
	res := make([]string, 0)
	if len(str) == 0 {
		return res
	}

	chs := []byte(str)
	processPermutation(chs, 0, res)
	return res
}

// str[0..i-1]已经做好决定的
// str[i...]都有机会来到i位置
// i到达终止位置，str当前的样子，就是一种结果 -> ans
func processPermutation(str []byte, i int, ans []string) {
	// i来到终点，返回该种答案
	if i == len(str) {
		ans = append(ans, string(str))
	}
	// 如果i没有终止，i...  都可以来到i位置
	for j := i; j < len(str); j++ { // i后面所有的字符都有机会来到i位置
		str[i], str[j] = str[j], str[i] // swap
		processPermutation(str, i + 1, ans)
		// 恢复交换之前的现场
		str[i], str[j] = str[j], str[i] // swap
	}
}
```


```Go
package main

// 字符串全排列问题无重复
func permutationNoRepeat(str string) []string {
	res := make([]string, 0)
	if len(str) == 0 {
		return res
	}
	chs := []byte(str)
	processPermutationNoRepeat(chs, 0, res)
	return res
}

// str[0..i-1]已经做好决定的
// str[i...]都有机会来到i位置
// i终止位置，str当前的样子，就是一种结果 -> ans
func processPermutationNoRepeat(str []byte, i int, ans []string) {
	if i == len(str) {
		ans = append(ans, string(str))
		return
	}

	visit := make([]bool, 0) // visit[0 1 .. 25] 代表a-z的字符有没有在当前出现过
	// i右边的字符都有机会
	for j := i; j < len(str); 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
			str[i], str[j] = str[j], str[i] // swap
			processPermutationNoRepeat(str, i + 1, ans)
			str[i], str[j] = str[j], str[i] // swap
		}
	}
}
```

## 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字符，无法尝试。继续如此周而复始

```Go
package main

import "fmt"

// 数字字符转化问题。1对应A,B对应2...; 111可以转化为AAA、KA、AK。所以有三种转化
func number(str string) int {
	if len(str) == 0 {
		return 0
	}

	// i初始为0，表示0位置往后有多少中转化结果
	return processConvert([]byte(str), 0)
}

// str[0...i-1]已经转化完了，固定了
// i之前的位置，如何转化已经做过决定了, 不用再关心
// i... 有多少种转化的结果
func processConvert(chars []byte, i int) int {
	// i和字符串长度一样大，右侧没有字符了。找到1中转化是0~n-1位置的转化
	if i == len(chars) { // base case
		return 1
	}

	// i之前的决策，让当前i位置单独面对一个0字符，那么之前决策错误，返回0
	// 例如10先转化为A，2位置是0字符无法转化，当前决策无效
	// 而10直接转化为J,直接到终止位置，返回一种转化J
	if chars[i] == '0' {
		return 0
	}

	// i位置如果是1或者2，有可能和下一个位置共同转化，因为字符数为0~26
	// 反之3~9超过26不需要决策

	// str[i] 如果是1，总是有两个选择，因为最大为19，不超过26
	if chars[i] == '1' {
		res := processConvert(chars, i+1)
		if i+1 < len(chars) {
			res += processConvert(chars, i+2)
		}
		return res
	}

	// str[i] 如果是2，那么有可能有两种选择，需要看是否超过26
	if chars[i] == '2' {
		res := processConvert(chars, i+1)
		if i+1 < len(chars) && (chars[i+1] >= '0' && chars[i+1] <= '6') {
			res += processConvert(chars, i+2) // (i和i+1)作为单独的部分，后续有多少种方法
		}
		return res
	}

	// // str[i] 在3~9的位置，下个位置必须决策一种选择
	return processConvert(chars, i+1)
}

// dbNumber 动态规划解法
func dbNumber(str string) int {
	if len(str) == 0 {
		return 0
	}

	chars := []byte(str)
	N := len(str)
	dp := make([]int, 0, N+1)
	dp[N] = 1
	for i := N - 1; i >= 0; i-- {
		if chars[i] == '0' {
			dp[i] = 0
		} else if chars[i] == '1' {
			dp[i] = dp[i+1]
			if i+1 < N {
				dp[i] += dp[i+2]
			}
		} else if chars[i] == '2' {
			dp[i] = dp[i+1]
			if i+1 < N && (chars[i+1] >= '0' && chars[i+1] <= '6') {
				dp[i] += dp[i+2]
			}
		} else {
			dp[i] = dp[i + 1]
		}
	}
	return dp[0]
}

func main() {
	fmt.Println(number("111"))
}
```

#### 1.2.1.2 背包价值问题

2、给定两个长度都为N的数组weights和values，weight[i]和values[i]分别代表i号物品的重量和价值。

给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？

```Go
package main

import (
	"fmt"
	"math"
)

// maxBagValue 背包最大价值问题。
func maxBagValue(w, v []int, bag int) int {
	return processRest(w, v, 0, bag)
}

// 只剩下rest的空间了，
// index...货物自由选择，但是剩余空间不要小于0
// 返回 index...货物能够获得的最大价值
func processRest(w, v []int, index, rest int) int {
	// base case
	if rest < 0 {
		return -1
	}

	// rest >=0。index来到终止位置，当前返回0价值
	// base case 2
	if index == len(w) {
		return 0
	}

	// 有货也有空间。当前index不选择，得到p1总价值
	p1 := processRest(w, v, index+1, rest)
	p2 := -1
	// 选择了index位置，剩余空间减去当前重量
	p2Next := processRest(w, v, index+1, rest-w[index])
	// 选择index的总价值，是index...的价值加上个当前index的价值
	if p2Next != -1 {
		p2 = v[index] + p2Next
	}
	return int(math.Max(float64(p1), float64(p2)))
}

// maxBagValueDp 背包问题动态规划解法
func maxBagValueDp(w, v []int, bag int) int {
	N := len(w)

	// m行 n列。golang数组只能常量初始化，这里动态构造切片
	m,n := N+1, bag+1
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	for index := N - 1; index >= 0; index-- {
		for rest := 1; rest <= bag; rest++ {
			dp[index][rest] = dp[index+1][rest]
			if rest >= w[index] {
				dp[index][rest] = int(math.Max(float64(dp[index][rest]), float64(v[index]+dp[index+1][rest-w[index]])))
			}
		}
	}
	return dp[0][bag]
}

func main() {
	w := []int{3, 2, 4, 7}
	v := []int{5, 6, 3, 19}
	bag := 11
	fmt.Println(maxBagValue(w, v, bag))
	fmt.Println(maxBagValueDp(w, v, bag))
}
```

### 1.2.2 范围上的尝试模型

#### 1.2.2.1 玩家抽取纸牌问题

给定一个整形数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌。规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数

> 绝顶聪明学术上的解释：双方玩家都会使得对方玩家在当前单独改变策略时，不会获得更大的收益。

```Go
package main

import "math"

// CardsInLineWin 给定纸牌，返回A先手的情况下，最后获胜者的分数
func CardsInLineWin(arr []int) int {
	if len(arr) == 0 {
		return 0
	}
	// 先手在0~length-1和后手在0~length-1上，谁分数大就是获胜者的分数
	return int(math.Max(float64(firstHand(arr, 0, len(arr)-1)), float64(secondHand(arr, 0, len(arr)-1))))
}

// L....R 先手函数
// F  S  L+1..R
// L..R-1
func firstHand(arr []int, L int, R int) int {
	// base case 当只剩一张牌，且是先手
	if L == R {
		return arr[L]
	}

	// 当前是先手，选择最好的
	return int(math.Max(float64(arr[L]+secondHand(arr, L+1, R)), float64(arr[R]+secondHand(arr, L, R-1))))
}

// 后手函数
// arr[L..R]
func secondHand(arr []int, L int, R int) int {
	// base case 当只剩一张牌，且为后手
	if L == R {
		return 0
	}
	// 当前是后手，好的被绝顶聪明的先手选走了
	// 相当于是先手的决策剩下的当前牌，留下最差的min
	return int(math.Min(float64(firstHand(arr, L+1, R)), float64(firstHand(arr, L, R-1))))
}

func CardsInLineWinDp(arr []int) int {
	if len(arr) == 0 {
		return 0
	}

	N := len(arr)
	// m行 n列。golang数组只能常量初始化，这里动态构造切片
	m, n := N, N
	dpf := make([][]int, m)
	dps := make([][]int, m)
	for i := range dpf {
		dpf[i] = make([]int, n)
		dps[i] = make([]int, n)
	}

	for i := 0; i < N; i++ {
		dpf[i][i] = arr[i]
	}

	// dps[i][i] = 0
	for i := 1; i < N; i++ {
		L := 0
		R := i
		for L < N && R < N {
			dpf[L][R] = int(math.Max(float64(arr[L]+dps[L+1][R]), float64(arr[R]+dps[L][R-1])))
			dps[L][R] = int(math.Min(float64(dpf[L+1][R]), float64(dpf[L][R-1])))
			L++
			R++
		}
	}
	return int(math.Max(float64(dpf[0][N-1]), float64(dps[0][N-1])))
}
```
#### 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是用位运算加速了常数项的时间

```Go
package main

import (
	"fmt"
	"math"
	"time"
)

// NQueensNum1 n皇后摆放问题解法1
func NQueensNum1(n int) int {
	if n < 1 {
		return 0
	}

	// len是0 cap是n; golang中append是在扩大len，当len超过数组的cap时，会触发cap扩容，指向新开辟的底层数组
	// ！！！ 如果指定len和cap相同，注意不要使用append触发数组扩容
	record := make([]int, n, n)
	return NQueensProcess1(0, record, n)
}

// NQueensProcess1 潜台词：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不共斜线
// 目前来到了第i行，在i行准备放皇后
// record[0..i-1]表示之前的行，放了的皇后位置
// n代表整体一共有多少行  0~n-1行
// 返回值是，摆完所有的皇后，合理的摆法有多少种
// 尝试过程
func NQueensProcess1(i int, record []int, n int) int {
	if i == n { // // 终止行
		return 1
	}
	// 没有到终止位置，还有皇后要摆
	res := 0
	// 当前行在i行，尝试i行所有的列  -> j
	for j := 0; j < n; j++ {
		// 当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行共列共斜线，
		// 如果是，认为有效，当前可以摆在j列的位置
		// 如果不是，认为无效
		if isValid(record, i, j) {
			// 当前存在i行的有效值为j列位置
			record[i] = j
			res += NQueensProcess1(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|
func isValid(record []int, i, j int) bool {
	// 之前的某个k行的皇后
	for k := 0; k < i; k++ {
		if j == record[k] || math.Abs(float64(record[k]-j)) == math.Abs(float64(i-k)) {
			return false
		}
	}
	return true
}

// NQueensNum2 n皇后摆放问题解法2。
// 请不要超过32皇后问题
func NQueensNum2(n int) int {
	if n < 1 || n > 32 {
		return 0
	}

	limit := 0
	if n == 32 {
		limit = -1
	} else {
		limit = (1 << n) - 1
	}

	return NQueensProcess2(limit, 0, 0, 0)
}

// NQueensProcess2 limit 划定了问题的规模 -> 固定
// 用位运算加速常数项时间
// colLim 列的限制，1的位置不能放皇后，0的位置可以
// leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
// rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
func NQueensProcess2(limit, colLim, leftDiaLim, rightDiaLim int)  int {
	if colLim == limit { // base case
		return 1
	}

	// 所有可以放皇后的位置，都在pos上
	// colLim | leftDiaLim | rightDiaLim   -> 总限制
	// ~ (colLim | leftDiaLim | rightDiaLim) -> 左侧的一坨0干扰，右侧每个1，可尝试

	// 把左侧的去反后的一坨1，移除掉
	pos := limit & (^(colLim | leftDiaLim | rightDiaLim))
	mostRightOne := 0
	res := 0
	for pos != 0 {
		// 提取出pos中，最右侧的1来，剩下位置都是0
		mostRightOne = pos & (^pos + 1)

		pos = pos - mostRightOne
		// int(uint(rightDiaLim | mostRightOne) >> 1 相当于java (rightDiaLim | mostRightOne) >>> 1 表示无符号右移
		res += NQueensProcess2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, int(uint(rightDiaLim | mostRightOne) >> 1))
	}
	return res
}

func main() {
	n := 5
	start := time.Now().Unix()
	fmt.Println(NQueensNum1(n))
	end := time.Now().Unix()
	fmt.Println(end - start)

	start2 := time.Now().Unix()
	fmt.Println(NQueensNum2(n))
	end2 := time.Now().Unix()
	fmt.Println(end2 - start2)
}
```