LeetCode Go · 动态规划（2）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

198. 打家劫舍

中等3 种解法

标签：数组、动态规划

题目、示例与约束

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

 

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

 

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

方法一：记忆化搜索 · Go 实现

思考

相邻房屋不能都偷，求最大金额。枚举子集要检查相邻约束，房屋数虽不大，重叠子问题很多。从第 $i$ 间出发：偷则跳到 $i+2$，不偷则到 $i+1$，取较大者。记忆化后每个下标只算一次。

我们设计一个函数 $\mathit{\text{dfs}}(i)$，表示从第 $i$ 间房屋开始偷窃能够得到的最高金额。那么答案即为 $\mathit{\text{dfs}}(0)$。

函数 $\mathit{\text{dfs}}(i)$ 的执行过程如下：

• 如果 $i\ge \mathit{\text{len}}(\mathit{\text{nums}})$，表示所有房屋都被考虑过了，直接返回 $0$；
• 否则，考虑偷窃第 $i$ 间房屋，那么 $\mathit{\text{dfs}}(i)=\mathit{\text{nums}}[i]+\mathit{\text{dfs}}(i+2)$；不偷窃第 $i$ 间房屋，那么 $\mathit{\text{dfs}}(i)=\mathit{\text{dfs}}(i+1)$。
• 返回 $max(\mathit{\text{nums}}[i]+\mathit{\text{dfs}}(i+2),\mathit{\text{dfs}}(i+1))$。

为了避免重复计算，我们使用记忆化搜索的方法，将 $\mathit{\text{dfs}}(i)$ 的结果保存在一个数组或哈希表中，每次计算前先查询是否已经计算过，如果计算过直接返回结果。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组长度。

func rob(nums []int) int {
	n := len(nums)
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if f[i] < 0 {
			f[i] = max(nums[i]+dfs(i+2), dfs(i+1))
		}
		return f[i]
	}
	return dfs(0)
}

方法二：动态规划 · Go 实现

思考

方法一是递归。 $f[i]$ 表示前 $i$ 间的最大金额，转移只看「偷第 $i$ 间则加 $f[i-2]$，否则继承 $f[i-1]$」，自底向上填表。

我们定义 $f[i]$ 表示前 $i$ 间房屋能偷窃到的最高总金额，初始时 $f[0]=0$, $f[1]=nums[0]$。

考虑 $i>1$ 的情况，第 $i$ 间房屋有两个选项：

• 不偷窃第 $i$ 间房屋，偷窃总金额为 $f[i-1]$；
• 偷窃第 $i$ 间房屋，偷窃总金额为 $f[i-2]+nums[i-1]$；

因此，我们可以得到状态转移方程：

$$f[i]=\{\begin{array}{ll}0,& i=0\\ nums[0],& i=1\\ max(f[i-1],f[i-2]+nums[i-1]),& i>1\end{array}$$

最终的答案即为 $f[n]$，其中 $n$ 是数组的长度。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组长度。

func rob(nums []int) int {
	n := len(nums)
	f := make([]int, n+1)
	f[1] = nums[0]
	for i := 2; i <= n; i++ {
		f[i] = max(f[i-1], f[i-2]+nums[i-1])
	}
	return f[n]
}

方法三：动态规划（空间优化） · Go 实现

思考

方法二的 $f[i]$ 只依赖前两项，两个变量滚动即可，空间降为 $O(1)$。

我们注意到，当 $i>2$ 时， $f[i]$ 只和 $f[i-1]$ 与 $f[i-2]$ 有关，因此我们可以使用两个变量代替数组，将空间复杂度降到 $O(1)$。

func rob(nums []int) int {
	f, g := 0, 0
	for _, x := range nums {
		f, g = max(f, g), f+x
	}
	return max(f, g)
}

力扣原题 · Doocs 题解来源

213. 打家劫舍 II

中等1 种解法

标签：数组、动态规划

题目、示例与约束

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

 

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

 

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

方法一：动态规划 · Go 实现

思考

房屋围成环，第一间与最后一间相邻，不能同时偷，线性打家劫舍不能直接套用。

为此拆成两段：不偷第一间、或不偷最后一间，分别做线性 DP，再取较大者；仅一间时直接返回该值。

环状排列意味着第一个房屋和最后一个房屋中最多只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房屋子问题。

时间复杂度 $O(n)$，其中 $n$ 是数组长度。空间复杂度 $O(1)$。

func rob(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}
	return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1))
}

func robRange(nums []int, l, r int) int {
	f, g := 0, 0
	for _, x := range nums[l : r+1] {
		f, g = max(f, g), f+x
	}
	return max(f, g)
}

力扣原题 · Doocs 题解来源

221. 最大正方形

中等1 种解法

标签：数组、动态规划、矩阵

题目、示例与约束

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

 

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

方法一：动态规划 · Go 实现

思考

枚举每个右下角并向上检查正方形，在网格较大时重复访问。以 $(i,j)$ 为右下角的最大边长，受限于其左、上、左上三个位置的最大边长。

为此令 $dp[i+1][j+1]$ 表示该最大边长：格子为 $0$ 则为 $0$，否则取三者最小值加一。答案是最大边长的平方。

我们定义 $dp[i+1][j+1]$ 表示以下标 $(i,j)$ 作为正方形右下角的最大正方形边长。答案为所有 $dp[i+1][j+1]$ 中的最大值。

状态转移方程为：

$$dp[i+1][j+1]=\{\begin{array}{ll}0& \mathit{\text{if }}matrix[i][j]{=}^{\prime }{0}^{\prime }\\ min(dp[i][j],dp[i][j+1],dp[i+1][j])+1& \mathit{\text{if }}matrix[i][j]{=}^{\prime }{1}^{\prime }\end{array}$$

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	mx := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				dp[i+1][j+1] = min(min(dp[i][j+1], dp[i+1][j]), dp[i][j]) + 1
				mx = max(mx, dp[i+1][j+1])
			}
		}
	}
	return mx * mx
}

力扣原题 · Doocs 题解来源

233. 数字 1 的个数

困难1 种解法

标签：递归、数学、动态规划

题目、示例与约束

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

 

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

 

提示：

• 0 <= n <= 109

方法一：数位 DP · Go 实现

思考

逐个检查 $[1,n]$ 中的每一位，在 $n$ 很大时不可行。 $1$ 的出现次数只与数位及上界有关，适合数位 DP。

将 $n$ 视为数字串，记忆化搜索 $dfs(i,\mathit{\text{cnt}},\mathit{\text{limit}})$：从高位填到第 $i$ 位、已出现 $\mathit{\text{cnt}}$ 个 $1$，并记录是否贴着上界。枚举当前位数字后累加方案。

这道题实际上是求在给定区间 $[l,..r]$ 中，数字中出现 $1$ 个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。

对于区间 $[l,..r]$ 问题，我们一般会将其转化为 $[1,..r]$ 然后再减去 $[1,..l-1]$ 的问题，即：

$$ans=\sum _{i=1}^{r}an{s}_i-\sum _{i=1}^{l-1}an{s}_i$$

不过对于本题而言，我们只需要求出区间 $[1,..r]$ 的值即可。

这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。

基本步骤如下：

我们首先将数字 $n$ 转化为字符串 $s$。然后我们设计一个函数 $\mathit{\text{dfs}}(i,\mathit{\text{cnt}},\mathit{\text{limit}})$，其中：

• 数字 $i$ 表示当前搜索到的位置，我们从高位开始搜索，即 $i=0$ 表示最高位。
• 数字 $\mathit{\text{cnt}}$ 表示当前数字中 $1$ 出现的次数。
• 布尔值 $\mathit{\text{limit}}$ 表示当前是否受到上界的限制。

函数的执行过程如下：

如果 $i$ 超过了数字 $n$ 的长度，说明搜索结束，直接返回 $cnt$。如果 $\mathit{\text{limit}}$ 为真，那么 $up$ 为当前数字的第 $i$ 位，否则 $up=9$。接下来，我们遍历 $j$ 从 $0$ 到 $up$，对于每一个 $j$：

• 如果 $j$ 等于 $1$，我们将 $cnt$ 加一。
• 递归调用 $\mathit{\text{dfs}}(i+1,\mathit{\text{cnt}},\mathit{\text{limit}}\wedge j=up)$。

答案为 $\mathit{\text{dfs}}(0,0,\text{True})$。

时间复杂度 $O(m^2\times D)$，空间复杂度 $O(m^2)$。其中 $m$ 为数字 $n$ 的长度，而 $D=10$。

相似题目：

• 357. 统计各位数字都不同的数字个数
• 600. 不含连续 1 的非负整数
• 788. 旋转数字
• 902. 最大为 N 的数字组合
• 1012. 至少有 1 位重复的数字
• 2376. 统计特殊整数

func countDigitOne(n int) int {
	s := strconv.Itoa(n)
	m := len(s)
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, m)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, cnt int, limit bool) int
	dfs = func(i, cnt int, limit bool) int {
		if i >= m {
			return cnt
		}
		if !limit && f[i][cnt] != -1 {
			return f[i][cnt]
		}
		up := 9
		if limit {
			up = int(s[i] - '0')
		}
		ans := 0
		for j := 0; j <= up; j++ {
			t := 0
			if j == 1 {
				t = 1
			}
			ans += dfs(i+1, cnt+t, limit && j == up)
		}
		if !limit {
			f[i][cnt] = ans
		}
		return ans
	}
	return dfs(0, 0, true)
}

力扣原题 · Doocs 题解来源

241. 为运算表达式设计优先级

中等1 种解法

标签：递归、记忆化、数学、字符串、动态规划、括号序列

题目、示例与约束

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

 

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

 

提示：

• 1 <= expression.length <= 20
• expression 由数字和算符 '+'、'-' 和 '*' 组成。
• 输入表达式中的所有整数值在范围 [0, 99] 
• 输入表达式中的所有整数都没有前导 '-' 或 '+' 表示符号。

方法一：记忆化搜索 · Go 实现

思考

不同加括号方式对应以某个运算符为根的划分，枚举划分后左右各自求值再组合。子表达式会被重复计算。

对每个运算符切开，递归求左右所有可能值并按该运算符合并，用记忆化缓存同一子串的结果。

var memo = map[string][]int{}

