前置知识：从递归入手二维动态规划

从递归到三维动态规划，包含：

多维费用背包
严格位置依赖的三维动态规划
三维动态规划的空间压缩

三维动态规划

尝试函数有一个可变参数可以完全决定返回值，进而可以改出一维动态规划表的实现

同理，尝试函数有两个可变参数可以完全决定返回值，那么就可以改出两维动态规划的实现

同理，尝试函数有三个可变参数可以完全决定返回值，那么就可以改出三维动态规划的实现

大体过程都差不多

备注

多维费用背包问题就是很普通的动态规划

但是【必备】课程里还会安排背包 dp 的内容，那时候会把其他几种背包问题做汇总讲述

题目1.一和零

多维费用的 01 背包问题

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

输出：4

解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"}，因此答案是 4 。

其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"}。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1

输出：2

解释：最大的子集是 {"0", "1"}，所以答案是 2。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

测试链接

474.一和零

暴力递归

var (
	theStrs []string
	l int
)
 
func findMaxForm(strs []string, m int, n int) int {
	theStrs = strs
	l = len(strs)
	return f(0, m, n)
}
 
// str[i:] 自由选择，希望零的数量不超过 z、一的数量不超过 o
// 返回：最多能选多少个字符串
func f(i, z, o int) int {
	if i == l {
		// 没有字符串了
		return 0
	}
	// 情况一：不用 strs[i] 字符串
	p1 := f(i+1, z, o)
	// 情况二：用 strs[i] 字符串
	p2 := 0
	zeros, ones := getZerosAndOnesCount(theStrs[i])
	if zeros <= z && ones <= o {
		p2 = 1 + f(i+1, z-zeros, o-ones)
	}
	return max(p1, p2)
}
 
// 统计一个字符串中 0 的 1 的数量
func getZerosAndOnesCount(str string) (zeros, ones int) {
	n := len(str)
	for i := 0; i < n; i++ {
		if str[i] == '0' {
			zeros++
		} else {
			ones++
		}
	}
	return
}

记忆化搜索

var (
	theStrs []string
	l       int
	cache   [][][]int
)
 
func findMaxForm(strs []string, m int, n int) int {
	theStrs = strs
	l = len(strs)
	cache = make([][][]int, l)
	for i := range cache {
		cache[i] = make([][]int, m+1)
		for j := range cache[i] {
			cache[i][j] = make([]int, n+1)
			for k := range cache[i][j] {
				cache[i][j][k] = -1
			}
		}
	}
	return f(0, m, n)
}
 
// str[i:] 自由选择，希望零的数量不超过 z、一的数量不超过 o
// 返回：最多能选多少个字符串
func f(i, z, o int) int {
	if i == l {
		// 没有字符串了
		return 0
	}
	if cache[i][z][o] != -1 {
		return cache[i][z][o]
	}
	ans := 0
	// 情况一：不用 strs[i] 字符串
	p1 := f(i+1, z, o)
	// 情况二：用 strs[i] 字符串
	p2 := 0
	zeros, ones := getZerosAndOnesCount(theStrs[i])
	if zeros <= z && ones <= o {
		p2 = 1 + f(i+1, z-zeros, o-ones)
	}
	ans = max(p1, p2)
	cache[i][z][o] = ans
	return ans
}
 
// 统计一个字符串中 0 的 1 的数量
func getZerosAndOnesCount(str string) (zeros, ones int) {
	n := len(str)
	for i := 0; i < n; i++ {
		if str[i] == '0' {
			zeros++
		} else {
			ones++
		}
	}
	return
}

位置依赖

