灵神常见算法

回溯

子集型回溯

17. 电话号码的字母组合 - 力扣（LeetCode）

var mapping = [...]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

func letterCombinations(digits string) (res []string) {
	if digits == "" {
		return 
	}
	
	n := len(digits)
	path := make([]rune, n)

	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			res = append(res, string(path))
			return
		}

		for _, c := range mapping[digits[i]-'0'] {
			path[i] = c
			dfs(i + 1)
		}
	}
	dfs(0)
	return
}

---

78. 子集 - 力扣（LeetCode）

func subsets(nums []int) (res [][]int) {
	n := len(nums)
	path := make([]int, 0, n)

	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			res = append(res, slices.Clone(path))
			return
		}
		dfs(i + 1) //不选

		path = append(path, nums[i])
		dfs(i + 1)                //选
		path = path[:len(path)-1] //恢复
	}
	dfs(0)
	return
}

动态规划

子序列

1143. 最长公共子序列 - 力扣（LeetCode）

从text1末尾选的一个字母当作x，从text2末尾选的一个字母当作y。

	x、y都选	选x不选y
s=abcdc	s=abcd	s=abcd
t=abc	t=abc	t=abc

x==y时，

• x、y都选，dfs(i - 1, j - 1) + 1

x!=y时，

• x、y都不选，dfs(i - 1, j - 1)
• 选x不选y，dfs(i - 1, j)
• 不选x选y，dfs(i, j - 1)

属于选和不选类型。

由于dfs(i - 1, j)或者dfs(i, j - 1)中，下一次会递归调用dfs(i - 1, j - 1)，因此都不选的情况可以忽略。

func longestCommonSubsequence1(text1 string, text2 string) int {
	n, m := len(text1), len(text2)

	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i < 0 || j < 0 {
			return 0
		}

		if text1[i] == text2[j] { //x==y，都选
			return dfs(i-1, j-1) + 1
		} else { //选x不选y 和 不选x选y
			return max(dfs(i-1, j), dfs(i, j-1))
		}
	}
	return dfs(n-1, m-1)
}

将深搜转换成递推

f[i][j] = f[i - 1][j - 1] + 1

f[i][j] = max(f[i - 1][j], f[i][j - 1])

式子有了，该确定边界了。

• 如果边界使用0到n-1和0到m-1，那么f[i-1][j-1]就会越界。
• 因此式子里的i和j全部加一，边界使用1到n和1到m

func longestCommonSubsequence(text1 string, text2 string) int {
	n, m := len(text1), len(text2)

	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, m+1)
	}

	for i, x := range text1 {
		for j, y := range text2 {
			if x == y { //x==y，都选
				f[i+1][j+1] = f[i][j] + 1
			} else { //选x不选y 和 不选x选y
				f[i+1][j+1] = max(f[i][j+1], f[i+1][j])
			}
		}
	}
	return f[n][m]
}

300. 最长递增子序列 - 力扣（LeetCode）

属于选和不选类型

• 使用选和不选，还需要一个参数存储上一个数。
• 枚举下一个数选什么，就不需要存储上一个数。

记忆化搜索：

func lengthOfLIS(nums []int) int {
	n := len(nums)
	mem := make([]int, n)

	var dfs func(int) int
	dfs = func(i int) int {
		if mem[i] > 0 {
			return mem[i]
		}

		l := 0
		for j, v := range nums[:i] { //选下一个更小的数
			if v < nums[i] {
				l = max(l, dfs(j))
			}
		}
		mem[i] = l + 1
		return mem[i]
	}

	ans := 0
	for i := 0; i < n; i++ { //循环，一次dfs只能搜索 i 为尾数的最长递增子序列
		ans = max(ans, dfs(i))
	}
	return ans
}