func diffWaysToCompute(expression string) []int {
	return dfs(expression)
}

func dfs(exp string) []int {
	if v, ok := memo[exp]; ok {
		return v
	}
	if len(exp) < 3 {
		v, _ := strconv.Atoi(exp)
		return []int{v}
	}
	ans := []int{}
	for i, c := range exp {
		if c == '-' || c == '+' || c == '*' {
			left, right := dfs(exp[:i]), dfs(exp[i+1:])
			for _, a := range left {
				for _, b := range right {
					if c == '-' {
						ans = append(ans, a-b)
					} else if c == '+' {
						ans = append(ans, a+b)
					} else {
						ans = append(ans, a*b)
					}
				}
			}
		}
	}
	memo[exp] = ans
	return ans
}

力扣原题 · Doocs 题解来源

256. 粉刷房子 🔒

中等1 种解法

标签：数组、动态规划

题目、示例与约束

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

 

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

示例 2：

输入: costs = [[7,6,2]]
输出: 2

 

提示:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

方法一：动态规划 · Go 实现

思考

相邻房屋颜色不能相同，枚举着色方案过多。第 $i$ 间选某色的最小花费，只依赖上一间另外两色的最小花费。

用三个变量滚动记录刷成三种颜色的累计最小代价，最后取最小者。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 表示房子的数量。

func minCost(costs [][]int) int {
	r, g, b := 0, 0, 0
	for _, cost := range costs {
		_r, _g, _b := r, g, b
		r = min(_g, _b) + cost[0]
		g = min(_r, _b) + cost[1]
		b = min(_r, _g) + cost[2]
	}
	return min(r, min(g, b))
}

力扣原题 · Doocs 题解来源

264. 丑数 II

中等2 种解法

标签：哈希表、数学、动态规划、堆（优先队列）

题目、示例与约束

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

 

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

 

提示：

• 1 <= n <= 1690

方法一：优先队列（最小堆） · Go 实现

思考

从小到大枚举并试除判定丑数，在第 $n$ 项较大时浪费大量非丑数。丑数只由已有丑数乘 $2,3,5$ 得到。

最小堆弹出当前最小丑数，再把其乘积入堆，哈希去重，弹出 $n$ 次即第 $n$ 个。

初始时，将第一个丑数 $1$ 加入堆。每次取出堆顶元素 $x$，由于 $2x$, $3x$, $5x$ 也是丑数，因此将它们加入堆中。为了避免重复元素，可以用哈希表 $vis$ 去重。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。

func nthUglyNumber(n int) int {
	h := IntHeap([]int{1})
	heap.Init(&h)
	ans := 1
	vis := map[int]bool{1: true}
	for n > 0 {
		ans = heap.Pop(&h).(int)
		for _, v := range []int{2, 3, 5} {
			nxt := ans * v
			if !vis[nxt] {
				vis[nxt] = true
				heap.Push(&h, nxt)
			}
		}
		n--
	}
	return ans
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

方法二：动态规划 · Go 实现

思考

堆与去重集合占用额外空间且带对数。用三个指针指向下一个应乘 $2,3,5$ 的丑数，每次取三者最小写入 $dp$，相等的指针一并前进以免重复。

定义数组 $dp$，其中 $dp[i-1]$ 表示第 $i$ 个丑数，那么第 $n$ 个丑数就是 $dp[n-1]$。最小的丑数是 $1$，所以 $dp[0]=1$。

定义 $3$ 个指针 $p_2$, $p_3$ 和 $p_5$，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都指向 $0$。

当 $i$ 在 $[1,2..n-1]$ 范围内，我们更新 $dp[i]=min(dp[p_2]\times 2,dp[p_3]\times 3,dp[p_5]\times 5)$，然后分别比较 $dp[i]$ 与 $dp[p_2]\times 2$, $dp[p_3]\times 3$, $dp[p_5]\times 5$ 是否相等，若是，则对应的指针加 $1$。

最后返回 $dp[n-1]$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func nthUglyNumber(n int) int {
	dp := make([]int, n)
	dp[0] = 1
	p2, p3, p5 := 0, 0, 0
	for i := 1; i < n; i++ {
		next2, next3, next5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
		dp[i] = min(next2, min(next3, next5))
		if dp[i] == next2 {
			p2++
		}
		if dp[i] == next3 {
			p3++
		}
		if dp[i] == next5 {
			p5++
		}
	}
	return dp[n-1]
}

力扣原题 · Doocs 题解来源

265. 粉刷房子 II 🔒

困难1 种解法

标签：数组、动态规划

题目、示例与约束

假如有一排房子共有 n 幢，每个房子可以被粉刷成 k 种颜色中的一种。房子粉刷成不同颜色的花费成本也是不同的。你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

每个房子粉刷成不同颜色的花费以一个 n x k 的矩阵表示。

• 例如，costs[0][0] 表示第 0 幢房子粉刷成 0 号颜色的成本；costs[1][2] 表示第 1 幢房子粉刷成 2 号颜色的成本，以此类推。

返回 粉刷完所有房子的最低成本 。

 

示例 1：

输入: costs = [[1,5,3],[2,9,4]]
输出: 5
解释: 
将房子 0 刷成 0 号颜色，房子 1 刷成 2 号颜色。花费: 1 + 4 = 5; 
或者将 房子 0 刷成 2 号颜色，房子 1 刷成 0 号颜色。花费: 3 + 2 = 5. 

示例 2:

输入: costs = [[1,3],[2,4]]
输出: 5

 

提示：

• costs.length == n
• costs[i].length == k
• 1 <= n <= 100
• 2 <= k <= 20
• 1 <= costs[i][j] <= 20

 

进阶：您能否在 O(nk) 的时间复杂度下解决此问题？

方法一：动态规划 · Go 实现

思考

相邻房屋颜色不同， $k$ 种颜色时枚举方案过多。第 $i$ 间刷色 $j$ 的最小花费，等于上一间除 $j$ 外的最小花费加上 $costs[i][j]$。

滚动一维数组 $f$，对每间房、每种颜色扫描上一行其余颜色取最小。

定义 $f[i][j]$ 表示粉刷前 $i$ 个房子，且最后一个房子被粉刷成第 $j$ 种颜色的最小花费。答案为 $\underset{0\le j<k}{min}f[n][j]$。

对于 $f[i][j]$，可以从 $f[i-1][j^{\prime }]$ 转移而来，其中 $j^{\prime }\ne j$。因此，可以得到状态转移方程：

$$f[i][j]=\underset{0\le j^{\prime }<k,j^{\prime }\ne j}{min}f[i-1][j^{\prime }]+costs[i-1][j]$$

由于 $f[i][j]$ 只与 $f[i-1][j^{\prime }]$ 有关，因此可以使用滚动数组优化空间复杂度。

时间复杂度 $O(n\times k^2)$，空间复杂度 $O(k)$。其中 $n$ 和 $k$ 分别为房子数量和颜色数量。

func minCostII(costs [][]int) int {
	n, k := len(costs), len(costs[0])
	f := cp(costs[0])
	for i := 1; i < n; i++ {
		g := cp(costs[i])
		for j := 0; j < k; j++ {
			t := math.MaxInt32
			for h := 0; h < k; h++ {
				if h != j && t > f[h] {
					t = f[h]
				}
			}
			g[j] += t
		}
		f = g
	}
	return slices.Min(f)
}

func cp(arr []int) []int {
	t := make([]int, len(arr))
	copy(t, arr)
	return t
}

力扣原题 · Doocs 题解来源

276. 栅栏涂色 🔒

中等2 种解法

标签：动态规划

题目、示例与约束

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，请你按下述规则为栅栏设计涂色方案：

• 每个栅栏柱可以用其中 一种 颜色进行上色。
• 相邻的栅栏柱 最多连续两个 颜色相同。

给你两个整数 k 和 n ，返回所有有效的涂色 方案数 。

 

示例 1：

输入：n = 3, k = 2
输出：6
解释：所有的可能涂色方案如上图所示。注意，全涂红或者全涂绿的方案属于无效方案，因为相邻的栅栏柱 最多连续两个 颜色相同。

示例 2：

输入：n = 1, k = 1
输出：1

示例 3：

输入：n = 7, k = 2
输出：42

 

提示：

• 1 <= n <= 50
• 1 <= k <= 105
• 题目数据保证：对于输入的 n 和 k ，其答案在范围 [0, 231 - 1] 内

方法一：动态规划 · Go 实现

思考

至多连续两根同色，第 $i$ 根要么与前一根不同色，要么相同但前两根必须不同。

令 $f[i]$ 为末两根不同色的方案， $g[i]$ 为末两根同色： $f[i]=(f[i-1]+g[i-1])(k-1)$， $g[i]=f[i-1]$。

我们定义 $f[i]$ 表示表示 $[0..i]$ 的栅栏柱且最后两个栅栏柱颜色不同的涂色方法数，定义 $g[i]$ 表示表示 $[0..i]$ 的栅栏柱且最后两个栅栏柱颜色相同的涂色方法数。初始时 $f[0]=k$，而 $g[0]=0$。

当 $i>0$ 时，有如下状态转移方程：

$$\begin{array}{rl}f[i]& =(f[i-1]+g[i-1])\times (k-1)\\ g[i]& =f[i-1]\end{array}$$

最终的答案即为 $f[n-1]+g[n-1]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是栅栏的数量。

func numWays(n int, k int) int {
	f := make([]int, n)
	g := make([]int, n)
	f[0] = k
	for i := 1; i < n; i++ {
		f[i] = (f[i-1] + g[i-1]) * (k - 1)
		g[i] = f[i-1]
	}
	return f[n-1] + g[n-1]
}

方法二：动态规划（空间优化） · Go 实现

思考

$f[i],g[i]$ 只依赖前一项，滚动两个变量即可把空间降为常数。

我们发现 $f[i]$ 和 $g[i]$ 只与 $f[i-1]$ 和 $g[i-1]$ 有关，因此我们可以使用两个变量 $f$ 和 $g$ 分别记录 $f[i-1]$ 和 $g[i-1]$ 的值，从而将空间复杂度优化到 $O(1)$。

func numWays(n int, k int) int {
	f, g := k, 0
	for i := 1; i < n; i++ {
		f, g = (f+g)*(k-1), f
	}
	return f + g
}

力扣原题 · Doocs 题解来源

279. 完全平方数

中等2 种解法

标签：广度优先搜索、数学、动态规划、背包问题、完全背包

题目、示例与约束

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

 

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

 

提示：

• 1 <= n <= 104

方法一：动态规划(完全背包) · Go 实现

思考

完全平方数可重复使用，求组成 $n$ 的最少个数，即完全背包。物品为 $1^2,\dots ,m^2$（ $m=\lfloor \sqrt{n}\rfloor$）。

$f[i][j]$ 表示用前 $i$ 种平方数凑 $j$ 的最少个数，转移为不选或再加一个 $i^2$。

我们定义 $f[i][j]$ 表示使用数字 $1,2,\cdots ,i$ 的完全平方数组成和为 $j$ 的最少数量。初始时 $f[0][0]=0$，其余位置的值均为正无穷。

我们可以枚举使用的最后一个数字的数量 $k$，那么：

$$f[i][j]=min(f[i-1][j],f[i-1][j-i^2]+1,\cdots ,f[i-1][j-k\times i^2]+k)$$

其中 $i^2$ 表示最后一个数字 $i$ 的完全平方数。

不妨令 $j=j-i^2$，那么有：

$$f[i][j-i^2]=min(f[i-1][j-i^2],f[i-1][j-2\times i^2]+1,\cdots ,f[i-1][j-k\times i^2]+k-1)$$

将二式代入一式，我们可以得到以下状态转移方程：

$$f[i][j]=min(f[i-1][j],f[i][j-i^2]+1)$$

最后答案即为 $f[m][n]$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 为 $sqrt(n)$ 的整数部分。

相似题目：

• 322. 零钱兑换

func numSquares(n int) int {
	m := int(math.Sqrt(float64(n)))
	f := make([][]int, m+1)
	const inf = 1 << 30
	for i := range f {
		f[i] = make([]int, n+1)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			f[i][j] = f[i-1][j]
			if j >= i*i {
				f[i][j] = min(f[i][j], f[i][j-i*i]+1)
			}
		}
	}
	return f[m][n]
}