func findMaxForm(strs []string, m int, n int) int {
	l := len(strs)
	dp := make([][][]int, l+1)
	for i := range dp {
		dp[i] = make([][]int, m+1)
		for j := range dp[i] {
			dp[i][j] = make([]int, n+1)
		}
	}
	// 初始化：dp[l][*][*] 都是 0
 
	// 从上往下推
	for i := l - 1; i >= 0; i-- {
		zeros, ones := getZerosAndOnesCount(strs[i])
		// 同一层顺序随意
		for z := 0; z <= m; z++ {
			for o := 0; o <= n; o++ {
				p1 := dp[i+1][z][o]
				p2 := 0
				if zeros <= z && ones <= o {
					p2 = 1 + dp[i+1][z-zeros][o-ones]
				}
				dp[i][z][o] = max(p1, p2)
			}
		}
	}
	return dp[0][m][n]
}
 
// 统计一个字符串中 0 的 1 的数量
func getZerosAndOnesCount(str string) (zeros, ones int) {
	n := len(str)
	for i := 0; i < n; i++ {
		if str[i] == '0' {
			zeros++
		} else {
			ones++
		}
	}
	return
}

空间压缩

每一层的 dp 表可以复用（滚动数组），但要注意同一层的递推顺序了

func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
 
	// 不用考虑顺序了，把字符串都遍历了就行
	for _, str := range strs {
		zeros, ones := getZerosAndOnesCount(str)
		// z、o 从大往小推
		for z := m; z >= zeros; z-- {
			for o := n; o >= ones; o-- {
				dp[z][o] = max(dp[z][o], 1+dp[z-zeros][o-ones])
			}
		}
	}
	return dp[m][n]
}
 
// 统计一个字符串中 0 的 1 的数量
func getZerosAndOnesCount(str string) (zeros, ones int) {
	n := len(str)
	for i := 0; i < n; i++ {
		if str[i] == '0' {
			zeros++
		} else {
			ones++
		}
	}
	return
}

题目2.盈利计划

多维费用的 01 背包问题，和题目1 差不多

题目描述

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

示例 1：

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]

输出：2

解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。总的来说，有两种计划。

示例 2：

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]

输出：7

解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。

有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

测试链接

879.盈利计划

暴力递归

var (
	theGroup  []int
	theProfit []int
	l         int
)
 
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	theGroup = group
	theProfit = profit
	l = len(group)
	return f(0, n, minProfit)
}
 
// i：来到 i 号工作
// r：员工额度还有 r 人，如果 r<=0 说明已经没法再选择工作了
// s：利润还有 s 才能达标，如果 s<=0 说明之前的选择已经让利润达标了
// 返回：有多少种方案
func f(i, r, s int) int {
	// 人已经耗尽了，或工作耗尽了
	if r <= 0 || i == l {
		if s <= 0 {
			return 1
		} else {
			return 0
		}
	}
	// 不要当前工作
	p1 := f(i+1, r, s)
	// 要当前工作
	p2 := 0
	if r >= theGroup[i] {
		p2 = f(i+1, r-theGroup[i], s-theProfit[i])
	}
	return p1 + p2
}

记忆化搜索

const (
	MOD = 1e9 + 7
)
 
var (
	theGroup  []int
	theProfit []int
	l         int
	cache     [][][]int
)
 
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	theGroup = group
	theProfit = profit
	l = len(group)
	cache = make([][][]int, l)
	for i := range cache {
		cache[i] = make([][]int, n+1)
		for j := range cache[i] {
			cache[i][j] = make([]int, minProfit+1)
			for k := range cache[i][j] {
				cache[i][j][k] = -1
			}
		}
	}
	return f(0, n, minProfit)
}
 
// i：来到 i 号工作
// r：员工额度还有 r 人，如果 r<=0 说明已经没法再选择工作了
// s：利润还有 s 才能达标，如果 s<=0 说明之前的选择已经让利润达标了
// 返回：有多少种方案
func f(i, r, s int) int {
	// 人已经耗尽了，或工作耗尽了
	if r <= 0 || i == l {
		if s <= 0 {
			return 1
		} else {
			return 0
		}
	}
	if cache[i][r][s] != -1 {
		return cache[i][r][s]
	}
	// 不要当前工作
	p1 := f(i+1, r, s)
	// 要当前工作
	p2 := 0
	if r >= theGroup[i] {
		// max(s-theProfit[i], 0)：防止负数，缓存表越界
		p2 = f(i+1, r-theGroup[i], max(s-theProfit[i], 0))
	}
	ans := (p1 + p2) % MOD
	cache[i][r][s] = ans
	return ans
}

