记忆化搜索入门
摘要
- 什么时候可以使用记忆化搜索
- DFS 和记忆化搜索的区别
- 如何用三行代码让 DFS 变成记忆化搜索
- 用记忆化搜索解决博弈型动态规划
- 记忆化搜索的缺陷
109 · 数字三角形
找出数字三角形中从上到下的一条最短路径
var triangle = [][]int{
{2},
{3, 4},
{6, 5, 7},
{4, 1, 8, 3},
}
(x,y) => (x+1,y), (x+1,y+1)
数字三角形 vs 二叉树
- n 层的数字三角形:O (n^2) 个节点
- n 层的满二叉树:O (2^n) 个节点
DFS: Traverse
时间复杂度:O (2^n)
有 2^n 条路径
var minimum int
func MinimumTotal(triangle [][]int) int {
minimum = math.MaxInt
traverse(triangle, 0, 0, 0)
return minimum
}
func traverse(triangle [][]int, x, y, pathSum int) {
if x == len(triangle) {
// 最内层的循环主体
minimum = min(minimum, pathSum)
return
}
traverse(triangle, x+1, y, pathSum+triangle[x][y])
traverse(triangle, x+1, y+1, pathSum+triangle[x][y])
}
DFS: Divide & Conquer
一个点左右两边同时也都是数字三角形,所以可以分治
时间复杂度:O (2^n)
func MinimumTotal(triangle [][]int) int {
return dnc(triangle, 0, 0)
}
func dnc(triangle [][]int, x, y int) int {
if x == len(triangle) {
return 0
}
l := dnc(triangle, x+1, y)
r := dnc(triangle, x+1, y+1)
return min(l, r) + triangle[x][y]
}
DFS: Divide & Conquer + Hash
时间复杂度:O (n^2)
func MinimumTotal(triangle [][]int) int {
return divideConquer(triangle, 0, 0, map[struct{ x, y int }]int{})
}
func divideConquer(triangle [][]int, x, y int, memo map[struct{ x, y int }]int) int {
if x == len(triangle) {
return 0
}
if v, ok := memo[struct {
x int
y int
}{x: x, y: y}]; ok {
return v
}
l := divideConquer(triangle, x+1, y, memo)
r := divideConquer(triangle, x+1, y+1, memo)
minimum := min(l, r) + triangle[x][y]
memo[struct {
x int
y int
}{x: x, y: y}] = minimum
return minimum
}
记忆化搜索 Memoization Search
将函数的计算结果保存下来,下次通过同样的参数访问时,直接返回保存下来的结果就叫做记忆化搜索。
问:
- 对这个函数有什么限制条件没有?
- 需要有返回值
- 和系统设计中的什么很像?
- cache
记忆化搜索通常能够将指数级别的时间复杂度降低到多项式级别。
记忆化搜索与动态规划
- 记忆化搜索的本质:动态规划
- 动态规划快的原因:避免了重复计算
- 记忆化搜索 = 动态规划 (DP)
- 记忆化搜索是动态规划的一种实现方式
- 记忆化搜索是用搜索的方式实现了动态规划
- 因此记忆化搜索,就是动态规划
1300 · 巴什博弈
记忆化搜索非常适合博弈型动态规划
func CanWinBash(n int) bool {
memo := make(map[int]bool)
return memoSearch(n, memo)
}
func memoSearch(n int, memo map[int]bool) bool {
if n <= 3 {
return true
}
if v, ok := memo[n]; ok {
return v
}
for i := 1; i < 4; i++ {
if !memoSearch(n-i, memo) {
memo[n] = true
return true
}
}
memo[n] = false
return false
}
这份代码有什么问题?
StackOverflow
- n 可能很大,深度达到 O (n) 级别
- 如果时间复杂度和递归深度都是 O (n) 级别会栈溢出
- 如果时间复杂度是 O (n^2) 级别,递归深度是 O (n) 级别就不会溢出
解决思路
通过记忆化搜索的代码得到 n=1,2,3,4,... 的小数据结果
找规律,发现 n % 4 == 0 是 false,其他是 true
进一步想到 n % 4 == 0 时,先手取 x,后手取 4-x 先手必败
反之先手取 n % 4 个石子就让对手面对必败局面
func CanWinBash(n int) bool {
return n%4 != 0
}
记忆化搜索的缺点
不适合解决 O (n) 时间复杂度的 DP 问题
因为会有 StackOverflow 的风险
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。