方法二：动态规划优化 · Go 实现

思考

二维表中 $f[i][j]$ 只依赖 $f[i-1][j]$ 与 $f[i][j-i^2]$，可压成一维，按 $j$ 从小到大更新。

$f[i][j]$ 只与 $f[i-1][j]$ 和 $f[i][j-i^2]$ 有关，因此可以将二维数组优化为一维数组，空间复杂度降为 $O(n)$。时间复杂度仍为 $O(m\times n)$。

func numSquares(n int) int {
	m := int(math.Sqrt(float64(n)))
	f := make([]int, n+1)
	for i := range f {
		f[i] = 1 << 30
	}
	f[0] = 0
	for i := 1; i <= m; i++ {
		for j := i * i; j <= n; j++ {
			f[j] = min(f[j], f[j-i*i]+1)
		}
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

294. 翻转游戏 II 🔒

中等2 种解法

标签：记忆化、极小化极大、数学、动态规划、回溯、博弈、无偏博弈

题目、示例与约束

你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：

给你一个字符串 currentState ，其中只含 '+' 和 '-' 。你和朋友轮流将 连续 的两个 "++" 反转成 "--" 。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。默认每个人都会采取最优策略。

请你写出一个函数来判定起始玩家 是否存在必胜的方案 ：如果存在，返回 true ；否则，返回 false 。

 

示例 1：

输入：currentState = "++++"
输出：true
解释：起始玩家可将中间的 "++" 翻转变为 "+--+" 从而得胜。

示例 2：

输入：currentState = "+"
输出：false

 

提示：

• 1 <= currentState.length <= 60
• currentState[i] 不是 '+' 就是 '-'
• 不能有超过 20 个连续的 '+'。

 

进阶：请推导你算法的时间复杂度。

方法一：状态压缩 + 记忆化搜索 · Go 实现

思考

双方轮流翻 $++$，无法行动者负。状态可用长度为 $n$ 的位掩码表示 $+$ 的位置，枚举合法翻转后看对手是否必败。

同一掩码会反复出现，记忆化 $dfs(\mathit{\text{mask}})$：存在一步使对手返回假则先手胜。

func canWin(currentState string) bool {
	n := len(currentState)
	memo := map[int]bool{}
	mask := 0
	for i, c := range currentState {
		if c == '+' {
			mask |= 1 << i
		}
	}
	var dfs func(int) bool
	dfs = func(mask int) bool {
		if v, ok := memo[mask]; ok {
			return v
		}
		for i := 0; i < n-1; i++ {
			if (mask&(1<<i)) == 0 || (mask&(1<<(i+1))) == 0 {
				continue
			}
			if dfs(mask ^ (1 << i) ^ (1 << (i + 1))) {
				continue
			}
			memo[mask] = true
			return true
		}
		memo[mask] = false
		return false
	}
	return dfs(mask)
}

方法二：Sprague-Grundy 定理 · Go 实现

思考

记忆化搜索状态数为 $2^n$。连续的 $+$ 段彼此独立，可用 SG 函数：整局 SG 为各段异或，非零则先手胜。

Sprague-Grundy 定理为游戏的每一个状态定义了一个 Sprague-Grundy 数（简称 SG 数），游戏状态的组合相当于 SG 数的异或运算。

Sprague-Grundy 定理的完整表述如下：

若一个游戏满足以下条件：

1. 双人、回合制
2. 信息完全公开
3. 无随机因素
4. 必然在有限步内结束，且每步的走法数有限
5. 没有平局
6. 双方可采取的行动及胜利目标都相同
7. 这个胜利目标是自己亲手达成终局状态，或者说走最后一步者为胜（normal play）

则游戏中的每个状态可以按如下规则赋予一个非负整数，称为 Sprague-Grundy 数，即 $SG(A)=mex\{SG(B)|A->B\}$。（式中 $A$, $B$ 代表状态，代表 $A$ 状态经一步行动可以到达 $B$ 状态，而 $mex$ 表示一个集合所不包含的最小非负整数）

SG 数有如下性质：

1. SG 数为 0 的状态，后手必胜；SG 数为正的状态，先手必胜；
2. 若一个母状态可以拆分成多个相互独立的子状态，则母状态的 SG 数等于各个子状态的 SG 数的异或。

参考资料：Sprague-Grundy 定理是怎么想出来的

时间复杂度 $O(n^2)$。

func canWin(currentState string) bool {
	n := len(currentState)
	sg := make([]int, n+1)
	for i := range sg {
		sg[i] = -1
	}
	var win func(i int) int
	win = func(i int) int {
		if sg[i] != -1 {
			return sg[i]
		}
		vis := make([]bool, n)
		for j := 0; j < i-1; j++ {
			vis[win(j)^win(i-j-2)] = true
		}
		for j := 0; j < n; j++ {
			if !vis[j] {
				sg[i] = j
				return j
			}
		}
		return 0
	}
	ans, i := 0, 0
	for i < n {
		j := i
		for j < n && currentState[j] == '+' {
			j++
		}
		ans ^= win(j - i)
		i = j + 1
	}
	return ans > 0
}

力扣原题 · Doocs 题解来源

300. 最长递增子序列

中等2 种解法

标签：数组、二分查找、动态规划、最长上升子序列

题目、示例与约束

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

 

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

方法一：动态规划 · Go 实现

思考

子序列须保持相对顺序且严格递增。若枚举全部子序列，长度为 $n$ 时状态过多； $n\le 2500$，故可接受按结尾位置转移。

以 $nums[i]$ 结尾的最长递增子序列，只依赖于左侧更小的元素。为此定义 $f[i]$ 为该长度，枚举 $j<i$ 且 $nums[j]<nums[i]$，取 $f[j]+1$ 的最大值。每个位置独立成段时长度为 $1$，最终答案为 $maxf$。

我们定义 $f[i]$ 表示以 $nums[i]$ 结尾的最长递增子序列的长度，初始时 $f[i]=1$，答案为 $f[i]$ 的最大值。

对于 $f[i]$，我们需要枚举 $0\le j<i$，如果 $nums[j]<nums[i]$，则 $f[i]=max(f[i],f[j]+1)$。

最后的答案即为 $f[i]$ 的最大值。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

func lengthOfLIS(nums []int) int {
	n := len(nums)
	f := make([]int, n)
	for i := range f {
		f[i] = 1
	}
	ans := 1
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				f[i] = max(f[i], f[j]+1)
				ans = max(ans, f[i])
			}
		}
	}
	return ans
}

方法二：离散化 + 树状数组 · Go 实现

思考

方法一查询「左侧小于 $x$ 的最大 $f[j]$」需线性扫描，整体为 $O(n^2)$。将数值离散化后，该查询变为秩上的前缀最大值，树状数组可在 $O(\log n)$ 内维护。

按原序遍历每个 $x$：先查询小于 $x$ 的前缀最大长度再写回 $x$ 处，保证只用到左侧信息。因此时间降至 $O(n\log n)$，转移语义与方法一相同。

我们将数组中的元素离散化，然后使用树状数组维护不大于某个元素的最长递增子序列的长度。

遍历数组中的每个元素 $x$，将其离散化，然后在树状数组中查找不大于 $x-1$ 的最长递增子序列的长度 $t$，则 $x$ 的最长递增子序列的长度为 $t+1$，更新答案，并且更新树状数组中 $x$ 的最长递增子序列的长度。

遍历完数组中的所有元素，即可得到答案。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	return &BinaryIndexedTree{n, make([]int, n+1)}
}

func (bit *BinaryIndexedTree) update(x, v int) {
	for x <= bit.n {
		bit.c[x] = max(bit.c[x], v)
		x += x & -x
	}
}

func (bit *BinaryIndexedTree) query(x int) int {
	mx := 0
	for x > 0 {
		mx = max(mx, bit.c[x])
		x -= x & -x
	}
	return mx
}

func lengthOfLIS(nums []int) int {
	n := len(nums)
	s := make([]int, n)
	copy(s, nums)
	sort.Ints(s)
	m := 0
	for i, x := range s {
		if i == 0 || x != s[i-1] {
			s[m] = x
			m++
		}
	}
	tree := newBinaryIndexedTree(m)
	for _, x := range nums {
		x = sort.SearchInts(s[:m], x) + 1
		t := tree.query(x-1) + 1
		tree.update(x, t)
	}
	return tree.query(m)
}