位置依赖

const (
	MOD = 1e9 + 7
)
 
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	l := len(group)
	dp := make([][][]int, l+1)
	for i := range dp {
		dp[i] = make([][]int, n+1)
		for j := range dp[i] {
			dp[i][j] = make([]int, minProfit+1)
		}
	}
	// 初始化：i == l（没有工作） && s == 0（利润已经达标）时有 1 种方案
	for r := 0; r <= n; r++ {
		dp[l][r][0] = 1
	}
 
	for i := l - 1; i >= 0; i-- {
		for r := 0; r <= n; r++ {
			for s := 0; s <= minProfit; s++ {
				// 不要当前工作
				p1 := dp[i+1][r][s]
				// 要当前工作
				p2 := 0
				if r >= group[i] {
					p2 = dp[i+1][r-group[i]][max(s-profit[i], 0)]
				}
				dp[i][r][s] = (p1 + p2) % MOD
			}
		}
	}
	return dp[0][n][minProfit]
}

空间压缩

const (
	MOD = 1e9 + 7
)
 
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	l := len(group)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, minProfit+1)
		// 初始化：i == l（没有工作） && s == 0（利润已经达标）时有 1 种方案
		dp[i][0] = 1
	}
 
	for i := l - 1; i >= 0; i-- {
		for r := n; r >= 0; r-- {
			for s := minProfit; s >= 0; s-- {
				// 不要当前工作
				p1 := dp[r][s]
				// 要当前工作
				p2 := 0
				if r >= group[i] {
					p2 = dp[r-group[i]][max(s-profit[i], 0)]
				}
				dp[r][s] = (p1 + p2) % MOD
			}
		}
	}
	return dp[n][minProfit]
}

题目3.骑士在棋盘上的概率

题目描述

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有 8 种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从 8 种可能的移动中选择一种（即使棋子会离开棋盘），然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回骑士在棋盘停止移动后仍留在棋盘上的概率。

示例 1：

输入：n = 3, k = 2, row = 0, column = 0

输出：0.0625

解释：有两步（到 (1,2)，(2,1)）可以让骑士留在棋盘上。

在每一个位置上，也有两种移动可以让骑士留在棋盘上。

骑士留在棋盘上的总概率是 0.0625。

示例 2：

输入：n = 1, k = 0, row = 0, column = 0

输出：1.00000

提示：

1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1

测试链接

688.骑士在棋盘上的概率

记忆化搜索

var (
	N     int
	cache [][][]float64
)
 
func knightProbability(n int, k int, row int, column int) float64 {
	N = n
	cache = make([][][]float64, n)
	for i := range cache {
		cache[i] = make([][]float64, n)
		for j := range cache[i] {
			cache[i][j] = make([]float64, k+1)
			for l := range cache[i][j] {
				cache[i][j][l] = -1
			}
		}
	}
	return f(row, column, k)
}
 
// 从 (i, j) 出发还有 k 步要走，返回最后在棋盘上的概率
func f(i, j, k int) float64 {
	// 已越界
	if i < 0 || i >= N || j < 0 || j >= N {
		return 0
	}
	if cache[i][j][k] != -1 {
		return cache[i][j][k]
	}
	var ans float64
	if k == 0 {
		ans = 1
	} else {
		ans = f(i-2, j+1, k-1) / 8
		ans += f(i-1, j+2, k-1) / 8
		ans += f(i+1, j+2, k-1) / 8
		ans += f(i+2, j+1, k-1) / 8
		ans += f(i+2, j-1, k-1) / 8
		ans += f(i+1, j-2, k-1) / 8
		ans += f(i-1, j-2, k-1) / 8
		ans += f(i-2, j-1, k-1) / 8
	}
	cache[i][j][k] = ans
	return ans
}