力扣原题 · Doocs 题解来源

309. 买卖股票的最佳时机含冷冻期

中等4 种解法

标签：数组、动态规划

题目、示例与约束

给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

 

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

方法一：记忆化搜索 · Go 实现

思考

买卖可进行多次，卖出后须冷却一天。若按「第几天、是否持有、是否处于冷却」穷举决策树，同一状态会被反复展开。

状态可压成 $(i,j)$：从第 $i$ 天起、是否持有股票。每天可跳过；持有则可卖出并跳到 $i+2$，空仓则可买入并进入持有。记忆化后每个状态只算一次，卖出多走一天即表达冷却。

我们设计一个函数 $dfs(i,j)$，表示从第 $i$ 天开始，状态为 $j$ 时，能够获得的最大利润。其中 $j$ 的取值为 $0,1$，分别表示当前不持有股票和持有股票。答案即为 $dfs(0,0)$。

函数 $dfs(i,j)$ 的执行逻辑如下：

如果 $i\ge n$，表示已经没有股票可以交易了，此时返回 $0$；

否则，我们可以选择不交易，此时 $dfs(i,j)=dfs(i+1,j)$。我们也可以进行股票交易，如果此时 $j>0$，说明当前持有股票，可以卖出，此时 $dfs(i,j)=prices[i]+dfs(i+2,0)$；如果此时 $j=0$，说明当前不持有股票，可以买入，此时 $dfs(i,j)=-prices[i]+dfs(i+1,1)$。取最大值作为函数 $dfs(i,j)$ 的返回值。

答案为 $dfs(0,0)$。

为了避免重复计算，我们使用记忆化搜索的方法，用一个数组 $f$ 记录 $dfs(i,j)$ 的返回值，如果 $f[i][j]$ 不为 $-1$，说明已经计算过，直接返回 $f[i][j]$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $prices$ 的长度。

func maxProfit(prices []int) int {
	n := len(prices)
	f := make([][2]int, n)
	for i := range f {
		f[i] = [2]int{-1, -1}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= n {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans := dfs(i+1, j)
		if j > 0 {
			ans = max(ans, prices[i]+dfs(i+2, 0))
		} else {
			ans = max(ans, -prices[i]+dfs(i+1, 1))
		}
		f[i][j] = ans
		return ans
	}
	return dfs(0, 0)
}

方法二：动态规划 · Go 实现

思考

方法一从末尾填了一张后缀表。同样的选择也可以从左往右写： $f[i][0/1]$ 为前 $i$ 天结束时不持有/持有的最大利润。不持有由「继续空仓」或「今日卖出」转移；持有由「继续持有」或「冷却结束后买入」转移，买入只能接 $f[i-2][0]$。

自左向右填表，答案为最后一天空仓。时间仍为 $O(n)$。

我们也可以用动态规划的方法求解。

我们定义 $f[i][j]$ 表示到第 $i$ 天，且状态为 $j$ 时，能够获得的最大利润。其中 $j$ 的取值为 $0,1$，分别表示当前不持有股票和持有股票。初始时 $f[0][0]=0$, $f[0][1]=-prices[0]$。

当 $i\ge 1$ 时，如果当前不持有股票，那么 $f[i][0]$ 可以由 $f[i-1][0]$ 和 $f[i-1][1]+prices[i]$ 转移得到，即 $f[i][0]=max(f[i-1][0],f[i-1][1]+prices[i])$；如果当前持有股票，那么 $f[i][1]$ 可以由 $f[i-1][1]$ 和 $f[i-2][0]-prices[i]$ 转移得到，即 $f[i][1]=max(f[i-1][1],f[i-2][0]-prices[i])$。最终答案为 $f[n-1][0]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $prices$ 的长度。

func maxProfit(prices []int) int {
	n := len(prices)
	f := make([][2]int, n)
	f[0][1] = -prices[0]
	for i := 1; i < n; i++ {
		f[i][0] = max(f[i-1][0], f[i-1][1]+prices[i])
		if i > 1 {
			f[i][1] = max(f[i-1][1], f[i-2][0]-prices[i])
		} else {
			f[i][1] = max(f[i-1][1], -prices[i])
		}
	}
	return f[n-1][0]
}

方法三：动态规划（空间优化） · Go 实现

思考

方法二中 $f[i]$ 只依赖 $i-1$ 与 $i-2$，无需整张表。用三个变量滚动「前日空仓、昨日空仓、昨日持有」，按原转移更新即可把空间降到 $O(1)$。

$f[i]$ 只与前两天有关，用三个变量滚动即可，空间复杂度 $O(1)$。

func maxProfit(prices []int) int {
	f, f0, f1 := 0, 0, -prices[0]
	for _, x := range prices[1:] {
		f, f0, f1 = f0, max(f0, f1+x), max(f1, f-x)
	}
	return f0
}

方法四：动态规划 · Go 实现

思考

买卖可进行多次，卖出后须冷却一天。 $n\le 5000$，按决策树展开不可行。

状态是天数和是否持有。跳过当天总会先调用下一天再返回，调用链长度为 $n$，栈会溢出。

更靠后的天数在从末尾往前走时已经就绪。令 $f[i][j]$ 为从第 $i$ 天起、持有标记为 $j$ 的最大利润，从 $i=n-1$ 填到 $0$。卖出落到 $i+2$，多出的一天就是冷却。

令 $f[i][j]$ 表示从第 $i$ 天开始、状态为 $j$ 时能够获得的最大利润。 $j$ 取 $0$ 或 $1$，分别表示当前不持有股票和持有股票。答案为 $f[0][0]$。越过最后一天的利润为 $0$，因此 $f[n][j]=f[n+1][j]=0$。

我们从 $i=n-1$ 填到 $0$。不交易则保留 $f[i+1][j]$。若 $j>0$，当前持有股票，可以卖出，利润为 $prices[i]+f[i+2][0]$，多出的一天即冷却。若 $j=0$，当前不持有股票，可以买入，利润为 $-prices[i]+f[i+1][1]$。取较大值：

当 $j>0$ 时，

$$f[i][j]=max(f[i+1][j],prices[i]+f[i+2][0])$$

当 $j=0$ 时，

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

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $prices$ 的长度。

func maxProfit(prices []int) int {
	n := len(prices)
	f := make([][2]int, n+2)
	for i := n - 1; i >= 0; i-- {
		for j := 0; j < 2; j++ {
			ans := f[i+1][j]
			if j > 0 {
				ans = max(ans, prices[i]+f[i+2][0])
			} else {
				ans = max(ans, -prices[i]+f[i+1][1])
			}
			f[i][j] = ans
		}
	}
	return f[0][0]
}

力扣原题 · Doocs 题解来源

312. 戳气球

困难1 种解法

标签：数组、动态规划

题目、示例与约束

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

 

示例 1：

输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：

输入：nums = [1,5]
输出：10

 

提示：

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

方法一：动态规划 · Go 实现

思考

戳气球的顺序会改变两侧相邻关系，直接按戳破次序搜索会重复子区间。两端各补 $1$ 后，区间边界成为固定乘数。

若 $k$ 是开区间 $(i,j)$ 中最后戳破的气球，则左右子区间互不干扰，得分多出 $arr[i]\cdot arr[k]\cdot arr[j]$。为此定义 $f[i][j]$ 为戳完 $(i,j)$ 内全部气球的最大得分，按区间长度递增（代码中 $i$ 降序、 $j$ 升序）填表，答案为 $f[0][n+1]$。

我们记数组 $nums$ 的长度为 $n$。根据题目描述，我们可以在数组 $nums$ 的左右两端各添加一个 $1$，记为 $arr$。

然后，我们定义 $f[i][j]$ 表示戳破区间 $[i,j]$ 内的所有气球能得到的最多硬币数，那么答案即为 $f[0][n+1]$。

对于 $f[i][j]$，我们枚举区间 $[i,j]$ 内的所有位置 $k$，假设 $k$ 是最后一个戳破的气球，那么我们可以得到如下状态转移方程：

$$f[i][j]=max(f[i][j],f[i][k]+f[k][j]+arr[i]\times arr[k]\times arr[j])$$

在实现上，由于 $f[i][j]$ 的状态转移方程中涉及到 $f[i][k]$ 和 $f[k][j]$，其中 $i<k<j$，因此我们需要从大到小地遍历 $i$，从小到大地遍历 $j$，这样才能保证当计算 $f[i][j]$ 时 $f[i][k]$ 和 $f[k][j]$ 已经被计算出来。

最后，我们返回 $f[0][n+1]$ 即可。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为数组 $nums$ 的长度。

func maxCoins(nums []int) int {
    n := len(nums)
    arr := make([]int, n+2)
    arr[0] = 1
    arr[n+1] = 1
    copy(arr[1:], nums)

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

    for i := n - 1; i >= 0; i-- {
        for j := i + 2; j <= n+1; j++ {
            for k := i + 1; k < j; k++ {
                f[i][j] = max(f[i][j], f[i][k] + f[k][j] + arr[i]*arr[k]*arr[j])
            }
        }
    }

    return f[0][n+1]
}

力扣原题 · Doocs 题解来源

313. 超级丑数

中等2 种解法

标签：数组、数学、动态规划

题目、示例与约束

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

 

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32 
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

 

提示：

• 1 <= n <= 105
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• 题目数据 保证 primes[i] 是一个质数
• primes 中的所有值都 互不相同 ，且按 递增顺序 排列

方法一：优先队列（小根堆） · Go 实现

思考

超级丑数只含给定质因子。若从小到大枚举正整数并试除，当 $n$ 很大时线性扫描过慢。

从 $1$ 出发，每次弹出堆顶 $x$，再把 $x\times p$ 压回（防止溢出）。遇 $x$ 能被当前 $p$ 整除则停止后续质数，相当于欧拉筛去重。弹出 $n$ 次即为第 $n$ 个。

我们用一个优先队列（小根堆）维护所有可能的超级丑数，初始时将 $1$ 放入队列中。

每次从队列中取出最小的超级丑数 $x$，将 $x$ 乘以数组 primes 中的每个数，将乘积放入队列中，然后重复上述操作 $n$ 次即可得到第 $n$ 个超级丑数。

由于题目保证第 $n$ 个超级丑数在 $32$ 位带符号整数范围内，因此，我们将乘积放入队列之前，可以先判断乘积是否超过 $2^{31}-1$，如果超过，则不需要将乘积放入队列中。另外，可以使用欧拉筛优化。

时间复杂度 $O(n\times m\times \log (n\times m))$，空间复杂度 $O(n\times m)$。其中 $m$ 和 $n$ 分别为数组 primes 的长度和给定的整数 $n$。

func nthSuperUglyNumber(n int, primes []int) (x int) {
	q := hp{[]int{1}}
	for n > 0 {
		n--
		x = heap.Pop(&q).(int)
		for _, k := range primes {
			if x <= math.MaxInt32/k {
				heap.Push(&q, k*x)
			}
			if x%k == 0 {
				break
			}
		}
	}
	return
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

方法二：动态规划 + 多指针堆 · Go 实现

思考

方法一对每个已生成丑数向所有质数扩展，堆中候选过多。改为每个质数只保留一条指针：堆顶给出当前最小候选，写入后再把该质数的下一倍数压回。候选规模降为 $O(m)$，时间 $O(n\log m)$。

用数组 $ugly[1..n]$ 存放前 $n$ 个超级丑数，并维护一个小根堆。堆中每个元素对应一个质数 $p$，记录当前应由 $p$ 乘以第 $\mathit{\text{index}}$ 个超级丑数得到的候选值。

初始时 $ugly[1]=1$，把每个质数 $p$ 以 $(p,p,2)$ 入堆。每次取出堆顶最小值写入 $ugly$，再把该质数的指针后移并压回堆中。这样每个质数只维护一条指针，避免方法一中对已生成丑数的全局扩展。

时间复杂度 $O(n\times \log m)$，空间复杂度 $O(n+m)$。其中 $m$ 为数组 $\mathit{\text{primes}}$ 的长度。

type Ugly struct{ value, prime, index int }
type Queue []Ugly

func (u Queue) Len() int           { return len(u) }
func (u Queue) Swap(i, j int)      { u[i], u[j] = u[j], u[i] }
func (u Queue) Less(i, j int) bool { return u[i].value < u[j].value }
func (u *Queue) Push(v any)        { *u = append(*u, v.(Ugly)) }
func (u *Queue) Pop() any {
	old, x := *u, (*u)[len(*u)-1]
	*u = old[:len(old)-1]
	return x
}

func nthSuperUglyNumber(n int, primes []int) int {
	ugly, pq, p := make([]int, n+1), &Queue{}, 2
	ugly[1] = 1
	heap.Init(pq)
	for _, v := range primes {
		heap.Push(pq, Ugly{value: v, prime: v, index: 2})
	}
	for p <= n {
		top := heap.Pop(pq).(Ugly)
		if ugly[p-1] != top.value {
			ugly[p], p = top.value, p+1
		}
		top.value, top.index = ugly[top.index]*top.prime, top.index+1
		heap.Push(pq, top)
	}
	return ugly[n]
}

力扣原题 · Doocs 题解来源

322. 零钱兑换

中等2 种解法

标签：广度优先搜索、数组、动态规划、背包问题、完全背包

题目、示例与约束

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的 最少 的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

 

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

 

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

方法一：动态规划(完全背包) · Go 实现

思考

每种硬币可用任意多次，求凑出 $amount$ 的最少枚数。完全背包：物品为硬币、容量为金额。若 DFS 搜索组合，金额较大时重复子问题多。

定义 $f[i][j]$ 为用前 $i$ 种硬币凑 $j$ 的最少枚数。不选第 $i$ 种则继承 $f[i-1][j]$；若 $j\ge x$ 则可从 $f[i][j-x]$ 再加一枚。 $f[0][0]=0$，其余为无穷，无法凑出返回 $-1$。

我们定义 $f[i][j]$ 表示使用前 $i$ 种硬币，凑出金额 $j$ 的最少硬币数。初始时 $f[0][0]=0$，其余位置的值均为正无穷。

我们可以枚举使用的最后一枚硬币的数量 $k$，那么有：

$$f[i][j]=min(f[i-1][j],f[i-1][j-x]+1,\cdots ,f[i-1][j-k\times x]+k)$$

其中 $x$ 表示第 $i$ 种硬币的面值。

不妨令 $j=j-x$，那么有：

$$f[i][j-x]=min(f[i-1][j-x],f[i-1][j-2\times x]+1,\cdots ,f[i-1][j-k\times x]+k-1)$$

将二式代入一式，我们可以得到以下状态转移方程：

$$f[i][j]=min(f[i-1][j],f[i][j-x]+1)$$

最后答案即为 $f[m][n]$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为硬币的种类数和总金额。

func coinChange(coins []int, amount int) int {
	m, n := len(coins), amount
	f := make([][]int, m+1)
	const inf = 1 << 30
	for i := range f {
		f[i] = make([]int, n+1)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			f[i][j] = f[i-1][j]
			if j >= coins[i-1] {
				f[i][j] = min(f[i][j], f[i][j-coins[i-1]]+1)
			}
		}
	}
	if f[m][n] > n {
		return -1
	}
	return f[m][n]
}

方法二：动态规划优化 · Go 实现

思考

方法一中 $f[i][j]$ 只读 $f[i-1][j]$ 与 $f[i][j-x]$。压成一维后内层对金额递增，使 $f[j-x]$ 已含本枚硬币。空间降为 $O(amount)$，转移不变。

我们注意到 $f[i][j]$ 只与 $f[i-1][j]$ 和 $f[i][j-x]$ 有关，因此我们可以将二维数组优化为一维数组，空间复杂度降为 $O(n)$。时间复杂度仍为 $O(m\times n)$。

相似题目：

• 279. 完全平方数

func coinChange(coins []int, amount int) int {
	n := amount
	f := make([]int, n+1)
	for i := range f {
		f[i] = 1 << 30
	}
	f[0] = 0
	for _, x := range coins {
		for j := x; j <= n; j++ {
			f[j] = min(f[j], f[j-x]+1)
		}
	}
	if f[n] > n {
		return -1
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

338. 比特位计数

简单2 种解法

标签：位运算、动态规划

题目、示例与约束

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

不要使用内置函数来解决（例如，C++ 中的 __builtin_popcount）。

 

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

 

提示：

• 0 <= n <= 105

 

进阶：

• 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？

方法一：位运算 · Go 实现

思考

求 $0\dots n$ 每个数的二进制 $1$ 的个数。对每个 $i$ 单独数位需 $O(\log i)$。 $n$ 最大 ${10}^5$，线性带对数可过，但可再快。

直接对每个 $i$ 调用 bit_count（或反复 lowbit）即可得到答案数组。

我们直接枚举 $0\le i\le n$ 中的每个数，对于每个数 $i$，我们用库函数或者 $lowbit$ 运算得到 $i$ 中二进制位 $1$ 的个数。

时间复杂度 $O(n\times \log n)$，忽略答案的空间消耗，空间复杂度 $O(1)$。

func countBits(n int) []int {
	ans := make([]int, n+1)
	for i := 0; i <= n; i++ {
		ans[i] = bits.OnesCount(uint(i))
	}
	return ans
}

方法二：动态规划 · Go 实现

思考

方法一对每个数独立计数。 $i$ 去掉最低位 $1$ 后为 $i\mathrm{\&}(i-1)$，其答案已知，故 $ans[i]=ans[i\mathrm{\&}(i-1)]+1$。自小到大填表，总时间 $O(n)$。

我们定义一个长度为 $n+1$ 的答案数组 $ans$，初始时 $ans[0]=0$。

对于 $1\le i\le n$，我们有 $ans[i]=ans[i\mathit{\text{ and }}(i-1)]+1$。其中 $i\mathit{\text{ and }}(i-1)$ 表示将 $i$ 的二进制表示中的最低位 $1$ 变成 $0$ 之后的数，显然 $i\mathit{\text{ and }}(i-1)<i$，且 $ans[i\mathit{\text{ and }}(i-1)]$ 已经被计算出来了，我们就能以 $O(1)$ 的时间得到 $ans[i]$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func countBits(n int) []int {
	ans := make([]int, n+1)
	for i := 1; i <= n; i++ {
		ans[i] = ans[i&(i-1)] + 1
	}
	return ans
}

力扣原题 · Doocs 题解来源

343. 整数拆分

中等2 种解法

标签：数学、动态规划

题目、示例与约束

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

 

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

 

提示:

• 2 <= n <= 58

方法一：动态规划 · Go 实现

思考

把 $n$ 拆成至少两个正整数使乘积最大。枚举有序拆分过多。最后一段为 $j$ 时，其余部分可不再拆或取已算最优。

$f[i]=\underset{j}{max}max(f[i-j]\cdot j,(i-j)\cdot j)$。 $f[1]=1$，按 $i$ 递增填表，答案 $f[n]$。 $n\le 58$ 时 $O(n^2)$ 足够。

我们定义 $f[i]$ 表示正整数 $i$ 拆分后能获得的最大乘积，初始时 $f[1]=1$。答案即为 $f[n]$。

考虑 $i$ 最后拆分出的数字 $j$，其中 $j\in [1,i)$。对于 $i$ 拆分出的数字 $j$，有两种情况：

1. 将 $i$ 拆分成 $i-j$ 和 $j$ 的和，不继续拆分，此时乘积为 $(i-j)\times j$；
2. 将 $i$ 拆分成 $i-j$ 和 $j$ 的和，继续拆分，此时乘积为 $f[i-j]\times j$。

因此，我们可以得到状态转移方程：

$$f[i]=max(f[i],f[i-j]\times j,(i-j)\times j)(j\in [0,i))$$

最后返回 $f[n]$ 即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为给定的正整数。

func integerBreak(n int) int {
	f := make([]int, n+1)
	f[1] = 1
	for i := 2; i <= n; i++ {
		for j := 1; j < i; j++ {
			f[i] = max(max(f[i], f[i-j]*j), (i-j)*j)
		}
	}
	return f[n]
}

方法二：数学 · Go 实现

思考

方法一给出数值，未解释最优拆法。当 $n\ge 4$ 时应尽量拆出 $3$；余数为 $1$ 时改用 $2+2$（避免 $3+1$），余 $2$ 则多一个 $2$。 $n<4$ 只能拆成 $n-1$。闭式 $O(1)$。

当 $n<4$ 时，由于题目要求至少拆分成两个整数，因此 $n-1$ 是最大乘积。当 $n\ge 4$ 时，我们尽可能多地拆分 $3$，当剩下的最后一段为 $4$ 时，我们将其拆分为 $2+2$，这样乘积最大。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

func integerBreak(n int) int {
	if n < 4 {
		return n - 1
	}
	if n%3 == 0 {
		return int(math.Pow(3, float64(n/3)))
	}
	if n%3 == 1 {
		return int(math.Pow(3, float64(n/3-1))) * 4
	}
	return int(math.Pow(3, float64(n/3))) * 2
}

力扣原题 · Doocs 题解来源

351. 安卓系统手势解锁 🔒

中等1 种解法

标签：位运算、动态规划、回溯、位掩码

题目、示例与约束

我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。用户可以设置一个 “解锁模式” ，通过连接特定序列中的点，形成一系列彼此连接的线段，每个线段的端点都是序列中两个连续的点。如果满足以下两个条件，则 k 点序列是有效的解锁模式：

• 解锁模式中的所有点 互不相同 。
• 假如模式中两个连续点的线段需要经过其他点的 中心 ，那么要经过的点 必须提前出现 在序列中（已经经过），不能跨过任何还未被经过的点。
  • 例如，点 5 或 6 没有提前出现的情况下连接点 2 和 9 是有效的，因为从点 2 到点 9 的线没有穿过点 5 或 6 的中心。
  • 然而，点 2 没有提前出现的情况下连接点 1 和 3 是无效的，因为从圆点 1 到圆点 3 的直线穿过圆点 2 的中心。

以下是一些有效和无效解锁模式的示例：

• 无效手势：[4,1,3,6] ，连接点 1 和点 3 时经过了未被连接过的 2 号点。
• 无效手势：[4,1,9,2] ，连接点 1 和点 9 时经过了未被连接过的 5 号点。
• 有效手势：[2,4,1,3,6] ，连接点 1 和点 3 是有效的，因为虽然它经过了点 2 ，但是点 2 在该手势中之前已经被连过了。
• 有效手势：[6,5,4,1,9,2] ，连接点 1 和点 9 是有效的，因为虽然它经过了按键 5 ，但是点 5 在该手势中之前已经被连过了。

给你两个整数，分别为 ​​m 和 n ，那么请返回有多少种 不同且有效的解锁模式 ，是 至少 需要经过 m 个点，但是 不超过 n 个点的。

两个解锁模式 不同 需满足：经过的点不同或者经过点的顺序不同。

 

示例 1：

输入：m = 1, n = 1
输出：9

示例 2：

输入：m = 1, n = 2
输出：65

 

提示：

• 1 <= m, n <= 9

方法一：DFS · Go 实现

思考

安卓九键解锁，长度在 $[m,n]$ 且骑士跳过的中间键必须已用。 $9$ 个键，状态 $9\times 2^9$，可 DFS。

cross[i][j] 记下 $i$ 与 $j$ 之间必须经过的键。从当前键尝试未访问的 $j$，中间键为空或已用才合法。长度落入 $[m,n]$ 则计数。利用对称： $1$ 与 $2$ 各乘 $4$，再加中心 $5$。

我们定义一个二维数组 $cross$，其中 $cross[i][j]$ 表示数字 $i$ 和数字 $j$ 之间是否有中间数字，如果有则 $cross[i][j]$ 的值为中间数字，否则为 $0$。

我们还需要一个一维数组 $vis$，用来记录数字是否被使用过。

由于数字 $1$, $3$, $7$, $9$ 是对称的，因此我们只需要计算数字 $1$ 的情况，然后乘以 $4$ 即可。

由于数字 $2$, $4$, $6$, $8$ 也是对称的，因此我们只需要计算数字 $2$ 的情况，然后乘以 $4$ 即可。

最后我们再计算数字 $5$ 的情况。

我们设计一个函数 $dfs(i,cnt)$，表示当前位于数字 $i$，且已经选了 $cnt$ 个数字的情况下，有多少种解锁模式。

函数 $dfs(i,cnt)$ 的执行过程如下：

如果 $cnt>n$，说明当前选中的数字个数超过了 $n$，直接返回 $0$。

否则，我们将数字 $i$ 标记为已使用，然后初始化答案 $ans$ 为 $0$。如果 $cnt\ge m$，说明当前选中的数字个数不少于 $m$，那么答案 $ans$ 就需要加 $1$。

接下来，我们枚举下一个数字 $j$，如果数字 $j$ 没有被使用过，且数字 $i$ 和数字 $j$ 之间没有中间数字，或者数字 $i$ 和数字 $j$ 之间的中间数字已经被使用过，那么我们就可以从数字 $j$ 出发，继续搜索，此时答案 $ans$ 需要加上 $dfs(j,cnt+1)$ 的返回值。

最后，我们将数字 $i$ 标记为未使用，然后返回答案 $ans$。

最终的答案即为 $dfs(1,1)\times 4+dfs(2,1)\times 4+dfs(5,1)$。

时间复杂度 $O(n!)$，空间复杂度 $O(n)$。其中 $n$ 是手势的最大长度。

func numberOfPatterns(m int, n int) int {
	cross := [10][10]int{}
	vis := [10]bool{}
	cross[1][3] = 2
	cross[1][7] = 4
	cross[1][9] = 5
	cross[2][8] = 5
	cross[3][7] = 5
	cross[3][9] = 6
	cross[4][6] = 5
	cross[7][9] = 8
	cross[3][1] = 2
	cross[7][1] = 4
	cross[9][1] = 5
	cross[8][2] = 5
	cross[7][3] = 5
	cross[9][3] = 6
	cross[6][4] = 5
	cross[9][7] = 8
	var dfs func(int, int) int
	dfs = func(i, cnt int) int {
		if cnt > n {
			return 0
		}
		vis[i] = true
		ans := 0
		if cnt >= m {
			ans++
		}
		for j := 1; j < 10; j++ {
			x := cross[i][j]
			if !vis[j] && (x == 0 || vis[x]) {
				ans += dfs(j, cnt+1)
			}
		}
		vis[i] = false
		return ans
	}
	return dfs(1, 1)*4 + dfs(2, 1)*4 + dfs(5, 1)
}

力扣原题 · Doocs 题解来源

354. 俄罗斯套娃信封问题

困难1 种解法

标签：数组、二分查找、动态规划、排序、最长上升子序列

题目、示例与约束

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

 

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

 

提示：

• 1 <= envelopes.length <= 105
• envelopes[i].length == 2
• 1 <= wi, hi <= 105

方法一：贪心 + 二分查找 · Go 实现

思考

套娃信封须宽高都严格更大，求最多层数。二维 LIS 若 $O(n^2)$， $n$ 达 ${10}^5$ 不可行。宽递增后，高上的 LIS 即答案；同宽须避免套自己。

按宽升序、同宽按高降序排序，再对高做贪心 LIS：大于末尾则追加，否则二分替换。同宽的高降序保证至多选一个。

时间复杂度 O(nlogn)。

func maxEnvelopes(envelopes [][]int) int {
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] != envelopes[j][0] {
			return envelopes[i][0] < envelopes[j][0]
		}
		return envelopes[j][1] < envelopes[i][1]
	})
	n := len(envelopes)
	d := make([]int, n+1)
	d[1] = envelopes[0][1]
	size := 1
	for _, e := range envelopes[1:] {
		x := e[1]
		if x > d[size] {
			size++
			d[size] = x
		} else {
			left, right := 1, size
			for left < right {
				mid := (left + right) >> 1
				if d[mid] >= x {
					right = mid
				} else {
					left = mid + 1
				}
			}
			if d[left] < x {
				left = 1
			}
			d[left] = x
		}
	}
	return size
}