位置依赖

var (
	N  int
	dp [][][]float64
)
 
func knightProbability(n int, k int, row int, column int) float64 {
	N = n
	// dp[i][j][k]：骑士在 (i, j) 位置还有 k 步，留着棋盘上的概率
	dp = make([][][]float64, n)
	for i := range dp {
		dp[i] = make([][]float64, n)
		for j := range dp[i] {
			dp[i][j] = make([]float64, k+1)
			// 初始化： k == 0 时，概率是 1
			dp[i][j][0] = 1
		}
	}
	for l := 1; l <= k; l++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				doDp(i, j, l, -2, +1)
				doDp(i, j, l, -1, +2)
				doDp(i, j, l, +1, +2)
				doDp(i, j, l, +2, +1)
				doDp(i, j, l, +2, -1)
				doDp(i, j, l, +1, -2)
				doDp(i, j, l, -1, -2)
				doDp(i, j, l, -2, -1)
			}
		}
	}
	return dp[row][column][k]
}
 
// 检查 (i+iOffset, j+jOffset) 是否越界
// 不越界就正确填充 dp 表
func doDp(i, j, k, iOffset, jOffset int) {
	if i+iOffset < 0 || i+iOffset >= N || j+jOffset < 0 || j+jOffset >= N {
		return
	}
	dp[i][j][k] += dp[i+iOffset][j+jOffset][k-1] / 8
}

空间压缩

题目1 和题目2 每一层依赖上一层一边的地方，填充时不会影响之后格子的依赖，可以一层滚动

而本题由于每一层的依赖关系是四面八方的，所以要使用两层轮替递推

var (
	N   int
	dp0 [][]float64
	dp1 [][]float64
)
 
func knightProbability(n int, k int, row int, column int) float64 {
	N = n
	dp0 = make([][]float64, n)
	dp1 = make([][]float64, n)
	for i := 0; i < n; i++ {
		dp0[i] = make([]float64, n)
		dp1[i] = make([]float64, n)
		for j := 0; j < n; j++ {
			// 初始化： k == 0 时，概率是 1
			dp0[i][j] = 1
		}
	}
	for l := 1; l <= k; l++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				// 清除上上层的数据
				dp1[i][j] = 0
				doDp(i, j, -2, +1)
				doDp(i, j, -1, +2)
				doDp(i, j, +1, +2)
				doDp(i, j, +2, +1)
				doDp(i, j, +2, -1)
				doDp(i, j, +1, -2)
				doDp(i, j, -1, -2)
				doDp(i, j, -2, -1)
			}
		}
		dp0, dp1 = dp1, dp0
	}
	// k == 0：dp0 都是 1
	// k > 0：dp0 和 dp1 已经交换
	// 两种情况都是正确的
	return dp0[row][column]
}
 
// 检查 (i+iOffset, j+jOffset) 是否越界
// 不越界就正确填充 dp 表
func doDp(i, j, iOffset, jOffset int) {
	if i+iOffset < 0 || i+iOffset >= N || j+jOffset < 0 || j+jOffset >= N {
		return
	}
	dp1[i][j] += dp0[i+iOffset][j+jOffset] / 8
}

题目4.矩阵中和能被 K 整除的路径

题目描述

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往下或者往右，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 10^9 + 7 取余的结果。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 5 * 10^4
1 <= m * n <= 5 * 10^4
0 <= grid[i][j] <= 100
1 <= k <= 50

测试链接

2435.矩阵中和能被 K 整除的路径

思路

暴力递归

const (
	MOD = 1e9 + 7
)
 
var (
	theGrid [][]int
	n       int
	m       int
	K       int
)
 
func numberOfPaths(grid [][]int, k int) int {
	theGrid = grid
	n = len(grid)
	m = len(grid[0])
	K = k
	return f(0, 0, 0)
}
 
// 当前在 (i, j) 位置，要到 (n-1, m-1)
// 有多少条路径，累加和 %k 的余数是 r
func f(i, j, r int) int {
	// 当前就在目标点，只需要考虑当前点是否 %k 的余数是 r 即可
	if i == n-1 && j == m-1 {
		if theGrid[i][j]%K == r {
			return 1
		} else {
			return 0
		}
	}
	// 后续需要凑出来的余数
	need := (K + r - (theGrid[i][j] % K)) % K
	// 或者写条件转移
	// need := 0
	// if theGrid[i][j]%K <= r {
	// 	need = r - theGrid[i][j]%K
	// } else {
	// 	need = K + r - theGrid[i][j]%K
	// }
	ans := 0
	if i < n-1 {
		ans = f(i+1, j, need)
	}
	if j < m-1 {
		ans = (ans + f(i, j+1, need)) % MOD
	}
	return ans
}

记忆化搜索

const (
	MOD = 1e9 + 7
)
 
var (
	theGrid [][]int
	n       int
	m       int
	K       int
	cache   [][][]int
)
 
func numberOfPaths(grid [][]int, k int) int {
	theGrid = grid
	n = len(grid)
	m = len(grid[0])
	K = k
	cache = make([][][]int, n)
	for i := range cache {
		cache[i] = make([][]int, m)
		for j := range cache[i] {
			cache[i][j] = make([]int, k)
			for r := range cache[i][j] {
				cache[i][j][r] = -1
			}
		}
	}
	return f(0, 0, 0)
}
 
// 当前在 (i, j) 位置，要到 (n-1, m-1)
// 有多少条路径，累加和 %k 的余数是 r
func f(i, j, r int) int {
	// 当前就在目标点，只需要考虑当前点是否 %k 的余数是 r 即可
	if i == n-1 && j == m-1 {
		if theGrid[i][j]%K == r {
			return 1
		} else {
			return 0
		}
	}
	if cache[i][j][r] != -1 {
		return cache[i][j][r]
	}
	// 后续需要凑出来的余数
	need := (K + r - (theGrid[i][j] % K)) % K
	ans := 0
	if i < n-1 {
		ans = f(i+1, j, need)
	}
	if j < m-1 {
		ans = (ans + f(i, j+1, need)) % MOD
	}
	cache[i][j][r] = ans
	return ans
}

位置依赖

以 n、m 为二维，r 为第三维

n、m 二维中，每个位置依赖下、右两个格子，而第三维 r 则可能大、可能小

初始化：(n-1, m-1) 位置 grid[n-1][m-1] % k 为 1，其余为 0；然后初始化 n-1 行和 m-1 列

const (
	MOD = 1e9 + 7
)
 
func numberOfPaths(grid [][]int, k int) int {
	n := len(grid)
	m := len(grid[0])
	// dp[i][j][r]: 当前在 (i, j) 位置，要到 (n-1, m-1)
	// 有多少条路径，累加和 %k 的余数是 r
	dp := make([][][]int, n)
	for i := range dp {
		dp[i] = make([][]int, m)
		for j := range dp[i] {
			dp[i][j] = make([]int, k)
		}
	}
 
	// 初始化
	// dp[n-1][m-1][*]
	dp[n-1][m-1][grid[n-1][m-1]%k] = 1
	// dp m-1 列，从下往上，每个格子只依赖下侧格子
	for i := n - 2; i >= 0; i-- {
		for r := 0; r < k; r++ {
			dp[i][m-1][r] = dp[i+1][m-1][(k+r-(grid[i][m-1]%k))%k]
		}
	}
	// dp n-1 行，从右往左，每个格子只依赖右侧格子
	for j := m - 2; j >= 0; j-- {
		for r := 0; r < k; r++ {
			dp[n-1][j][r] = dp[n-1][j+1][(k+r-(grid[n-1][j]%k))%k]
		}
	}
 
	// 正常位置：从下往上、从右往左
	for i := n - 2; i >= 0; i-- {
		for j := m - 2; j >= 0; j-- {
			for r := 0; r < k; r++ {
				need := (k + r - (grid[i][j] % k)) % k
				dp[i][j][r] = (dp[i+1][j][need] + dp[i][j+1][need]) % MOD
			}
		}
	}
	return dp[0][0][0]
}