力扣原题 · Doocs 题解来源

357. 统计各位数字都不同的数字个数

中等1 种解法

标签：数学、动态规划、回溯

题目、示例与约束

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。

 

示例 1：

输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。 

示例 2：

输入：n = 0
输出：1

 

提示：

• 0 <= n <= 8

方法一：状态压缩 + 数位 DP · Go 实现

思考

统计 $x$ 位数以内各位数字均不同的个数，含 $0$。枚举再判重在 $n=8$ 时仍可，但数位 DP 统一处理前导零与已用数字。

$dfs(i,mask,lead)$ 表示还剩 $i+1$ 位、已用数字集合为 $mask$、是否仍前导零。前导零不占用数字；否则把 $j$ 记入 $mask$。 $n$ 位从 $i=n-1$ 开始，记忆化后状态很少。

这道题实际上是求在给定区间 $[l,..r]$ 中，满足条件的数的个数。条件与数的大小无关，而只与数的组成有关，因此可以使用数位 DP 的思想求解。数位 DP 中，数的大小对复杂度的影响很小。

对于区间 $[l,..r]$ 问题，我们一般会将其转化为 $[1,..r]$ 然后再减去 $[1,..l-1]$ 的问题，即：

$$ans=\sum _{i=1}^{r}an{s}_i-\sum _{i=1}^{l-1}an{s}_i$$

不过对于本题而言，我们只需要求出区间 $[1,.{.10}^n-1]$ 的值即可。

这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。

我们根据题目信息，设计一个函数 $\mathit{\text{dfs}}(i,\mathit{\text{mask}},\mathit{\text{lead}})$，其中：

• 数字 $i$ 表示当前搜索到的位置，我们从高位开始搜索，即 $i=0$ 表示最高位。
• 数字 $\mathit{\text{mask}}$ 表示当前数字的状态，即 $\mathit{\text{mask}}$ 的第 $j$ 位为 $1$ 表示数字 $j$ 已经被使用过。
• 布尔值 $\mathit{\text{lead}}$ 表示当前是否只包含前导 $0$。

函数的执行过程如下：

如果 $i$ 超过了数字 $n$ 的长度，即 $i<0$，说明搜索结束，直接返回 $1$。

否则，我们从 $0$ 到 $9$ 枚举位置 $i$ 的数字 $j$，对于每一个 $j$：

• 如果 $\mathit{\text{mask}}$ 的第 $j$ 位为 $1$，说明数字 $j$ 已经被使用过，直接跳过。
• 如果 $\mathit{\text{lead}}$ 为真且 $j=0$，说明当前数字只包含前导 $0$，递归到下一层时，此时 $\mathit{\text{lead}}$ 仍为真。
• 否则，我们递归到下一层，更新 $\mathit{\text{mask}}$ 的第 $j$ 位为 $1$，并将 $\mathit{\text{lead}}$ 更新为假。

最后，我们将所有递归到下一层的结果累加，即为答案。

答案为 $\mathit{\text{dfs}}(n-1,0,\mathit{\text{True}})$。

关于函数的实现细节，可以参考下面的代码。

时间复杂度 $O(n\times 2^D\times D)$，空间复杂度 $O(n\times 2^D)$。其中 $n$ 为数字 $n$ 的长度，而 $D=10$。

相似题目：

• 233. 数字 1 的个数
• 600. 不含连续 1 的非负整数
• 788. 旋转数字
• 902. 最大为 N 的数字组合
• 1012. 至少有 1 位重复的数字
• 2376. 统计特殊整数

func countNumbersWithUniqueDigits(n int) int {
	f := make([][1 << 10]int, n)
	for i := range f {
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, mask int, lead bool) int
	dfs = func(i, mask int, lead bool) int {
		if i < 0 {
			return 1
		}
		if !lead && f[i][mask] != -1 {
			return f[i][mask]
		}
		ans := 0
		for j := 0; j < 10; j++ {
			if mask>>j&1 == 1 {
				continue
			}
			if lead && j == 0 {
				ans += dfs(i-1, mask, true)
			} else {
				ans += dfs(i-1, mask|1<<j, false)
			}
		}
		if !lead {
			f[i][mask] = ans
		}
		return ans
	}
	return dfs(n-1, 0, true)
}

力扣原题 · Doocs 题解来源

361. 轰炸敌人 🔒

中等1 种解法

标签：数组、动态规划、矩阵

题目、示例与约束

给你一个大小为 m x n 的矩阵 grid ，其中每个单元格都放置有一个字符：

• 'W' 表示一堵墙
• 'E' 表示一个敌人
• '0'（数字 0）表示一个空位

返回你使用 一颗炸弹 可以击杀的最大敌人数目。你只能把炸弹放在一个空位里。

由于炸弹的威力不足以穿透墙体，炸弹只能击杀同一行和同一列没被墙体挡住的敌人。

 

示例 1：

输入：grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
输出：3

示例 2：

输入：grid = [["W","W","W"],["0","0","0"],["E","E","E"]]
输出：1

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] 可以是 'W'、'E' 或 '0'

方法一 · Go 实现

思考

空格放炸弹，沿四向直到墙，求能炸到的敌人最多。每个空格四向扫描为 $O(mn(m+n))$。同一行（列）相邻空格共享墙之间的敌人计数。

对每行左右各扫一遍、每列上下各扫一遍，把墙段内的敌人累加到格子上。空格上四向之和即炸杀数，取最大；无空格则为 $0$。