题目5.扰乱字符串

题目描述

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
- 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
- 随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
- 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

提示：

s1.length == s2.length
1 <= s1.length <= 30
s1 和 s2 由小写英文字母组成

测试链接

87.扰乱字符串

暴力递归（4 个参数）

var (
	S1 string
	S2 string
	n  int
)
 
func isScramble(s1 string, s2 string) bool {
	S1 = s1
	S2 = s2
	n = len(s1)
	return f(0, n-1, 0, n-1)
}
 
// s1[l1:r1+1] 和 s2[l2:r2+1] 是不是扰乱串的关系
// 要求：r1-l1 == r2-l2
func f(l1, r1, l2, r2 int) bool {
	// 只有一个字符
	if l1 == r1 {
		return S1[l1] == S2[l2]
	}
	// 不交换位置
	for i, j := l1, l2; i < r1; i, j = i+1, j+1 {
		if f(l1, i, l2, j) && f(i+1, r1, j+1, r2) {
			return true
		}
	}
	// 交换位置
	for i, j := l1, r2; i < r1; i, j = i+1, j-1 {
		if f(l1, i, j, r2) && f(i+1, r1, l2, j-1) {
			return true
		}
	}
	return false
}

暴力递归（3 个参数）

因为长度相同，所以只需要三个可变参数即可

var (
	S1 string
	S2 string
	n  int
)
 
func isScramble(s1 string, s2 string) bool {
	S1 = s1
	S2 = s2
	n = len(s1)
	return f(0, 0, n)
}
 
// s1[l1:l1+length] 和 s2[l2:l2+length] 是不是扰乱串的关系
func f(l1, l2, length int) bool {
	// 只有一个字符
	if length == 1 {
		return S1[l1] == S2[l2]
	}
	// 不交换位置
	for k := 0; k < length; k++ {
		if f(l1, l2, k) && f(l1+k, l2+k, length-k) {
			return true
		}
	}
	// 交换位置
	for i, j, k := l1+1, l2+length-1, 1; k < length; i, j, k = i+1, j-1, k+1 {
		if f(l1, j, k) && f(i, l2, length-k) {
			return true
		}
	}
	return false
}

记忆化搜索

var (
	S1    string
	S2    string
	n     int
	cache [][][]*bool
)
 
func isScramble(s1 string, s2 string) bool {
	S1 = s1
	S2 = s2
	n = len(s1)
	// cache[l1][l2][length]:
	// 1. nil: 没展开过
	// 2. true: 展开过，返回的结果是 true
	// 3. false: 展开过，返回的结果是 false
	cache = make([][][]*bool, n)
	for i := range cache {
		cache[i] = make([][]*bool, n)
		for j := range cache[i] {
			cache[i][j] = make([]*bool, n+1)
		}
	}
	return f(0, 0, n)
}
 
// s1[l1:l1+length] 和 s2[l2:l2+length] 是不是扰乱串的关系
func f(l1, l2, length int) bool {
	// 只有一个字符
	if length == 1 {
		return S1[l1] == S2[l2]
	}
	if cache[l1][l2][length] != nil {
		return *cache[l1][l2][length]
	}
	ans := false
	// 不交换位置
	for k := 0; k < length; k++ {
		if f(l1, l2, k) && f(l1+k, l2+k, length-k) {
			ans = true
			break
		}
	}
	// 交换位置
	if !ans {
		for i, j, k := l1+1, l2+length-1, 1; k < length; i, j, k = i+1, j-1, k+1 {
			if f(l1, j, k) && f(i, l2, length-k) {
				ans = true
				break
			}
		}
	}
	cache[l1][l2][length] = &ans
	return ans
}