func maxKilledEnemies(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		t := 0
		for j := 0; j < n; j++ {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
		t = 0
		for j := n - 1; j >= 0; j-- {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
	}
	for j := 0; j < n; j++ {
		t := 0
		for i := 0; i < m; i++ {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
		t = 0
		for i := m - 1; i >= 0; i-- {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
	}
	ans := 0
	for i, row := range grid {
		for j, v := range row {
			if v == '0' && ans < g[i][j] {
				ans = g[i][j]
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

368. 最大整除子集

中等1 种解法

标签：数组、数学、动态规划、排序

题目、示例与约束

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

• answer[i] % answer[j] == 0 ，或
• answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

 

示例 1：

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 109
• nums 中的所有整数 互不相同

方法一：排序 + 动态规划 · Go 实现

思考

最大子集须任意两数互相整除。无序时整除关系不构成链。排序后只需看较大数是否整除较小数，转移与 LIS 相同。

$f[i]$ 为以 $nums[i]$ 为最大元的最长整除子集。 $nums[i]\mathrm{\%}nums[j]=0$ 则可接 $f[j]+1$。记下最大 $f$ 的下标，再倒序按长度递减还原元素。

我们先对数组进行排序，这样可以保证对于任意的 $i<j$，如果 $nums[i]$ 可以整除 $nums[j]$，那么 $nums[i]$ 一定在 $nums[j]$ 的左边。

接下来，我们定义 $f[i]$ 表示以 $nums[i]$ 为最大元素的最大整除子集的大小，初始时 $f[i]=1$。

对于每一个 $i$，我们从左往右枚举 $j$，如果 $nums[i]$ 可以被 $nums[j]$ 整除，那么 $f[i]$ 可以从 $f[j]$ 转移而来，我们更新 $f[i]=max(f[i],f[j]+1)$。过程中，我们记录 $f[i]$ 的最大值的下标 $k$ 以及对应的子集大小 $m$。

最后，我们从 $k$ 开始倒序遍历，如果 $nums[k]$ 可以被 $nums[i]$ 整除，且 $f[i]=m$，那么 $nums[i]$ 就是一个整除子集的元素，我们将 $nums[i]$ 加入答案，并将 $m$ 减 $1$，同时更新 $k=i$。继续倒序遍历，直到 $m=0$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。

func largestDivisibleSubset(nums []int) (ans []int) {
	sort.Ints(nums)
	n := len(nums)
	f := make([]int, n)
	k := 0
	for i := 0; i < n; i++ {
		f[i] = 1
		for j := 0; j < i; j++ {
			if nums[i]%nums[j] == 0 {
				f[i] = max(f[i], f[j]+1)
			}
		}
		if f[k] < f[i] {
			k = i
		}
	}
	m := f[k]
	for i := k; m > 0; i-- {
		if nums[k]%nums[i] == 0 && f[i] == m {
			ans = append(ans, nums[i])
			k = i
			m--
		}
	}
	return
}

力扣原题 · Doocs 题解来源

375. 猜数字大小 II

中等1 种解法

标签：极小化极大、数学、动态规划、博弈

题目、示例与约束

我们正在玩一个猜数游戏，游戏规则如下：

1. 我从 1 到 n 之间选择一个数字。
2. 你来猜我选了哪个数字。
3. 如果你猜到正确的数字，就会 赢得游戏 。
4. 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
5. 每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。

给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。

 

示例 1：

输入：n = 10
输出：16
解释：制胜策略如下：
- 数字范围是 [1,10] 。你先猜测数字为 7 。
    - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $7 。
    - 如果我的数字更大，则下一步需要猜测的数字范围是 [8,10] 。你可以猜测数字为 9 。
        - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $9 。
        - 如果我的数字更大，那么这个数字一定是 10 。你猜测数字为 10 并赢得游戏，总费用为 $7 + $9 = $16 。
        - 如果我的数字更小，那么这个数字一定是 8 。你猜测数字为 8 并赢得游戏，总费用为 $7 + $9 = $16 。
    - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,6] 。你可以猜测数字为 3 。
        - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $3 。
        - 如果我的数字更大，则下一步需要猜测的数字范围是 [4,6] 。你可以猜测数字为 5 。
            - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $5 。
            - 如果我的数字更大，那么这个数字一定是 6 。你猜测数字为 6 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。
            - 如果我的数字更小，那么这个数字一定是 4 。你猜测数字为 4 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。
        - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,2] 。你可以猜测数字为 1 。
            - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $1 。
            - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $7 + $3 + $1 = $11 。
在最糟糕的情况下，你需要支付 $16 。因此，你只需要 $16 就可以确保自己赢得游戏。

示例 2：

输入：n = 1
输出：0
解释：只有一个可能的数字，所以你可以直接猜 1 并赢得游戏，无需支付任何费用。

示例 3：

输入：n = 2
输出：1
解释：有两个可能的数字 1 和 2 。
- 你可以先猜 1 。
    - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $1 。
    - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $1 。
最糟糕的情况下，你需要支付 $1 。

 

提示：

• 1 <= n <= 200

方法一：动态规划 · Go 实现

思考

猜错要付所猜之数，求保证猜中的最少最坏花费。枚举猜测顺序是博弈树。区间 $[i,j]$ 的最优与更短区间独立。

$f[i][j]$ 为该区间的最少最坏花费。猜 $k$ 则花费 $k+max(\mathrm{左},\mathrm{右})$，对 $k$ 取最小。按区间长度填表，答案 $f[1][n]$。

我们定义 $f[i][j]$ 表示在区间 $[i,j]$ 中猜中任意一个数最少需要花费的钱数。初始时 $f[i][i]=0$，因为猜中了唯一的数不需要花费，对于 $i>j$ 的情况，也有 $f[i][j]=0$。答案即为 $f[1][n]$。

对于 $f[i][j]$，我们可以枚举 $[i,j]$ 中的任意一个数 $k$，将区间 $[i,j]$ 分为 $[i,k-1]$ 和 $[k+1,j]$ 两部分，选择其中的较大值加上 $k$ 的花费，即 $max(f[i][k-1],f[k+1][j])+k$ 的最小值。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为猜测的数字范围。

func getMoneyAmount(n int) int {
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := n - 1; i > 0; i-- {
		for j := i + 1; j <= n; j++ {
			f[i][j] = j + f[i][j-1]
			for k := i; k < j; k++ {
				f[i][j] = min(f[i][j], k+max(f[i][k-1], f[k+1][j]))
			}
		}
	}
	return f[1][n]
}

力扣原题 · Doocs 题解来源

376. 摆动序列

中等1 种解法

标签：贪心、数组、动态规划

题目、示例与约束

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

 

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

 

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

 

进阶：你能否用 O(n) 时间复杂度完成此题?

方法一：动态规划 · Go 实现

思考

摆动子序列要求相邻差正负交替。枚举子序列过多。以某位置结尾时只需区分最后一段升或降。

$f[i]$ 升结尾、 $g[i]$ 降结尾。 $nums[j]<nums[i]$ 则接在降段后更新 $f$；大于则接在升段后更新 $g$。答案为所有 $f,g$ 的最大。

我们定义 $f[i]$ 表示以第 $i$ 个元素结尾且最后是上升趋势的摆动序列的长度，定义 $g[i]$ 表示以第 $i$ 个元素结尾且最后是下降趋势的摆动序列的长度。初始时 $f[0]=g[0]=1$，因为只有一个元素时，摆动序列的长度为 $1$。初始化答案为 $1$。

对于 $f[i]$，其中 $i\ge 1$，我们在 $[0,i)$ 的范围内枚举 $j$，如果 $nums[j]<nums[i]$，则说明 $i$ 可以接在 $j$ 的后面形成一个上升的摆动序列，此时 $f[i]=max(f[i],g[j]+1)$；如果 $nums[j]>nums[i]$，则说明 $i$ 可以接在 $j$ 的后面形成一个下降的摆动序列，此时 $g[i]=max(g[i],f[j]+1)$。然后我们更新答案为 $max(f[i],g[i])$。

最后，我们返回答案。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

func wiggleMaxLength(nums []int) int {
	n := len(nums)
	f := make([]int, n)
	g := make([]int, n)
	f[0], g[0] = 1, 1
	ans := 1
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				f[i] = max(f[i], g[j]+1)
			} else if nums[j] > nums[i] {
				g[i] = max(g[i], f[j]+1)
			}
		}
		ans = max(ans, max(f[i], g[i]))
	}
	return ans
}

力扣原题 · Doocs 题解来源

377. 组合总和 Ⅳ

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

 

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

 

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

 

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

方法一：动态规划 · Go 实现

思考

排列（顺序不同算不同）凑出 $target$ 的方案数。若按组合背包外层物品，会漏掉不同顺序。须先枚举和、再枚举末项。

$f[i]$ 为和为 $i$ 的排列数， $f[0]=1$。对每个 $i$ 枚举 $x$，若 $i\ge x$ 则加上 $f[i-x]$。与 322 同形，目标从最少枚数改为计数。

我们定义 $f[i]$ 表示总和为 $i$ 的元素组合的个数，初始时 $f[0]=1$，其余 $f[i]=0$。最终答案即为 $f[target]$。

对于 $f[i]$，我们可以枚举数组中的每个元素 $x$，如果 $i\ge x$，则 $f[i]=f[i]+f[i-x]$。

最后返回 $f[target]$ 即可。

时间复杂度 $O(n\times target)$，空间复杂度 $O(target)$。其中 $n$ 为数组的长度。

func combinationSum4(nums []int, target int) int {
	f := make([]int, target+1)
	f[0] = 1
	for i := 1; i <= target; i++ {
		for _, x := range nums {
			if i >= x {
				f[i] += f[i-x]
			}
		}
	}
	return f[target]
}

力扣原题 · Doocs 题解来源

392. 判断子序列

简单1 种解法

标签：双指针、字符串、动态规划

题目、示例与约束

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

 

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

 

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

方法一：双指针 · Go 实现

思考

判断 $s$ 是否为 $t$ 的子序列。对 $s$ 每个字符在 $t$ 中找下一个出现即可。双指针一次扫描。

$i$ 指向 $s$， $j$ 扫 $t$：相等则 $i$ 前进。 $i$ 走到末尾则是子序列。

我们定义两个指针 $i$ 和 $j$，分别指向字符串 $s$ 和 $t$ 的初始位置。每次我们比较两个指针指向的字符，如果相同，则两个指针同时右移；如果不同，则只有 $j$ 右移。当指针 $i$ 移动到字符串 $s$ 的末尾时，说明 $s$ 是 $t$ 的子序列。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度。空间复杂度 $O(1)$。

func isSubsequence(s string, t string) bool {
	i, j, m, n := 0, 0, len(s), len(t)
	for i < m && j < n {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == m
}

力扣原题 · Doocs 题解来源

396. 旋转函数

中等1 种解法

标签：数组、数学、动态规划

题目、示例与约束

给定一个长度为 n 的整数数组 nums 。

假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数  F 为：

• F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]

返回 F(0), F(1), ..., F(n-1)中的最大值 。

生成的测试用例让答案符合 32 位 整数。

 

示例 1:

输入: nums = [4,3,2,6]
输出: 26
解释:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

示例 2:

输入: nums = [100]
输出: 0

 

提示:

• n == nums.length
• 1 <= n <= 105
• -100 <= nums[i] <= 100

方法一 · Go 实现

思考

$F(k)=\sum i\cdot \mathit{\text{nums}}[(i+k)modn]$，求最大 $F$。每次旋转后重算为 $O(n^2)$。相邻 $F$ 有线性关系。

$F(k+1)=F(k)+\sum nums-n\cdot nums[n-1-k]$。先算 $F(0)$，再滚 $n-1$ 次取最大。

func maxRotateFunction(nums []int) int {
	f, s, n := 0, 0, len(nums)
	for i, v := range nums {
		f += i * v
		s += v
	}
	ans := f
	for i := 1; i < n; i++ {
		f = f + s - n*nums[n-i]
		ans = max(ans, f)
	}
	return ans
}

力扣原题 · Doocs 题解来源

397. 整数替换

中等1 种解法

标签：贪心、位运算、记忆化、动态规划

题目、示例与约束

给定一个正整数 n ，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n 。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。

返回 n 变为 1 所需的 最小替换次数 。

 

示例 1：

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

示例 2：

输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

示例 3：

输入：n = 4
输出：2

 

提示：

• 1 <= n <= 231 - 1

方法一 · Go 实现

思考

偶则除 $2$，奇则加一或减一，求到 $1$ 的最少步。BFS 可行，但贪心按二进制更短。偶必右移；奇时若末两位为 $11$ 且不是 $3$，加一可消更多 $1$，否则减一。

$3$ 特判减一，避免加到 $4$ 再除两次多走。循环直到 $1$。

func integerReplacement(n int) int {
	ans := 0
	for n != 1 {
		if (n & 1) == 0 {
			n >>= 1
		} else if n != 3 && (n&3) == 3 {
			n++
		} else {
			n--
		}
		ans++
	}
	return ans
}

力扣原题 · Doocs 题解来源

403. 青蛙过河

困难2 种解法

标签：数组、动态规划

题目、示例与约束

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

 

示例 1：

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

示例 2：

输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

 

提示：

• 2 <= stones.length <= 2000
• 0 <= stones[i] <= 231 - 1
• stones[0] == 0
• stones 按严格升序排列

方法一：哈希表 + 记忆化搜索 · Go 实现

思考

从每个石子尝试步长 $k-1,k,k+1$，同一「石子 + 上一步距」会被反复走到。 $n\le 1100$，状态 $(i,k)$ 至多 $O(n^2)$ 个。

用哈希表把坐标映射到下标，记忆化 $dfs(i,k)$，只向确实存在的下一石子扩展。先建 $\mathit{\text{pos}}$，落点查询才是常数时间。

我们用哈希表 $pos$ 记录每个石子的下标，接下来设计一个函数 $dfs(i,k)$，表示青蛙从第 $i$ 个石子跳跃且上一次跳跃距离为 $k$，如果青蛙能够到达终点，那么函数返回 true，否则返回 false。

函数 $dfs(i,k)$ 的计算过程如下：

如果 $i$ 是最后一个石子的下标，那么青蛙已经到达终点，返回 true；

否则，我们需要枚举青蛙接下来的跳跃距离 $j$，其中 $j\in [k-1,k,k+1]$。如果 $j$ 是正数，并且哈希表 $pos$ 中存在位置 $stones[i]+j$，那么青蛙在第 $i$ 个石子上可以选择跳跃 $j$ 个单位，如果 $dfs(pos[stones[i]+j],j)$ 返回 true，那么青蛙可以从第 $i$ 个石子成功跳跃到终点，我们就可以返回 true。

枚举结束，说明青蛙在第 $i$ 个石子上无法选择合适的跳跃距离跳到终点，我们就返回 false。

为了防止函数 $dfs(i,k)$ 中出现重复计算，我们可以使用记忆化搜索，将 $dfs(i,k)$ 的结果记录在一个数组 $f$ 中，每当函数 $dfs(i,k)$ 返回结果，我们就将 $f[i][k]$ 进行赋值，并在下次遇到 $dfs(i,k)$ 时直接返回 $f[i][k]$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 是石子的数量。

func canCross(stones []int) bool {
	n := len(stones)
	f := make([][]int, n)
	pos := map[int]int{}
	for i := range f {
		pos[stones[i]] = i
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) bool
	dfs = func(i, k int) bool {
		if i == n-1 {
			return true
		}
		if f[i][k] != -1 {
			return f[i][k] == 1
		}
		for j := k - 1; j <= k+1; j++ {
			if j > 0 {
				if p, ok := pos[stones[i]+j]; ok {
					if dfs(p, j) {
						f[i][k] = 1
						return true
					}
				}
			}
		}
		f[i][k] = 0
		return false
	}
	return dfs(0, 0)
}

方法二：动态规划 · Go 实现

思考

方法一的递归深度随路径增长。改为 $f[i][k]$ 表示能否以步长 $k$ 落到第 $i$ 块石子，由更早的 $j$ 转移， $k=\mathit{\text{stones}}[i]-\mathit{\text{stones}}[j]$。

若 $k-1>j$，更远的 $j$ 步长更大而中间石子更少，可以提前结束内层循环。自底向上填表，避免递归栈。

我们定义 $f[i][k]$ 表示青蛙能否达到「现在所处的石子编号」为 $i$，「上一次跳跃距离」为 $k$ 的状态。初始时 $f[0][0]=true$，其余均为 false。

考虑 $f[i]$，我们可以枚举上一块石子的编号 $j$，那么上一次跳跃的距离 $k=stones[i]-stones[j]$。如果 $k-1>j$，那么青蛙无法从第 $j$ 块石子跳跃到第 $i$ 块石子，我们可以直接跳过这种情况。否则，青蛙可以从第 $j$ 块石子跳跃到第 $i$ 块石子，那么 $f[i][k]=f[j][k-1]\vee f[j][k]\vee f[j][k+1]$。如果 $i=n-1$，且 $f[i][k]=true$，那么青蛙可以成功过河，我们就可以返回 true。

否则，我们最后返回 false。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 是石子的数量。

func canCross(stones []int) bool {
	n := len(stones)
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, n)
	}
	f[0][0] = true
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0; j-- {
			k := stones[i] - stones[j]
			if k-1 > j {
				break
			}
			f[i][k] = f[j][k-1] || f[j][k] || f[j][k+1]
			if i == n-1 && f[i][k] {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源