位置依赖

func isScramble(s1 string, s2 string) bool {
	n := len(s1)
	// cache[l1][l2][length]
	dp := make([][][]bool, n)
	for l1 := range dp {
		dp[l1] = make([][]bool, n)
		for l2 := range dp[l1] {
			dp[l1][l2] = make([]bool, n+1)
			// 初始化：length == 1
			dp[l1][l2][1] = s1[l1] == s2[l2]
		}
	}
	for length := 2; length <= n; length++ {
		// 注意如下的边界条件 : l1 <= n-length, l2 <= n-length
		// 是用不到的格子，强行填充的话转移方程会下标越界
		for l1 := 0; l1 <= n-length; l1++ {
			for l2 := 0; l2 <= n-length; l2++ {
				// 不交换位置
				for k := 1; k < length; k++ {
					if dp[l1][l2][k] && dp[l1+k][l2+k][length-k] {
						dp[l1][l2][length] = true
						break
					}
				}
				// 交换位置
				if !dp[l1][l2][length] {
					for i, j, k := l1+1, l2+length-1, 1; k < length; i, j, k = i+1, j-1, k+1 {
						if dp[l1][j][k] && dp[i][l2][length-k] {
							dp[l1][l2][length] = true
							break
						}
					}
				}
			}
		}
	}
	return dp[0][0][n]
}

复杂度

动态规划方法的时间复杂度：动态规划表的大小 * 每个格子的枚举代价

前 4 个题目每个格子的枚举代价都是 $O (1)$ ，时间复杂度就是动态规划表的大小（是正常动态规划表的大小，不是空间压缩后的大小。空间压缩只降低了空间，整体逻辑流程是不变的，不会影响时间）

题目5 每个格子的枚举代价是 $O (n)$ ，动态规划表的大小是 $O (n^{3})$ ，所以时间复杂度是 $O (n^{4})$

My-Notes

Explorer

051.从递归入手三维动态规划

三维动态规划 §

备注 §

题目1.一和零 §

题目描述 §

测试链接 §

暴力递归 §

记忆化搜索 §

位置依赖 §

空间压缩 §

题目2.盈利计划 §

题目描述 §

测试链接 §

暴力递归 §

记忆化搜索 §

位置依赖 §

空间压缩 §

题目3.骑士在棋盘上的概率 §

题目描述 §

测试链接 §

记忆化搜索 §

位置依赖 §

空间压缩 §

题目4.矩阵中和能被 K 整除的路径 §

题目描述 §

测试链接 §

思路 §

暴力递归 §

记忆化搜索 §

位置依赖 §

题目5.扰乱字符串 §

题目描述 §

测试链接 §

暴力递归（4 个参数） §

暴力递归（3 个参数） §

记忆化搜索 §

位置依赖 §

复杂度 §

Graph View

Table of Contents

Backlinks

三维动态规划

备注

题目1.一和零

题目描述

测试链接

暴力递归

记忆化搜索

位置依赖

空间压缩

题目2.盈利计划

题目描述

测试链接

暴力递归

记忆化搜索

位置依赖

空间压缩

题目3.骑士在棋盘上的概率

题目描述

测试链接

记忆化搜索

位置依赖

空间压缩

题目4.矩阵中和能被 K 整除的路径

题目描述

测试链接

思路

暴力递归

记忆化搜索

位置依赖

题目5.扰乱字符串

题目描述

测试链接

暴力递归（4 个参数）

暴力递归（3 个参数）

记忆化搜索

位置依赖

复杂度