LeetCode Go · 动态规划（3）

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

来源与许可

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

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

410. 分割数组的最大值

困难1 种解法

标签：贪心、数组、二分查找、动态规划、前缀和

题目、示例与约束

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组，使得这 k 个子数组各自和的最大值 最小。

返回分割后最小的和的最大值。

子数组 是数组中连续的部分。

 

示例 1：

输入：nums = [7,2,5,10,8], k = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：

输入：nums = [1,2,3,4,5], k = 2
输出：9

示例 3：

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

 

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= k <= min(50, nums.length)

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

思考

枚举全部分割点组合，段数与长度都会爆炸。观察到：子数组和的上限越大，所需段数越少，可行性关于上限单调。

对上限 $\mathit{\text{mid}}$ 二分，贪心从左累加，超过 $\mathit{\text{mid}}$ 就新开一段，判断段数是否不超过 $k$。左界为 $max(\mathit{\text{nums}})$，右界为总和。

二分找最小可行上限，把组合搜索换成线性校验。

我们注意到，当子数组的和的最大值越大，子数组的个数越少，当存在一个满足条件的子数组和的最大值时，那么比这个最大值更大的子数组和的最大值一定也满足条件。也就是说，我们可以对子数组和的最大值进行二分查找，找到满足条件的最小值。

我们定义二分查找的左边界 $left=max(nums)$，右边界 $right=sum(nums)$，然后对于二分查找的每一步，我们取中间值 $mid=\lfloor \frac{left+right}{2}\rfloor$，然后判断是否存在一个分割方式，使得子数组的和的最大值不超过 $mid$，如果存在，则说明 $mid$ 可能是满足条件的最小值，因此我们将右边界调整为 $mid$，否则我们将左边界调整为 $mid+1$。

我们如何判断是否存在一个分割方式，使得子数组的和的最大值不超过 $mid$ 呢？我们可以使用贪心的方法，从左到右遍历数组，将数组中的元素依次加入到子数组中，如果当前子数组的和大于 $mid$，则我们将当前元素加入到下一个子数组中。如果我们能够将数组分割成不超过 $k$ 个子数组，且每个子数组的和的最大值不超过 $mid$，则说明 $mid$ 是满足条件的最小值，否则 $mid$ 不是满足条件的最小值。

时间复杂度 $O(n\times \log m)$，空间复杂度 $O(1)$。其中 $n$ 和 $m$ 分别是数组的长度和数组所有元素的和。

func splitArray(nums []int, k int) int {
	left, right := 0, 0
	for _, x := range nums {
		left = max(left, x)
		right += x
	}
	return left + sort.Search(right-left, func(mx int) bool {
		mx += left
		s, cnt := 1<<30, 0
		for _, x := range nums {
			s += x
			if s > mx {
				s = x
				cnt++
			}
		}
		return cnt <= k
	})
}

力扣原题 · Doocs 题解来源

413. 等差数列划分

中等1 种解法

标签：数组、动态规划、滑动窗口

题目、示例与约束

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

• 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

 

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1]
输出：0

 

提示：

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000

方法一：遍历计数 · Go 实现

思考

枚举所有长度至少为 $3$ 的子数组再验公差，需要 $O(n^2)$。 $n\le 5000$ 勉强可行，但相邻公差一旦确定，整段贡献可以闭式累加。

一次扫描维护当前公差与连续段内新增切片数 $\mathit{\text{cnt}}$：公差不变则 $\mathit{\text{cnt}}$ 加一并计入答案，否则重置。

长度为 $L$ 的等差段恰好贡献 $1+2+\cdots +(L-2)$ 个切片，边走边加 $\mathit{\text{cnt}}$ 即完成求和。

我们用 $d$ 表示当前相邻两个元素的差值，用 $cnt$ 表示当前等差数列的长度，初始时 $d=3000$, $cnt=2$。

遍历数组 nums，对于相邻的两个元素 $a$ 和 $b$，如果 $b-a=d$，则说明当前元素 $b$ 也属于当前等差数列，此时 $cnt$ 自增 1；否则说明当前元素 $b$ 不属于当前等差数列，此时更新 $d=b-a$，且 $cnt=2$。如果 $cnt\ge 3$，则说明当前等差数列的长度至少为 3，此时等差数列的个数为 $cnt-2$，将其加到答案中。

遍历结束后，即可得到答案。

在代码实现上，我们也可以将 $cnt$ 初始化为 $0$，重置 $cnt$ 时，直接将 $cnt$ 置为 $0$；累加答案时，直接累加 $cnt$ 即可。

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

相似题目：

• 1513. 仅含 1 的子串数
• 2348. 全 0 子数组的数目

func numberOfArithmeticSlices(nums []int) (ans int) {
	cnt, d := 0, 3000
	for i, b := range nums[1:] {
		a := nums[i]
		if b-a == d {
			cnt++
		} else {
			d = b - a
			cnt = 0
		}
		ans += cnt
	}
	return
}

力扣原题 · Doocs 题解来源

416. 分割等和子集

中等2 种解法

标签：数组、动态规划、背包问题、0-1 背包

题目、示例与约束

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

 

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

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

思考

等和划分即能否选出一个子集，其和为总和的一半。总和为奇数则不可能。子集枚举在 $n\le 200$ 时不可行。

这是容量为 $m=s/2$ 的 $0$-$1$ 背包：令 $f[i][j]$ 表示前 $i$ 个数能否凑出 $j$，转移为选或不选 $x$。 $n$ 与 $m$ 的乘积可接受。

先判奇偶再填表，空集对应 $f[0][0]=\mathit{\text{true}}$，保证转移有起点。

我们先计算出数组的总和 $s$，如果总和是奇数，那么一定不能分割成两个和相等的子集，直接返回 $false$。如果总和是偶数，我们记目标子集的和为 $m=\frac{s}{2}$，那么问题就转化成了：是否存在一个子集，使得其元素的和为 $m$。

我们定义 $f[i][j]$ 表示前 $i$ 个数中选取若干个数，使得其元素的和恰好为 $j$。初始时 $f[0][0]=true$，其余 $f[i][j]=false$。答案为 $f[n][m]$。

考虑 $f[i][j]$，如果我们选取了第 $i$ 个数 $x$，那么 $f[i][j]=f[i-1][j-x]$；如果我们没有选取第 $i$ 个数 $x$，那么 $f[i][j]=f[i-1][j]$。因此状态转移方程为：

$$f[i][j]=f[i-1][j]\mathit{\text{ or }}f[i-1][j-x]\mathit{\text{ if }}j\ge x$$

最终答案为 $f[n][m]$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为数组的总和的一半和数组的长度。

func canPartition(nums []int) bool {
	s := 0
	for _, x := range nums {
		s += x
	}
	if s%2 == 1 {
		return false
	}
	n, m := len(nums), s>>1
	f := make([][]bool, n+1)
	for i := range f {
		f[i] = make([]bool, m+1)
	}
	f[0][0] = true
	for i := 1; i <= n; i++ {
		x := nums[i-1]
		for j := 0; j <= m; j++ {
			f[i][j] = f[i-1][j] || (j >= x && f[i-1][j-x])
		}
	}
	return f[n][m]
}

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

思考

$f[i][j]$ 只依赖上一行，且同一物品不能用两次，因此将 $j$ 倒序更新并压成一维数组，空间从 $O(nm)$ 降到 $O(m)$。

我们注意到，方法一中 $f[i][j]$ 只与 $f[i-1][\cdot ]$ 有关，因此我们可以将二维数组压缩成一维数组。

时间复杂度 $O(n\times m)$，空间复杂度 $O(m)$。其中 $n$ 是数组的长度，而 $m$ 是数组的总和的一半。

func canPartition(nums []int) bool {
	s := 0
	for _, x := range nums {
		s += x
	}
	if s%2 == 1 {
		return false
	}
	m := s >> 1
	f := make([]bool, m+1)
	f[0] = true
	for _, x := range nums {
		for j := m; j >= x; j-- {
			f[j] = f[j] || f[j-x]
		}
	}
	return f[m]
}

力扣原题 · Doocs 题解来源

418. 屏幕可显示句子的数量 🔒

中等1 种解法

标签：数组、字符串、动态规划

题目、示例与约束

给你一个 rows x cols 的屏幕和一个用 非空 的单词列表组成的句子，请你计算出给定句子可以在屏幕上完整显示的次数。

句子中的单词顺序必须保持不变，并且不能将一个单词分成两行。一行中的两个连续单词必须用空白分开。

 

示例 1：

输入：sentence = ["hello", "world"], rows = 2, cols = 8
输出：1
解释：
hello---
world---
字符 '-' 表示屏幕上的一个空白位置。

 

示例 2：

输入：sentence = ["a", "bcd", "e"], rows = 3, cols = 6
输出：2
解释：
a-bcd- 
e-a---
bcd-e-
字符 '-' 表示屏幕上的一个空白位置。

 

示例 3：

输入：sentence = ["i", "had", "apple", "pie"], rows = 4, cols = 5
输出：1
解释：
i-had
apple
pie-i
had--
字符 '-' 表示屏幕上的一个空白位置。

 

提示：

• 1 <= sentence.length <= 100
• 1 <= sentence[i].length <= 10
• sentence[i] 由小写英文字母组成。
• 1 <= rows, cols <= 2 * 104

方法一：贪心 · Go 实现

思考

逐词判断当前行能否放下，行数可达 ${10}^4$，句子会循环多次，指针在单词间来回移动较繁琐。

把句子连成带尾空格的环 $s$，用 $\mathit{\text{cur}}$ 表示已经覆盖的字符数。每一行先加上 $\mathit{\text{cols}}$：若落点是空格，说明刚好结束一个单词，再前进一格；否则回退到上一个空格，相当于把未写完的单词放到下一行。

整句出现次数即 $\lfloor \mathit{\text{cur}}/|s|\rfloor$。尾空格把「单词之间必须有空格」编码进环上，回退保证不会把单词拆开。

我们将句子的每个单词拼接上一个空格，然后把句子拼接起来，得到字符串 $s$。例如，对于句子 ["hello", "world"]，得到的字符串为 "hello world "。记 $s$ 的长度为 $m$。

接下来，我们使用贪心的方法，找到最大的可显示句子数。定义一个变量 $cur$，表示当前已经在屏幕上显示的字符串的长度，初始时 $cur=0$。

我们循环 $rows$ 次，每次循环中，我们首先将 $cur$ 增加 $cols$，如果 $s[curmodm]$ 是一个空格，说明我们可以将完整的若干个单词放置到当前行，因此我们将 $cur$ 增加一个额外的 $1$；否则，说明我们需要回退 $cur$，直到 $cur$ 指向的字符是一个空格为止。然后继续下一次循环。

循环结束，返回 $\lfloor \frac{cur}{m}\rfloor$ 即可。

时间复杂度 $O(rows\times M)$，空间复杂度 $O(L)$。其中 $M$ 是单词的最大长度，而 $L$ 是单词的总长度。

func wordsTyping(sentence []string, rows int, cols int) int {
	s := strings.Join(sentence, " ") + " "
	m := len(s)
	cur := 0
	for i := 0; i < rows; i++ {
		cur += cols
		if s[cur%m] == ' ' {
			cur++
		} else {
			for cur > 0 && s[(cur-1)%m] != ' ' {
				cur--
			}
		}
	}
	return cur / m
}

力扣原题 · Doocs 题解来源

435. 无重叠区间

中等1 种解法

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

题目、示例与约束

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

 

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

 

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

方法一：排序 + 贪心 · Go 实现

思考

去掉最少区间使剩下的互不重叠，等价于选出最多互不重叠区间。枚举子集不可行。

按右端点升序后贪心：能接在上一段后面的就留下。先结束的区间给后面留出更多空间，因此按右端排序。

答案初值为区间总数，每留下一段减一，即「总数减去最大相容子集」。

我们首先将区间按照右边界升序排序，用一个变量 $\mathit{\text{pre}}$ 记录上一个区间的右边界，用一个变量 $\mathit{\text{ans}}$ 记录需要移除的区间数量，初始时 $\mathit{\text{ans}}=\mathit{\text{intervals.length}}$。

然后遍历区间，对于每一个区间：

• 若当前区间的左边界大于等于 $\mathit{\text{pre}}$，说明该区间无需移除，直接更新 $\mathit{\text{pre}}$ 为当前区间的右边界，然后将 $\mathit{\text{ans}}$ 减一；
• 否则，说明该区间需要移除，不需要更新 $\mathit{\text{pre}}$ 和 $\mathit{\text{ans}}$。

最后返回 $\mathit{\text{ans}}$ 即可。

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

func eraseOverlapIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	ans := len(intervals)
	pre := math.MinInt32
	for _, e := range intervals {
		l, r := e[0], e[1]
		if pre <= l {
			ans--
			pre = r
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

446. 等差数列划分 II - 子序列

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

• 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
• 再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

• 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

 

示例 1：

输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：

输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

 

提示：

• 1  <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1

方法一：动态规划 + 哈希表 · Go 实现

思考

子序列不必连续，公差范围大，枚举长度至少为 $3$ 的子序列不可行。 $n\le 1000$，可以接受 $O(n^2)$。

令 $f[i][d]$ 为以 $i$ 结尾、公差 $d$ 的弱等差子序列（至少两个元素）个数。枚举 $j<i$， $d=nums[i]-nums[j]$，已有的 $f[j][d]$ 条再接上 $nums[i]$ 就成为长度至少为 $3$ 的答案，同时 $f[i][d]$ 加上 $f[j][d]+1$（含新的数对）。

公差用哈希表而不开数组。先把 $f[j][d]$ 计入答案，再更新 $f[i][d]$，弱序列与真切片在同一次枚举中完成。

我们定义 $f[i][d]$ 表示以 $nums[i]$ 为结尾，公差为 $d$ 的弱等差子序列（最少有两个元素）的个数。由于 $d$ 的范围很大，所以我们使用哈希表来统计。

接下来，我们枚举 $nums$ 中的所有元素对 $(nums[i],nums[j])$，其中 $j<i$。我们将其作为等差数列的最后两个元素，由此即可得到公差 $d=nums[i]-nums[j]$。由于公差相同，我们可以将 $nums[i]$ 加到以 $nums[j]$ 为结尾的弱等差子序列的末尾，此时以 $nums[i]$ 为结尾的等差子序列的数量为 $f[j][d]$，我们将其加入答案。然后，我们再将 $nums[i]$ 加到以 $nums[j]$ 为结尾的弱等差子序列的末尾，这对应着状态转移 $f[i][d]+=f[j][d]$。同时， $(nums[i],nums[j])$ 这一对元素也可以当作一个弱等差子序列，因此有状态转移 $f[i][d]+=f[j][d]+1$。

枚举结束，返回答案即可。

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

func numberOfArithmeticSlices(nums []int) (ans int) {
	f := make([]map[int]int, len(nums))
	for i := range f {
		f[i] = map[int]int{}
	}
	for i, x := range nums {
		for j, y := range nums[:i] {
			d := x - y
			cnt := f[j][d]
			ans += cnt
			f[i][d] += cnt + 1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

458. 可怜的小猪

困难1 种解法

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

题目、示例与约束

有 buckets 桶液体，其中 正好有一桶 含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

1. 选择若干活猪进行喂养
2. 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
3. 小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
4. 过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
5. 重复这一过程，直到时间用完。

给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回 在规定时间内判断哪个桶有毒所需的 最小 猪数 。

 

示例 1：

输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出：5

示例 2：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
输出：2

示例 3：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 30
输出：2

 

提示：

• 1 <= buckets <= 1000
• 1 <= minutesToDie <= minutesToTest <= 100

方法一 · Go 实现

思考

每头猪在测试时间内可喝多次，死亡时刻给出多进制信息，而不是简单的「死/活一次」。

一轮等待能区分 $\mathit{\text{minutesToTest}}/\mathit{\text{minutesToDie}}+1$ 种状态（含存活）。 $x$ 头猪可区分 ${\mathit{\text{base}}}^x$ 只桶，求最小 $x$ 使该值不小于桶数。

从 $1$ 累乘 $\mathit{\text{base}}$ 直到覆盖桶数，即对 $\mathit{\text{buckets}}$ 取以 $\mathit{\text{base}}$ 为底的向上对数。

func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
	base := minutesToTest/minutesToDie + 1
	res := 0
	for p := 1; p < buckets; p *= base {
		res++
	}
	return res
}

力扣原题 · Doocs 题解来源

464. 我能赢吗

中等1 种解法

标签：位运算、记忆化、数学、动态规划、位掩码、博弈

题目、示例与约束

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过  100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

 

示例 1：

输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2:

输入：maxChoosableInteger = 10, desiredTotal = 0
输出：true

示例 3:

输入：maxChoosableInteger = 10, desiredTotal = 1
输出：true

 

提示:

• 1 <= maxChoosableInteger <= 20
• 0 <= desiredTotal <= 300

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

思考

两人轮流从 $1..n$ 里不放回取数，累计先达到目标者胜。 $n\le 20$，状态是已选集合，全集枚举博弈树会重复。

总和不足则无人能赢。否则 $dfs(\mathit{\text{mask}},s)$：枚举未选的 $i$，若 $s+i$ 已达目标或对手在新状态下必败，则当前赢。对 $\mathit{\text{mask}}$ 记忆化。

位掩码把集合压成整数，子问题至多 $2^n$ 个。先判总和，避免在必输局面上搜索。

我们首先判断可以选择的所有整数的和是否小于目标值，如果是，说明无论如何都无法赢，直接返回 false。

然后，我们设计一个函数 $\mathit{\text{dfs}}(mask,s)$，其中 mask 表示当前已选择的整数的状态，s 表示当前的累计和。函数返回值为当前玩家是否能赢。

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

我们遍历 $1$ 到 $maxChoosableInteger$ 中的每个整数 $i$，如果 $i$ 还没有被选择，我们可以选择 $i$，如果选择 $i$ 后的累计和 $s+i$ 大于等于目标值 desiredTotal，或者对手选择 $i$ 后的结果是输的，那么当前玩家就是赢的，返回 true。

如果没有任何一个选择能让当前玩家赢，那么当前玩家就是输的，返回 false。

为了避免重复计算，我们使用一个哈希表 f 记录已经计算过的状态，键为 mask，值为当前玩家是否能赢。

时间复杂度 $O(2^n)$，空间复杂度 $O(2^n)$。其中 $n$ 是 maxChoosableInteger。

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	if (1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal {
		return false
	}
	f := map[int]bool{}
	var dfs func(int, int) bool
	dfs = func(mask, s int) bool {
		if v, ok := f[mask]; ok {
			return v
		}
		for i := 1; i <= maxChoosableInteger; i++ {
			if mask>>i&1 == 0 {
				if s+i >= desiredTotal || !dfs(mask|1<<i, s+i) {
					f[mask] = true
					return true
				}
			}
		}
		f[mask] = false
		return false
	}
	return dfs(0, 0)
}

力扣原题 · Doocs 题解来源

465. 最优账单平衡 🔒

困难1 种解法

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

题目、示例与约束

给你一个表示交易的数组 transactions ，其中 transactions[i] = [fromi, toi, amounti] 表示 ID = fromi 的人给 ID = toi 的人共计 amounti $ 。

请你计算并返回还清所有债务的最小交易笔数。

 

示例 1：

输入：transactions = [[0,1,10],[2,0,5]]
输出：2
解释：
#0 给 #1 $10 。
#2 给 #0 $5 。
需要进行两笔交易。一种结清债务的方式是 #1 给 #0 和 #2 各 $5 。

示例 2：

输入：transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
输出：1
解释：
#0 给 #1 $10 。
#1 给 #0 $1 。
#1 给 #2 $5 。
#2 给 #0 $5 。
因此，#1 只需要给 #0 $4 ，所有的债务即可还清。

 

提示：

• 1 <= transactions.length <= 8
• transactions[i].length == 3
• 0 <= fromi, toi < 12
• fromi != toi
• 1 <= amounti <= 100

方法一：状态压缩动态规划 + 子集枚举 · Go 实现

思考

把债务清零的最少转账次数。余额为 $0$ 的人可以忽略。对剩余 $m$ 个人枚举转账顺序， $m\le 12$ 仍偏大，但可以按子集划分。

一个和为 $0$ 的子集最少需要 $|S|-1$ 次转账。令 $f[i]$ 为集合 $i$ 清零的最少次数：仅当收支和为 $0$ 时， $f[i]$ 不超过 $|i|-1$，再与所有非空真子集之和取最小。

子集枚举是 $O(3^m)$。先把交易收成余额数组，再只对和为零的集合做转移。

我们先遍历数组 transactions，统计每个人的收支情况，然后将所有收支不为零的人的收支情况存入数组 $nums$ 中。如果我们可以找到一个子集，子集中共有 $k$ 个人，且这 $k$ 个人的收支情况之和为零，那么我们最多通过 $k-1$ 次交易，就能够使得这 $k$ 个人的收支情况全部清零。这样，我们就能将原问题转化成一个子集枚举的问题。

我们定义 $f[i]$ 表示将集合 $i$ 的所有元素的收支情况全部清零，所需的最少交易次数，初始时 $f[0]=0$，其余 $f[i]=+\mathrm{\infty }$。

考虑 $f[i]$，其中 $i\in [1,2^m)$, $m$ 是数组 $nums$ 的长度。我们可以统计集合 $i$ 中所有元素的收支情况之和 $s$，如果 $s=0$，那么 $f[i]$ 的取值不超过 $|i|-1$，其中 $|i|$ 表示集合 $i$ 中的元素个数。然后我们可以枚举 $i$ 的所有非空子集 $j$，计算 $f[j]+f[i-j]$，其中 $f[j]$ 和 $f[i-j]$ 分别表示将集合 $j$ 和 $i-j$ 的所有元素的收支情况全部清零，所需的最少交易次数。我们可以得到状态转移方程：

$$f[i]=\{\begin{array}{ll}0,& i=0\\ +\mathrm{\infty },& i\ne 0,s\ne 0\\ min(|i|-1,\underset{j\subset i,j\ne \mathrm{\varnothing }}{min}\{f[j]+f[i-j]\}),& i\ne 0,s=0\end{array}$$

其中 $j\subset i$ 表示 $j$ 是 $i$ 的子集，且 $j\ne \mathrm{\varnothing }$。

最终答案即为 $f[2^m-1]$。

时间复杂度 $O(3^n)$，空间复杂度 $O(2^n)$。其中 $n$ 是人的数量，本题中 $n\le 12$。

func minTransfers(transactions [][]int) int {
	g := [12]int{}
	for _, t := range transactions {
		g[t[0]] -= t[2]
		g[t[1]] += t[2]
	}
	nums := []int{}
	for _, x := range g {
		if x != 0 {
			nums = append(nums, x)
		}
	}
	m := len(nums)
	f := make([]int, 1<<m)
	for i := 1; i < 1<<m; i++ {
		f[i] = 1 << 29
		s := 0
		for j, x := range nums {
			if i>>j&1 == 1 {
				s += x
			}
		}
		if s == 0 {
			f[i] = bits.OnesCount(uint(i)) - 1
			for j := (i - 1) & i; j > 0; j = (j - 1) & i {
				f[i] = min(f[i], f[j]+f[i^j])
			}
		}
	}
	return f[1<<m-1]
}

力扣原题 · Doocs 题解来源

466. 统计重复个数

困难1 种解法

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

题目、示例与约束

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

• 例如，str == ["abc", 3] =="abcabcabc" 。

如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。

• 例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。

现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。

请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。

 

示例 1：

输入：s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
输出：2

示例 2：

输入：s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
输出：1

 

提示：

• 1 <= s1.length, s2.length <= 100
• s1 和 s2 由小写英文字母组成
• 1 <= n1, n2 <= 106

方法一：预处理 + 递推 · Go 实现

思考

$n_1$ 个 $s_1$ 里能抽出多少个 $n_2$ 个 $s_2$。直接模拟拼接， $n_1$ 很大时重复扫 $s_2$ 的同一起点。

预处理：从 $s_2$ 的每个位置 $i$ 出发，扫完一个 $s_1$ 后得到「匹配了几个 $s_2$」以及下一个下标。然后循环 $n_1$ 次按表递推，答案除以 $n_2$。

$s_2$ 长度有限，状态只有起点下标，一次 $s_1$ 的匹配被做成 $O(1)$ 转移。

我们预处理出以字符串 $s_2$ 的每个位置 $i$ 开始匹配一个完整的 $s_1$ 后，下一个位置 $j$ 以及经过了多少个 $s_2$，即 $d[i]=(cnt,j)$，其中 $cnt$ 表示匹配了多少个 $s_2$，而 $j$ 表示字符串 $s_2$ 的下一个位置。

接下来，我们初始化 $j=0$，然后循环 $n1$ 次，每一次将 $d[j][0]$ 加到答案中，然后更新 $j=d[j][1]$。

最后得到的答案就是 $n1$ 个 $s_1$ 所能匹配的 $s_2$ 的个数，除以 $n2$ 即可得到答案。

时间复杂度 $O(m\times n+n_1)$，空间复杂度 $O(n)$。其中 $m$ 和 $n$ 分别是 $s_1$ 和 $s_2$ 的长度。

func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) (ans int) {
	n := len(s2)
	d := make([][2]int, n)
	for i := 0; i < n; i++ {
		j := i
		cnt := 0
		for k := range s1 {
			if s1[k] == s2[j] {
				j++
				if j == n {
					cnt++
					j = 0
				}
			}
		}
		d[i] = [2]int{cnt, j}
	}
	for j := 0; n1 > 0; n1-- {
		ans += d[j][0]
		j = d[j][1]
	}
	ans /= n2
	return
}

力扣原题 · Doocs 题解来源

467. 环绕字符串中唯一的子字符串

中等1 种解法

标签：字符串、动态规划

题目、示例与约束

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

 

示例 1：

输入：s = "a"
输出：1
解释：字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。

 

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

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

思考

环形字母表中的唯一连续子串个数。枚举每个子串再去重，长度平方不可行。以同一字母结尾的连续段，短的被长的包含。

令 $f[c]$ 为以 $c$ 结尾的最长合法段长度，答案为所有 $f[c]$ 之和。扫描时维护当前连续长度 $k$（相邻差模 $26$ 为 $1$ 则加一，否则重置）。

只保留每个结尾字母的最大 $k$，重复子串不会被加两次。

我们不妨定义一个长度为 $26$ 的数组 $f$，其中 $f[i]$ 表示以第 $i$ 个字符结尾的最长连续子串的长度。那么答案就是 $f$ 中所有元素的和。

我们定义一个变量 $k$，表示以当前字符结尾的最长连续子串的长度。遍历字符串 $s$，对于每个字符 $c$，如果 $c$ 和前一个字符 $s[i-1]$ 之间的差值为 $1$，那么 $k$ 就加 $1$，否则 $k$ 重置为 $1$。然后更新 $f[c]$ 为 $f[c]$ 和 $k$ 的较大值。

最后返回 $f$ 中所有元素的和即可。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(|\mathrm{\Sigma }|)$，其中 $\mathrm{\Sigma }$ 是字符集，这里是小写字母集合。

func findSubstringInWraproundString(s string) (ans int) {
	f := [26]int{}
	k := 0
	for i := range s {
		if i > 0 && (s[i]-s[i-1]+26)%26 == 1 {
			k++
		} else {
			k = 1
		}
		f[s[i]-'a'] = max(f[s[i]-'a'], k)
	}
	for _, x := range f {
		ans += x
	}
	return
}

力扣原题 · Doocs 题解来源

471. 编码最短长度的字符串 🔒

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给定一个 非空 字符串，将其编码为具有最短长度的字符串。

编码规则是：k[encoded_string]，其中在方括号 encoded_string 中的内容重复 k 次。

注：

• k 为正整数
• 如果编码的过程不能使字符串缩短，则不要对其进行编码。如果有多种编码方式，返回 任意一种 即可

 

示例 1：

输入：s = "aaa"
输出："aaa"
解释：无法将其编码为更短的字符串，因此不进行编码。

示例 2：

输入：s = "aaaaa"
输出："5[a]"
解释："5[a]" 比 "aaaaa" 短 1 个字符。

示例 3：

输入：s = "aaaaaaaaaa"
输出："10[a]"
解释："a9[a]" 或 "9[a]a" 都是合法的编码，和 "10[a]" 一样长度都为 5。

示例 4：

输入：s = "aabcaabcd"
输出："2[aabc]d"
解释："aabc" 出现两次，因此一种答案可以是 "2[aabc]d"。

示例 5：

输入：s = "abbbabbbcabbbabbbc"
输出："2[2[abbb]c]"
解释："abbbabbbc" 出现两次，但是 "abbbabbbc" 可以编码为 "2[abbb]c"，因此一种答案可以是 "2[2[abbb]c]"。

 

提示：

• 1 <= s.length <= 150
• s 由小写英文字母组成

方法一：动态规划（区间 DP） · Go 实现

思考

要把 $s$ 收成最短编码，可整体写成 $k[t]$，也可在某处切开分别编码。 $n\le 150$，适合区间 DP。

$f[i][j]$ 为 $s[i..j]$ 的最短编码。先用「倍增串查找周期」得到整段压缩 $g(i,j)$（长度小于 $5$ 则不压），再枚举切点与 $f[i][k]+f[k+1][j]$ 比长度。 $i$ 从大到小、 $j$ 从小到大，保证子区间已算完。

周期检测复用第 $459$ 题的技巧；括号里填的是周期串自己的最短编码，而不是原文。

在这道题中，我们需要判断一个字符串是否能够进行压缩，也即是说，一个字符串是否能通过其子串重复多次构成。我们可以利用第 $459$ 题的方法来判断，定义一个方法 $g(i,j)$，表示将字符串 $s[i...j]$ 进行压缩后得到的字符串。

接下来，我们用动态规划的方法，将字符串 $s$ 编码成一个最短长度的字符串。

我们定义 $f[i][j]$ 表示将字符串 $s[i..j]$ 编码后的最短字符串。如果直接将 $s[i..j]$ 进行压缩编码，那么 $f[i][j]=g(i,j)$，如果我们将其分成两个子串进行编码，那么 $f[i][j]$ 的值为 $f[i][k]+f[k+1][j]$ 的最小值，其中 $i\le k<j$。取两种情况下长度较小的字符串即可。

在枚举 $i$ 和 $j$ 时，我们可以从大到小枚举 $i$，然后从小到大枚举 $j$，这样我们在计算 $f[i][j]$ 时， $f[i][k]$ 和 $f[k+1][j]$ 的值都已经被计算过了。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 是字符串 $s$ 的长度。

func encode(s string) string {
	n := len(s)
	f := make([][]string, n)
	for i := range f {
		f[i] = make([]string, n)
	}
	g := func(i, j int) string {
		t := s[i : j+1]
		if len(t) < 5 {
			return t
		}
		k := strings.Index((t + t)[1:], t) + 1
		if k < len(t) {
			cnt := len(t) / k
			return strconv.Itoa(cnt) + "[" + f[i][i+k-1] + "]"
		}
		return t
	}
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			f[i][j] = g(i, j)
			if j-i+1 > 4 {
				for k := i; k < j; k++ {
					t := f[i][k] + f[k+1][j]
					if len(t) < len(f[i][j]) {
						f[i][j] = t
					}
				}
			}
		}
	}
	return f[0][n-1]
}

力扣原题 · Doocs 题解来源

473. 火柴拼正方形

中等1 种解法

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

题目、示例与约束

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

 

示例 1:

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

 

提示:

• 1 <= matchsticks.length <= 15
• 1 <= matchsticks[i] <= 108

方法一：排序 + 回溯 · Go 实现

思考

四边等长即总和能被 $4$ 整除，且没有一根超过边长。把火柴分配到四条边， $n\le 15$，朴素 $4^n$ 需剪枝。

从大到小放：当前棍尝试加入每条尚未超长的边，相同长度的边只试一次。边长或最大棍不合法则直接失败。

大棍先放更容易提前超限；相等边去重避免对称状态。

用 $edges[i]$ 记录正方形每条边当前的长度，对于第 $u$ 根火柴，尝试把它加到 $edges[i]$ 每条边，若加入后 $edges[i]$ 不超过正方形期望长度 $x$，则继续往下递归 $u+1$ 根火柴。若所有火柴都能被加入，说明满足拼成正方形的要求。

这里对 $matchsticks$ 从大到小排序，可以减少搜索次数。

时间复杂度 $O(4^n)$，其中 $n$ 表示 $matchsticks$ 的长度。每根火柴可以被放入正方形的 $4$ 条边，共有 $n$ 根火柴。

func makesquare(matchsticks []int) bool {
	s := 0
	for _, v := range matchsticks {
		s += v
	}
	if s%4 != 0 {
		return false
	}
	sort.Sort(sort.Reverse(sort.IntSlice(matchsticks)))
	edges := make([]int, 4)
	var dfs func(u, x int) bool
	dfs = func(u, x int) bool {
		if u == len(matchsticks) {
			return true
		}
		for i := 0; i < 4; i++ {
			if i > 0 && edges[i-1] == edges[i] {
				continue
			}
			edges[i] += matchsticks[u]
			if edges[i] <= x && dfs(u+1, x) {
				return true
			}
			edges[i] -= matchsticks[u]
		}
		return false
	}
	return dfs(0, s/4)
}

力扣原题 · Doocs 题解来源

474. 一和零

中等2 种解法

标签：数组、字符串、动态规划、背包问题、0-1 背包

题目、示例与约束

给你一个二进制字符串数组 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

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

思考

在 $0$、 $1$ 个数受限下选最多字符串，是二维费用的 $0$-$1$ 背包。子集枚举不可行。

$f[i][j][k]$：前 $i$ 个串、至多 $j$ 个 $0$、 $k$ 个 $1$ 的最大个数。不选抄上一行，选则加上 $1$（费用够时）。

先统计当前串的 $0/1$ 个数再填表，保证转移用的是这一件物品的费用。

我们定义 $f[i][j][k]$ 表示在前 $i$ 个字符串中，使用 $j$ 个 0 和 $k$ 个 1 的情况下最多可以得到的字符串数量。初始时 $f[i][j][k]=0$，答案为 $f[sz][m][n]$，其中 $sz$ 是数组 $strs$ 的长度。

对于 $f[i][j][k]$，我们有两种决策：

• 不选第 $i$ 个字符串，此时 $f[i][j][k]=f[i-1][j][k]$；
• 选第 $i$ 个字符串，此时 $f[i][j][k]=f[i-1][j-a][k-b]+1$，其中 $a$ 和 $b$ 分别是第 $i$ 个字符串中 $0$ 和 $1$ 的数量。

我们取两种决策中的最大值，即可得到 $f[i][j][k]$ 的值。

最终的答案即为 $f[sz][m][n]$。

时间复杂度 $O(sz\times m\times n)$，空间复杂度 $O(sz\times m\times n)$。其中 $sz$ 是数组 $strs$ 的长度；而 $m$ 和 $n$ 分别是字符串中 $0$ 和 $1$ 的数量上限。

func findMaxForm(strs []string, m int, n int) int {
	sz := len(strs)
	f := make([][][]int, sz+1)
	for i := range f {
		f[i] = make([][]int, m+1)
		for j := range f[i] {
			f[i][j] = make([]int, n+1)
		}
	}
	for i := 1; i <= sz; i++ {
		a, b := count(strs[i-1])
		for j := 0; j <= m; j++ {
			for k := 0; k <= n; k++ {
				f[i][j][k] = f[i-1][j][k]
				if j >= a && k >= b {
					f[i][j][k] = max(f[i][j][k], f[i-1][j-a][k-b]+1)
				}
			}
		}
	}
	return f[sz][m][n]
}

func count(s string) (int, int) {
	a := strings.Count(s, "0")
	return a, len(s) - a
}

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

思考

$f[i]$ 只依赖 $f[i-1]$，将 $j,k$ 倒序更新并丢掉第一维，空间降为 $O(mn)$，避免同一字符串被用两次。

我们注意到 $f[i][j][k]$ 的计算只和 $f[i-1][j][k]$ 以及 $f[i-1][j-a][k-b]$ 有关，因此我们可以去掉第一维，将空间复杂度优化到 $O(m\times n)$。

func findMaxForm(strs []string, m int, n int) int {
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for _, s := range strs {
		a, b := count(s)
		for j := m; j >= a; j-- {
			for k := n; k >= b; k-- {
				f[j][k] = max(f[j][k], f[j-a][k-b]+1)
			}
		}
	}
	return f[m][n]
}

func count(s string) (int, int) {
	a := strings.Count(s, "0")
	return a, len(s) - a
}

力扣原题 · Doocs 题解来源

486. 预测赢家

中等2 种解法

标签：递归、极小化极大、数组、数学、动态规划、博弈、零和博弈

题目、示例与约束

给你一个整数数组 nums。

玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。

每一回合，玩家从数组的 任意一端 取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中 移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。

注意，如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

 

示例 1：

输入：nums = [1,5,2]

输出：false

解释：

• 玩家 1 必须先取 1 或 2，两种选择都会导致相同的结果。
• 如果玩家 1 取 1，数组变为 [5, 2]。玩家 2 取 5，剩下 2 给玩家 1。
• 如果玩家 1 取 2，数组变为 [1, 5]。玩家 2 取 5，剩下 1 给玩家 1。
• 无论哪种情况，玩家 1 最终得到 1 + 2 = 3，玩家 2 得到 5。玩家 1 永远无法获胜，所以返回 false。

示例 2：

输入：nums = [1,5,233,7]

输出：true

解释：

• 玩家 1 先取 1，剩下 [5,233,7]。然后玩家 2 必须在 5 和 7 之间选择，无论玩家 2 选择哪个数字，玩家 1 在下一次回合都可以取 233。
• 玩家 1 的得分（234）高于玩家 2（12），所以返回 true。

 

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 107

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

思考

两人轮流取两端，求先手得分是否不少于后手。枚举取法树会重复同一区间。

$dfs(i,j)$ 表示当前玩家在 $[i,j]$ 上相对对手的最大分差：取左得 $nums[i]-dfs(i+1,j)$，取右对称。先手获胜当且仅当 $dfs(0,n-1)\ge 0$。

区间状态 $O(n^2)$，记忆化后每人总是面对已经最优的残局。

我们设计一个函数 $\mathit{\text{dfs}}(i,j)$，表示从第 $i$ 个数到第 $j$ 个数，当前玩家与另一个玩家的得分之差的最大值。那么答案就是 $\mathit{\text{dfs}}(0,n-1)\ge 0$。

函数 $\mathit{\text{dfs}}(i,j)$ 的计算方法如下：

• 如果 $i>j$，说明当前没有数字了，所以当前玩家没有分数可以拿，差值为 $0$，即 $\mathit{\text{dfs}}(i,j)=0$。
• 否则，当前玩家有两种选择，如果选择第 $i$ 个数，那么当前玩家与另一个玩家的得分之差为 $\mathit{\text{nums}}[i]-\mathit{\text{dfs}}(i+1,j)$；如果选择第 $j$ 个数，那么当前玩家与另一个玩家的得分之差为 $\mathit{\text{nums}}[j]-\mathit{\text{dfs}}(i,j-1)$。当前玩家会选择两种情况中差值较大的情况，也就是说 $\mathit{\text{dfs}}(i,j)=max(\mathit{\text{nums}}[i]-\mathit{\text{dfs}}(i+1,j),\mathit{\text{nums}}[j]-\mathit{\text{dfs}}(i,j-1))$。

最后，我们只需要判断 $\mathit{\text{dfs}}(0,n-1)\ge 0$ 即可。

为了避免重复计算，我们可以使用记忆化搜索的方法，用一个数组 $f$ 记录所有的 $\mathit{\text{dfs}}(i,j)$ 的值，当函数再次被调用到时，我们可以直接从 $f$ 中取出答案而不需要重新计算。

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

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

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

思考

方法一的转移可改成表： $f[i][j]$ 同义，先填长度为 $1$ 的对角线，再按区间从小到大（ $i$ 降 $j$ 升）填。去掉递归栈，复杂度相同。

我们也可以使用动态规划的方法，定义 $f[i][j]$ 表示当前玩家在 $\mathit{\text{nums}}[i..j]$ 这些数字中能够获得的最大得分的差值。那么最后答案就是 $f[0][n-1]\ge 0$。

初始时 $f[i][i]=\mathit{\text{nums}}[i]$，因为只有一个数，所以当前玩家只能拿取这个数，得分差值为 $\mathit{\text{nums}}[i]$。

考虑 $f[i][j]$，其中 $i<j$，有两种情况：

• 如果当前玩家拿走了 $\mathit{\text{nums}}[i]$，那么剩下的数字为 $\mathit{\text{nums}}[i+1..j]$，此时轮到另一个玩家进行游戏，所以 $f[i][j]=\mathit{\text{nums}}[i]-f[i+1][j]$。
• 如果当前玩家拿走了 $\mathit{\text{nums}}[j]$，那么剩下的数字为 $\mathit{\text{nums}}[i..j-1]$，此时轮到另一个玩家进行游戏，所以 $f[i][j]=\mathit{\text{nums}}[j]-f[i][j-1]$。

因此，最终的状态转移方程为 $f[i][j]=max(\mathit{\text{nums}}[i]-f[i+1][j],\mathit{\text{nums}}[j]-f[i][j-1])$。

最后，我们只需要判断 $f[0][n-1]\ge 0$ 即可。

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

相似题目：

• 877. 石子游戏

func predictTheWinner(nums []int) bool {
	n := len(nums)
	f := make([][]int, n)
	for i, x := range nums {
		f[i] = make([]int, n)
		f[i][i] = x
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = max(nums[i]-f[i+1][j], nums[j]-f[i][j-1])
		}
	}
	return f[0][n-1] >= 0
}

力扣原题 · Doocs 题解来源

487. 最大连续1的个数 II 🔒

中等1 种解法

标签：数组、动态规划、滑动窗口

题目、示例与约束

给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。

 

示例 1：

输入：nums = [1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
     当翻转以后，最大连续 1 的个数为 4。

示例 2:

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

 

提示:

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1.

 

进阶：如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？

方法一：滑动窗口 · Go 实现

思考

最多把一个 $0$ 当成 $1$，求最长连续 $1$。这是「窗口内 $0$ 的个数不超过 $1$」的最长窗口。

右端扩张，用 $x\oplus 1$ 统计窗口内的 $0$；超过一个则左端右移一格。只需最大长度，左端每次只移一步，答案为 $n-l$。

与「最多替换 $k$ 次」同类：窗口单调变长，不必把左端一次移到底。

我们可以遍历数组，用一个变量 $\mathit{\text{cnt}}$ 记录当前窗口中 0 的个数，当 $\mathit{\text{cnt}}>1$ 时，我们将窗口的左边界右移一位。

遍历结束后，窗口的长度即为最大连续 1 的个数。

注意，在上述过程中，我们不需要循环将窗口的左边界右移，而是直接将左边界右移一位，这是因为，题目求的是最大连续 1 的个数，因此，窗口的长度只会增加，不会减少，所以我们不需要循环右移左边界。

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

func findMaxConsecutiveOnes(nums []int) int {
	l, cnt := 0, 0
	for _, x := range nums {
		cnt += x ^ 1
		if cnt > 1 {
			cnt -= nums[l] ^ 1
			l++
		}
	}
	return len(nums) - l
}

力扣原题 · Doocs 题解来源

488. 祖玛游戏

困难1 种解法

标签：栈、广度优先搜索、记忆化、字符串、动态规划

题目、示例与约束

你正在参与祖玛游戏的一个变种。

在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。

你的目标是 清空 桌面上所有的球。每一回合：

• 从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。
• 接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。
  • 如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。
• 如果桌面上所有球都被移除，则认为你赢得本场游戏。
• 重复这个过程，直到你赢了游戏或者手中没有更多的球。

给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。

 

示例 1：

输入：board = "WRRBBW", hand = "RB"
输出：-1
解释：无法移除桌面上的所有球。可以得到的最好局面是：
- 插入一个 'R' ，使桌面变为 WRRRBBW 。WRRRBBW -> WBBW
- 插入一个 'B' ，使桌面变为 WBBBW 。WBBBW -> WW
桌面上还剩着球，没有其他球可以插入。

示例 2：

输入：board = "WWRRBBWW", hand = "WRBRW"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'R' ，使桌面变为 WWRRRBBWW 。WWRRRBBWW -> WWBBWW
- 插入一个 'B' ，使桌面变为 WWBBBWW 。WWBBBWW -> WWWW -> empty
只需从手中出 2 个球就可以清空桌面。

示例 3：

输入：board = "G", hand = "GGGGG"
输出：2
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'G' ，使桌面变为 GG 。
- 插入一个 'G' ，使桌面变为 GGG 。GGG -> empty
只需从手中出 2 个球就可以清空桌面。

示例 4：

输入：board = "RBYYBBRRB", hand = "YRBGB"
输出：3
解释：要想清空桌面上的球，可以按下述步骤：
- 插入一个 'Y' ，使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B
- 插入一个 'B' ，使桌面变为 BB 。
- 插入一个 'B' ，使桌面变为 BBB 。BBB -> empty
只需从手中出 3 个球就可以清空桌面。

 

提示：

• 1 <= board.length <= 16
• 1 <= hand.length <= 5
• board 和 hand 由字符 'R'、'Y'、'B'、'G' 和 'W' 组成
• 桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球

方法一：Go 实现（halfrost） · Go 实现

halfrost · 源码 · MIT 许可

本次根据原始 Go 源码整理的中文说明，非 halfrost 书籍原文。

把当前球串和剩余手牌作为搜索状态，按插入次数逐层进行广度优先搜索。每次从手牌中取一个字符插到球串中，再由 del3 删除连续至少三个同色球并处理后续消除；搜索遇到空球串时返回当前层数，队列耗尽则返回 −1。

func findMinStep(board string, hand string) int {
	q := [][]string{{board, hand}}
	mp := make(map[string]bool)
	minStep := 0
	for len(q) > 0 {
		length := len(q)
		minStep++
		for length > 0 {
			length--
			cur := q[0]
			q = q[1:]
			curB, curH := cur[0], cur[1]
			for i := 0; i < len(curB); i++ {
				for j := 0; j < len(curH); j++ {
					curB2 := del3(curB[0:i] + string(curH[j]) + curB[i:])
					curH2 := curH[0:j] + curH[j+1:]
					if len(curB2) == 0 {
						return minStep
					}
					if _, ok := mp[curB2+curH2]; ok {
						continue
					}
					mp[curB2+curH2] = true
					q = append(q, []string{curB2, curH2})
				}
			}
		}
	}
	return -1
}

func del3(str string) string {
	cnt := 1
	for i := 1; i < len(str); i++ {
		if str[i] == str[i-1] {
			cnt++
		} else {
			if cnt >= 3 {
				return del3(str[0:i-cnt] + str[i:])
			}
			cnt = 1
		}
	}
	if cnt >= 3 {
		return str[0 : len(str)-cnt]
	}
	return str
}

力扣原题 · Doocs 题解来源

494. 目标和

中等2 种解法

标签：数组、动态规划、回溯、背包问题、0-1 背包

题目、示例与约束

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

 

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

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

 

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

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

思考

给每个数加正号或负号使结果为 $\mathit{\text{target}}$。 $2^n$ 枚举在 $n\le 20$ 时勉强，但可以化成子集和。

记负号部分之和为 $x$，则 $(s-x)-x=\mathit{\text{target}}$，即 $x=(s-\mathit{\text{target}})/2$。 $s<\mathit{\text{target}}$ 或差为奇数则无解。 $f[i][j]$ 为前 $i$ 个数凑出 $j$ 的方案数。

空集对应 $f[0][0]=1$。选或不选 $x$ 的转移与 $0$-$1$ 背包计数相同。

我们记数组 $\mathit{\text{nums}}$ 所有元素的和为 $s$，添加负号的元素之和为 $x$，则添加正号的元素之和为 $s-x$，则有：

$$(s-x)-x=\mathit{\text{target}}\Rightarrow x=\frac{s-\mathit{\text{target}}}{2}$$

由于 $x\ge 0$，且 $x$ 为整数，所以 $s\ge \mathit{\text{target}}$ 且 $s-\mathit{\text{target}}$ 为偶数。如果不满足这两个条件，则直接返回 $0$。

接下来，我们可以将问题转化为：在数组 $\mathit{\text{nums}}$ 中选取若干元素，使得这些元素之和等于 $\frac{s-\mathit{\text{target}}}{2}$，问有多少种选取方法。

我们可以使用动态规划来解决这个问题。定义 $f[i][j]$ 表示在数组 $\mathit{\text{nums}}$ 的前 $i$ 个元素中选取若干元素，使得这些元素之和等于 $j$ 的选取方案数。

对于 $\mathit{\text{nums}}[i-1]$，我们有两种选择：选取或不选取。如果我们不选取 $\mathit{\text{nums}}[i-1]$，则 $f[i][j]=f[i-1][j]$；如果我们选取 $\mathit{\text{nums}}[i-1]$，则 $f[i][j]=f[i-1][j-\mathit{\text{nums}}[i-1]]$。因此，状态转移方程为：

$$f[i][j]=f[i-1][j]+f[i-1][j-\mathit{\text{nums}}[i-1]]$$

其中，选取的前提是 $j\ge \mathit{\text{nums}}[i-1]$。

最终答案即为 $f[m][n]$。其中 $m$ 为数组 $\mathit{\text{nums}}$ 的长度，而 $n=\frac{s-\mathit{\text{target}}}{2}$。

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

func findTargetSumWays(nums []int, target int) int {
	s := 0
	for _, x := range nums {
		s += x
	}
	if s < target || (s-target)%2 != 0 {
		return 0
	}
	m, n := len(nums), (s-target)/2
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			f[i][j] = f[i-1][j]
			if j >= nums[i-1] {
				f[i][j] += f[i-1][j-nums[i-1]]
			}
		}
	}
	return f[m][n]
}

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

思考

$f[i][j]$ 只依赖上一行，将 $j$ 倒序更新压成一维，空间降为容量大小，同一数字不会用两次。

我们可以发现，方法一中的状态转移方程中， $f[i][j]$ 的值只和 $f[i-1][j]$ 以及 $f[i-1][j-\mathit{\text{nums}}[i-1]]$ 有关，因此我们去掉第一维空间，只使用一维数组即可。

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

func findTargetSumWays(nums []int, target int) int {
	s := 0
	for _, x := range nums {
		s += x
	}
	if s < target || (s-target)%2 != 0 {
		return 0
	}
	n := (s - target) / 2
	f := make([]int, n+1)
	f[0] = 1
	for _, x := range nums {
		for j := n; j >= x; j-- {
			f[j] += f[j-x]
		}
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

509. 斐波那契数

简单2 种解法

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

题目、示例与约束

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

 

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

 

提示：

• 0 <= n <= 30

方法一：递推 · Go 实现

思考

斐波那契满足 $F_n=F_{n-1}+F_{n-2}$。直接递归会重复计算同一子问题； $n\le 30$ 虽小，仍宜改成递推。

用两个变量滚动保存相邻两项，迭代 $n$ 次即可得到 $F_n$，时间和空间均为线性与常数。

我们定义两个变量 $a$ 和 $b$，初始时 $a=0$, $b=1$。

接下来，我们进行 $n$ 次循环，每次循环中，我们将 $a$ 和 $b$ 的值分别更新为 $b$ 和 $a+b$。

最后，返回 $a$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为题目给定的整数 $n$。空间复杂度 $O(1)$。

func fib(n int) int {
	a, b := 0, 1
	for i := 0; i < n; i++ {
		a, b = b, a+b
	}
	return a
}

方法二：矩阵快速幂加速递推 · Go 实现

思考

方法一已是 $O(n)$，对本题足够，但同一线性递推在 $n$ 更大时仍想压到对数级。

$F_n$ 可由固定的 $2\times 2$ 转移矩阵连乘得到。矩阵快速幂把 $n$ 次转移降为 $O(\log n)$ 次乘法，常数略大，适合需要加速同一递推的场景。

我们设 $\mathit{\text{Fib}}(n)$ 表示一个 $1\times 2$ 的矩阵 $\left[\begin{array}{cc}{F}_n& F_{n-1}\end{array}\right]$，其中 $F_n$ 和 $F_{n-1}$ 分别是第 $n$ 个和第 $n-1$ 个斐波那契数。

我们希望根据 $\mathit{\text{Fib}}(n-1)=\left[\begin{array}{cc}{F}_{n-1}& F_{n-2}\end{array}\right]$ 推出 $\mathit{\text{Fib}}(n)$。也即是说，我们需要一个矩阵 $\mathit{\text{base}}$，使得 $\mathit{\text{Fib}}(n-1)\times \mathit{\text{base}}=\mathit{\text{Fib}}(n)$，即：

$$\left[\begin{array}{cc}{F}_{n-1}& F_{n-2}\end{array}\right]\times \mathit{\text{base}}=\left[\begin{array}{cc}{F}_n& F_{n-1}\end{array}\right]$$

由于 $F_n=F_{n-1}+F_{n-2}$，所以矩阵 $\mathit{\text{base}}$ 的第一列为：

$$\left[\begin{array}{c}1\\ 1\end{array}\right]$$

第二列为：

$$\left[\begin{array}{c}1\\ 0\end{array}\right]$$

因此有：

$$\left[\begin{array}{cc}{F}_{n-1}& F_{n-2}\end{array}\right]\times \left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}{F}_n& F_{n-1}\end{array}\right]$$

我们定义初始矩阵 $res=\left[\begin{array}{cc}1& 0\end{array}\right]$，那么 $F_n$ 等于 $res$ 乘以 ${\mathit{\text{base}}}^n$ 的结果矩阵中第一行的第二个元素。使用矩阵快速幂求解即可。

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

func fib(n int) int {
	a := [][]int{{1, 1}, {1, 0}}
	return pow(a, n)[0][1]
}

func mul(a, b [][]int) [][]int {
	m, n := len(a), len(b[0])
	c := make([][]int, m)
	for i := range c {
		c[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < len(b); k++ {
				c[i][j] = c[i][j] + a[i][k]*b[k][j]
			}
		}
	}
	return c
}

func pow(a [][]int, n int) [][]int {
	res := [][]int{{1, 0}}
	for n > 0 {
		if n&1 == 1 {
			res = mul(res, a)
		}
		a = mul(a, a)
		n >>= 1
	}
	return res
}

力扣原题 · Doocs 题解来源

514. 自由之路

困难1 种解法

标签：深度优先搜索、广度优先搜索、字符串、动态规划

题目、示例与约束

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

1. 您可以将 ring 顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
2. 如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

 

示例 1：

 

输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

示例 2:

输入: ring = "godding", key = "godding"
输出: 13

 

提示：

• 1 <= ring.length, key.length <= 100
• ring 和 key 只包含小写英文字母
• 保证 字符串 key 一定可以由字符串  ring 旋转拼出

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

思考

转盘每次转到 key 的下一个字符，可顺时可逆时，还要按确认键。若对每个字符枚举所有环上位置，朴素搜索分支随 |key| 增长。

设 $f[i][j]$ 为拼出 key 前 $i+1$ 个字符且指针停在 $j$ 的最少步数。同一字符的候选位置可预处理。从上一字符的位置转移到当前位置，代价是环上较短弧长再加一次确认。最后在 key 末字符的所有位置上取最小即可。

我们首先预处理出字符串 $ring$ 中每个字符 $c$ 出现的位置列表，记录在数组 $pos[c]$ 中。不妨假设字符串 $key$ 和 $ring$ 的长度分别为 $m$ 和 $n$。

然后我们定义 $f[i][j]$ 表示拼写完字符串 $key$ 的前 $i+1$ 个字符，且 $ring$ 的第 $j$ 个字符与 $12:00$ 方向对齐的最少步数。初始时 $f[i][j]=+\mathrm{\infty }$。答案为 $\underset{0\le j<n}{min}f[m-1][j]$。

我们可以先初始化 $f[0][j]$，其中 $j$ 是字符 $key[0]$ 在 $ring$ 中出现的位置。由于 $ring$ 的第 $j$ 个字符与 $12:00$ 方向对齐，因此我们只需要 $1$ 步即可拼写出 $key[0]$。此外，我们还需要 $min(j,n-j)$ 步将 $ring$ 旋转到 $12:00$ 方向。因此 $f[0][j]=min(j,n-j)+1$。

接下来，我们考虑当 $i\ge 1$ 时，状态如何转移。我们可以枚举 $key[i]$ 在 $ring$ 中的位置列表 $pos[key[i]]$，并枚举 $key[i-1]$ 在 $ring$ 中的位置列表 $pos[key[i-1]]$，然后更新 $f[i][j]$，即 $f[i][j]=\underset{k\in pos[key[i-1]]}{min}f[i-1][k]+min(\mathit{\text{abs}}(j-k),n-\mathit{\text{abs}}(j-k))+1$。

最后，我们返回 $\underset{0\le j<n}{min}f[m-1][j]$ 即可。

时间复杂度 $O(m\times n^2)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是字符串 $key$ 和 $ring$ 的长度。

func findRotateSteps(ring string, key string) int {
	m, n := len(key), len(ring)
	pos := [26][]int{}
	for j, c := range ring {
		pos[c-'a'] = append(pos[c-'a'], j)
	}
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = 1 << 30
		}
	}
	for _, j := range pos[key[0]-'a'] {
		f[0][j] = min(j, n-j) + 1
	}
	for i := 1; i < m; i++ {
		for _, j := range pos[key[i]-'a'] {
			for _, k := range pos[key[i-1]-'a'] {
				f[i][j] = min(f[i][j], f[i-1][k]+min(abs(j-k), n-abs(j-k))+1)
			}
		}
	}
	ans := 1 << 30
	for _, j := range pos[key[m-1]-'a'] {
		ans = min(ans, f[m-1][j])
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

516. 最长回文子序列

中等1 种解法

标签：字符串、动态规划

题目、示例与约束

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

 

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

 

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

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

思考

最长回文子序列不是子串，不能只扩中心。枚举所有子序列再判断回文，数量过多。

设 $f[i][j]$ 为 $s[i..j]$ 的最长回文子序列长度。两端相等则由内段加 $2$，否则取丢掉左端或右端的较优者。按区间长度从短到长（代码中 $i$ 从右向左、 $j$ 向右）填表，保证转移依赖已算出。 $f[0][n-1]$ 即为答案。

我们定义 $f[i][j]$ 表示字符串 $s$ 的第 $i$ 个字符到第 $j$ 个字符之间的最长回文子序列的长度。初始时 $f[i][i]=1$，其余位置的值均为 $0$。

如果 $s[i]=s[j]$，那么 $f[i][j]=f[i+1][j-1]+2$；否则 $f[i][j]=max(f[i+1][j],f[i][j-1])$。

由于 $f[i][j]$ 的值与 $f[i+1][j-1]$, $f[i+1][j]$, $f[i][j-1]$ 有关，所以我们应该从大到小枚举 $i$，从小到大枚举 $j$。

答案即为 $f[0][n-1]$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 为字符串 $s$ 的长度。

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

力扣原题 · Doocs 题解来源

518. 零钱兑换 II

中等2 种解法

标签：数组、动态规划、背包问题、完全背包

题目、示例与约束

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据 保证 最终 结果符合 32 位 带符号整数。

 

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

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

 

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

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

思考

求凑成 amount 的组合数，顺序不同视为同一种。若按排列计数会把同一组合算多次。

这是完全背包的方案数：外层枚举硬币、内层枚举金额，使每种硬币只按一种顺序加入。 $f[i][j]$ 表示用前 $i$ 种硬币凑 $j$ 的方案数，不选第 $i$ 种继承 $f[i-1][j]$，选则加上 $f[i][j-x]$。 $f[0][0]=1$ 作为空组合。

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

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

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

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

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

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

将式子二代入式子一，得到：

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

最终的答案为 $f[m][n]$，其中 $m$ 和 $n$ 分别表示硬币的种类数和总金额。

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

func change(amount int, coins []int) int {
	m, n := len(coins), amount
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	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] += f[i][j-coins[i-1]]
			}
		}
	}
	return f[m][n]
}

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

思考

二维表中 $f[i][j]$ 只依赖上一行的 $j$ 与本行的 $j-x$。压缩成一维后，对每枚硬币从 $x$ 扫到 amount，正序累加即可复用本硬币已更新的状态。

空间降为 $O(\mathit{\text{amount}})$，转移次数不变。

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

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

力扣原题 · Doocs 题解来源

526. 优美的排列

中等1 种解法

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

题目、示例与约束

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

• perm[i] 能够被 i 整除
• i 能够被 perm[i] 整除

给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

 

示例 1：

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
    - perm[1] = 1 能被 i = 1 整除
    - perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
    - perm[1] = 2 能被 i = 1 整除
    - i = 2 能被 perm[2] = 1 整除

示例 2：

输入：n = 1
输出：1

 

提示：

• 1 <= n <= 15

方法一：回溯 · Go 实现

思考

需要统计满足「位置 $i$ 上的数 $j$ 能整除或被整除」的排列数。 $n\le 15$，全排列 $15!$ 不可行，但每个位置的合法数字很少。

先预处理每个位置可放的数字列表，再按位置回溯并标记已用数字。搜到 $n+1$ 即得到一个合法排列。剪枝把搜索限制在整除条件上，对本规模足够。

按位置枚举还能放的数字，满足整除条件则继续搜索。

func countArrangement(n int) int {
	ans := 0
	match := make(map[int][]int)
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if i%j == 0 || j%i == 0 {
				match[i] = append(match[i], j)
			}
		}
	}
	vis := make([]bool, n+1)

	var dfs func(i int)
	dfs = func(i int) {
		if i == n+1 {
			ans++
			return
		}
		for _, j := range match[i] {
			if !vis[j] {
				vis[j] = true
				dfs(i + 1)
				vis[j] = false
			}
		}
	}

	dfs(1)
	return ans
}

力扣原题 · Doocs 题解来源

542. 01 矩阵

中等1 种解法

标签：广度优先搜索、数组、动态规划、矩阵

题目、示例与约束

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

 

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

 

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• mat 中至少有一个 0 

方法一：BFS · Go 实现

思考

每个 $1$ 要到最近的 $0$ 的距离。从每个 $1$ 单独 BFS 是 $O(mn)$ 次搜索。

多源 BFS：所有 $0$ 同时入队，距离为 $0$，向四向扩展未访问格子，距离加一。第一次到达即为最近 $0$。一次队列扫描覆盖全图。

我们创建一个大小和 $\mathit{\text{mat}}$ 一样的矩阵 $\mathit{\text{ans}}$，并将所有的元素初始化为 $-1$。

然后我们遍历 $\mathit{\text{mat}}$，将所有的 $0$ 元素的坐标 $(i,j)$ 加入队列 $\mathit{\text{q}}$，并将 $\mathit{\text{ans}}[i][j]$ 设为 $0$。

接下来，我们使用广度优先搜索，从队列中取出一个元素 $(i,j)$，并遍历其四个方向，如果该方向的元素 $(x,y)$ 满足 $0\le x<m$, $0\le y<n$ 且 $\mathit{\text{ans}}[x][y]=-1$，则将 $\mathit{\text{ans}}[x][y]$ 设为 $\mathit{\text{ans}}[i][j]+1$，并将 $(x,y)$ 加入队列 $\mathit{\text{q}}$。

最后返回 $\mathit{\text{ans}}$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为矩阵 $\mathit{\text{mat}}$ 的行数和列数。

func updateMatrix(mat [][]int) [][]int {
	m, n := len(mat), len(mat[0])
	ans := make([][]int, m)
	for i := range ans {
		ans[i] = make([]int, n)
		for j := range ans[i] {
			ans[i][j] = -1
		}
	}
	type pair struct{ x, y int }
	var q []pair
	for i, row := range mat {
		for j, v := range row {
			if v == 0 {
				ans[i][j] = 0
				q = append(q, pair{i, j})
			}
		}
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		for i := 0; i < 4; i++ {
			x, y := p.x+dirs[i], p.y+dirs[i+1]
			if x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1 {
				ans[x][y] = ans[p.x][p.y] + 1
				q = append(q, pair{x, y})
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

546. 移除盒子

困难1 种解法

标签：记忆化、数组、动态规划

题目、示例与约束

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。

返回 你能获得的最大积分和 。

 

示例 1：

输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)

示例 2：

输入：boxes = [1,1,1]
输出：9

示例 3：

输入：boxes = [1]
输出：1

 

提示：

• 1 <= boxes.length <= 100
• 1 <= boxes[i] <= 100

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

思考

每次消除一段连续同色，得分为长度平方，消除顺序影响后续拼接。区间 DP 的状态还要带上右侧已经连着的同色个数，否则无法表达「先消中间再与右边合并」。

$dfs(i,j,k)$ 表示区间 $[i,j]$ 且 $boxes[j]$ 右侧已有 $k$ 个同色。先把 $j$ 左侧连续同色收进 $k$，再选择直接消掉 $j$ 或找到更左的同色 $h$ 先清开中间再与 $j$ 合并。记忆化避免重复区间。

设计递归函数 dfs(i, j, k) 表示当前处理的区间为 [i, j]，且该区间的右边有 k 个与 boxes[j] 相同的元素，返回该区间的最大积分。答案即为 dfs(0, n - 1, 0)。

对于 dfs(i, j, k)，我们可以直接删除 boxes[j] 和其右边的 k 个元素，所得积分为 dfs(i, j - 1, 0) + (k + 1) * (k + 1)。

我们还可以在区间 [i, j-1] 内枚举下标 h，找到满足 boxes[h] == boxes[j] 的下标，那么我们就将区间 [i, j - 1] 分成两部分，即 [i, h] 和 [h + 1, j - 1]。其中 [i, h] 的部分可以与 boxes[j] 合并，所以积分为 dfs(i, h, k + 1) + dfs(h + 1, j - 1, 0)。求不同 h 下的最大值即可。

我们使用记忆化搜索来优化递归函数的时间复杂度。

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

func removeBoxes(boxes []int) int {
	n := len(boxes)
	f := make([][][]int, n)
	for i := range f {
		f[i] = make([][]int, n)
		for j := range f[i] {
			f[i][j] = make([]int, n)
		}
	}
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if i > j {
			return 0
		}
		for i < j && boxes[j] == boxes[j-1] {
			j, k = j-1, k+1
		}
		if f[i][j][k] > 0 {
			return f[i][j][k]
		}
		ans := dfs(i, j-1, 0) + (k+1)*(k+1)
		for h := i; h < j; h++ {
			if boxes[h] == boxes[j] {
				ans = max(ans, dfs(h+1, j-1, 0)+dfs(i, h, k+1))
			}
		}
		f[i][j][k] = ans
		return ans
	}
	return dfs(0, n-1, 0)
}

力扣原题 · Doocs 题解来源

552. 学生出勤记录 II

困难2 种解法

标签：动态规划

题目、示例与约束

可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

• 'A'：Absent，缺勤
• 'L'：Late，迟到
• 'P'：Present，到场

如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：

• 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
• 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。

给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。

 

示例 1：

输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 
只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。

示例 2：

输入：n = 1
输出：3

示例 3：

输入：n = 10101
输出：183236316

 

提示：

• 1 <= n <= 105

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

思考

长度为 $n$ 的合法串要限制缺勤次数与连续迟到。直接枚举 $3^n$ 种串不可行， $n$ 可达 ${10}^5$。

缺勤只用过 $0$ 次或 $1$ 次，连续迟到只有 $0,1,2$ 三档，六个状态就够了。若从第 $0$ 天递归到第 $n$ 天，调用栈深度为 $n$，在上限处会溢出。

因此从最后一天倒着填。 $f(j,k)$ 表示已缺勤 $j$ 次、当前连续迟到 $k$ 次时，把剩余记录填完的方案数。没有剩余天数时方案数为 $1$。往前一天可以放 P（连续迟到清零）、在 $j=0$ 时放一次 A，或在 $k<2$ 时放 L。答案是 $f(0,0)$，对 ${10}^9+7$ 取模。

设 $f(j,k)$ 表示已经缺勤 $j$ 次、当前连续迟到 $k$ 次时，把尚未填写的出勤记录全部填完的方案数。没有剩余天数时， $f(j,k)=1$。答案是倒推 $n$ 天之后的 $f(0,0)$。

从最后一天往前推。对于每一个状态 $(j,k)$，新的方案数是三种选择之和：

• 到场：连续迟到清零，对应 $f(j,0)$；
• 若 $j=0$，可以缺勤一次，对应 $f(1,0)$；
• 若 $k<2$，可以迟到，对应 $f(j,k+1)$。

每一天都用新数组接住结果，避免覆盖仍要读取的旧状态。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为出勤记录的长度。

func checkRecord(n int) int {
	const mod = int(1e9 + 7)
	f := [2][3]int{{1, 1, 1}, {1, 1, 1}}
	for i := 0; i < n; i++ {
		var g [2][3]int
		for j := 0; j < 2; j++ {
			for k := 0; k < 3; k++ {
				ans := f[j][0]
				if j == 0 {
					ans = (ans + f[1][0]) % mod
				}
				if k < 2 {
					ans = (ans + f[j][k+1]) % mod
				}
				g[j][k] = ans % mod
			}
		}
		f = g
	}
	return f[0][0]
}

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

思考

上一种做法只保留六个后缀方案数。这里把每一天的前缀方案都记下来，天数下标留在表里。

$dp[i][j][k]$ 表示前 $i+1$ 天、缺勤 $j$ 次、连续迟到 $k$ 次的方案数。按放 A / L / P 从上一天转移。最后对最后一天的所有 $(j,k)$ 求和。

动态规划，定义 dp[i][j][k] 表示前 i 天，缺勤 j 次，连续迟到 k 次时，可获得出勤奖励的情况数量

状态转移需要对第 i 天的出勤情况分别讨论：

• 缺勤：之前不能有任何缺勤记录，即 j == 0
• 迟到：之前最多连续迟到 1 次，即 k == 0 || k == 1
• 到场：无限制

const _mod int = 1e9 + 7

func checkRecord(n int) int {
	dp := make([][][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([][]int, 2)
		for j := 0; j < 2; j++ {
			dp[i][j] = make([]int, 3)
		}
	}

	// base case
	dp[0][0][0] = 1
	dp[0][0][1] = 1
	dp[0][1][0] = 1

	for i := 1; i < n; i++ {
		// A
		dp[i][1][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % _mod
		// L
		dp[i][0][1] = dp[i-1][0][0]
		dp[i][0][2] = dp[i-1][0][1]
		dp[i][1][1] = dp[i-1][1][0]
		dp[i][1][2] = dp[i-1][1][1]
		// P
		dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % _mod
		dp[i][1][0] = (dp[i][1][0] + dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2]) % _mod
	}

	var ans int
	for j := 0; j < 2; j++ {
		for k := 0; k < 3; k++ {
			ans = (ans + dp[n-1][j][k]) % _mod
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

553. 最优除法

中等1 种解法

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

题目、示例与约束

给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。

• 例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意：你的表达式不应该包含多余的括号。

 

示例 1：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

 

示例 2:

输入: nums = [2,3,4]
输出: "2/(3/4)"
解释: (2/(3/4)) = 8/3 = 2.667
可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。

 

说明:

• 1 <= nums.length <= 10
• 2 <= nums[i] <= 1000
• 对于给定的输入只有一种最优除法。

方法一 · Go 实现

思考

表达式只有除法，加括号改变的是结合顺序。实数除法下，要让结果尽量大，应尽量减小分母。

长度为 $1$、 $2$ 没有括号可选。更长时，把第一个数当分子、其余全部括成连除，等价于 $a_0/(a_1/a_2/\cdots )$，分母被除得最小。无需搜索全部加括号方案。

func optimalDivision(nums []int) string {
	n := len(nums)
	if n == 1 {
		return strconv.Itoa(nums[0])
	}
	if n == 2 {
		return fmt.Sprintf("%d/%d", nums[0], nums[1])
	}
	ans := &strings.Builder{}
	ans.WriteString(fmt.Sprintf("%d/(", nums[0]))
	for _, num := range nums[1 : n-1] {
		ans.WriteString(strconv.Itoa(num))
		ans.WriteByte('/')
	}
	ans.WriteString(fmt.Sprintf("%d)", nums[n-1]))
	return ans.String()
}

力扣原题 · Doocs 题解来源

562. 矩阵中最长的连续1线段 🔒

中等1 种解法

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

题目、示例与约束

给定一个 m x n 的二进制矩阵 mat ，返回矩阵中最长的连续1线段。

这条线段可以是水平的、垂直的、对角线的或者反对角线的。

 

示例 1:

输入: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
输出: 3

示例 2:

输入: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
输出: 4

 

提示:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] 不是 0 就是 1.

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

思考

最长的连续 $1$ 可沿水平、竖直、两条对角线。对每个起点向四向延伸是 $O(mn\cdot (m+n))$。

用四个表分别记录以 $(i,j)$ 结尾的四向长度，由正上方、正左、左上、右上转移加一。格子为 $0$ 则保持 $0$。四周加一圈空边以免越界。过程中维护全局最大。

我们定义 $f[i][j][k]$ 表示方向为 $k$，且以 $(i,j)$ 结尾的最长连续 $1$ 的长度。其中 $k$ 的取值范围为 $0,1,2,3$，分别表示水平、垂直、对角线、反对角线。

我们也可以用四个二维数组分别表示四个方向的最长连续 $1$ 的长度。

遍历矩阵，当遇到 $1$ 时，更新 $f[i][j][k]$ 的值。对于每个位置 $(i,j)$，我们只需要更新其四个方向的值即可。然后更新答案。

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

func longestLine(mat [][]int) (ans int) {
	m, n := len(mat), len(mat[0])
	f := make([][][4]int, m+2)
	for i := range f {
		f[i] = make([][4]int, n+2)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if mat[i-1][j-1] == 1 {
				f[i][j][0] = f[i-1][j][0] + 1
				f[i][j][1] = f[i][j-1][1] + 1
				f[i][j][2] = f[i-1][j-1][2] + 1
				f[i][j][3] = f[i-1][j+1][3] + 1
				for _, v := range f[i][j] {
					if ans < v {
						ans = v
					}
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

568. 最大休假天数 🔒

困难1 种解法

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

题目、示例与约束

力扣想让一个最优秀的员工在 N 个城市间旅行来收集算法问题。 但只工作不玩耍，聪明的孩子也会变傻，所以您可以在某些特定的城市和星期休假。您的工作就是安排旅行使得最大化你可以休假的天数，但是您需要遵守一些规则和限制。

规则和限制：

1. 您只能在 N 个城市之间旅行，用 0 到 n-1 的索引表示。一开始，您在索引为 0 的城市，并且那天是星期一。
2. 这些城市通过航班相连。这些航班用 n x n 矩阵 flights（不一定是对称的）表示，flights[i][j] 代表城市 i 到城市 j 的航空状态。如果没有城市 i 到城市 j 的航班，flights[i][j] = 0 ；否则，flights[i][j] = 1 。同时，对于所有的 i ，flights[i][i] = 0 。
3. 您总共有 k 周（每周7天）的时间旅行。您每天最多只能乘坐一次航班，并且只能在每周的星期一上午乘坐航班。由于飞行时间很短，我们不考虑飞行时间的影响。
4. 对于每个城市，不同的星期您休假天数是不同的，给定一个 N*K 矩阵 days 代表这种限制，days[i][j] 代表您在第j个星期在城市i能休假的最长天数。
5. 如果您从 A 市飞往 B 市，并在当天休假，扣除的假期天数将计入 B 市当周的休假天数。
6. 我们不考虑飞行时数对休假天数计算的影响。

给定 flights 矩阵和 days 矩阵，您需要输出 k 周内可以休假的最长天数。

 

示例 1:

输入:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
输出: 12
解释: 
最好的策略之一：
第一个星期 : 星期一从城市 0 飞到城市 1，玩 6 天，工作 1 天。 
（虽然你是从城市 0 开始，但因为是星期一，我们也可以飞到其他城市。） 
第二个星期 : 星期一从城市 1 飞到城市 2，玩 3 天，工作 4 天。
第三个星期 : 呆在城市 2，玩 3 天，工作 4 天。
Ans = 6 + 3 + 3 = 12. 

示例 2:

输入:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
输出: 3
解释: 
由于没有航班可以让您飞到其他城市，你必须在城市 0 呆整整 3 个星期。 
对于每一个星期，你只有一天时间玩，剩下六天都要工作。 
所以最大休假天数为 3.
Ans = 1 + 1 + 1 = 3. 

示例 3:

输入:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
输出: 21
解释:
最好的策略之一是：
第一个星期 : 呆在城市 0，玩 7 天。 
第二个星期 : 星期一从城市 0 飞到城市 1，玩 7 天。
第三个星期 : 星期一从城市 1 飞到城市 2，玩 7 天。
Ans = 7 + 7 + 7 = 21

 

提示:

• n == flights.length
• n == flights[i].length
• n == days.length
• k == days[i].length
• 1 <= n, k <= 100
• flights[i][j] 不是 0 就是 1
• 0 <= days[i] <= 7

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

思考

每周要待在一座城市休假，城市之间受航班约束（也可留在原地）。穷举每周选城是 $n^K$，在约束下过大。

$f[k][j]$ 表示前 $k$ 周且第 $k$ 周在城市 $j$ 的最长休假。从上一周的 $j$（留下）或有航班飞入的 $i$ 转移，再加 $days[j][k-1]$。起点只允许第 $0$ 周在城市 $0$。答案取最后一周所有城市的最大。

我们定义 $f[k][j]$ 表示前 $k$ 周，且最后一周在城市 $j$ 休假的最长天数。初始时 $f[0][0]=0$，其它 $f[0][j]=-\mathrm{\infty }$。答案为 $\underset{j=0}{\overset{n-1}{max}}f[K][j]$。

接下来，我们考虑如何计算 $f[k][j]$。对于当前这一周，我们可以枚举上一周所在的城市 $i$，城市 $i$ 可以和城市 $j$ 相等，那么 $f[k][j]=f[k-1][i]$；也可以和城市 $j$ 不相等，如果不相等，我们需要判断是否可以从城市 $i$ 飞到城市 $j$，如果可以，那么 $f[k][j]=max(f[k][j],f[k-1][i])$。最后，我们还需要加上这一周在城市 $j$ 休假的天数 $\mathit{\text{days}}[j][k-1]$。

最终的答案即为 $\underset{j=0}{\overset{n-1}{max}}f[K][j]$。

时间复杂度 $O(K\times n^2)$，空间复杂度 $O(K\times n)$。其中 $K$ 和 $n$ 分别为周数和城市数。

func maxVacationDays(flights [][]int, days [][]int) (ans int) {
	n, K := len(flights), len(days[0])
	f := make([][]int, K+1)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -(1 << 30)
		}
	}
	f[0][0] = 0
	for k := 1; k <= K; k++ {
		for j := 0; j < n; j++ {
			f[k][j] = f[k-1][j]
			for i := 0; i < n; i++ {
				if flights[i][j] == 1 {
					f[k][j] = max(f[k][j], f[k-1][i])
				}
			}
			f[k][j] += days[j][k-1]
		}
	}
	for j := 0; j < n; j++ {
		ans = max(ans, f[K][j])
	}
	return
}

力扣原题 · Doocs 题解来源

576. 出界的路径数

中等1 种解法

标签：动态规划

题目、示例与约束

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。

 

示例 1：

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6

示例 2：

输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
输出：12

 

提示：

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow < m
• 0 <= startColumn < n

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

思考

每步上下左右，最多 $k$ 步，统计走出网格的路径数。不记忆的搜索会重复同一格子与剩余步数。

$dfs(i,j,k)$ 表示在 $(i,j)$ 还剩 $k$ 步时的出界路径数。已出界且步数仍非负则计 $1$；步数用尽则计 $0$。四向转移并对 ${10}^9+7$ 取模。记忆化保证每个三元组只算一次。

我们定义一个函数 $\mathit{\text{dfs}}(i,j,k)$ 表示从坐标 $(i,j)$ 出发，还剩下 $k$ 步可以移动的情况下，可以移出边界的路径数量。

在函数 $\mathit{\text{dfs}}(i,j,k)$ 中，我们首先处理边界情况，如果当前坐标 $(i,j)$ 不在网格范围内，如果 $k\ge 0$，则返回 $1$，否则返回 $0$。如果 $k\le 0$，说明还在网格内，但是已经没有移动次数了，返回 $0$。接下来，我们遍历四个方向，移动到下一个坐标 $(x,y)$，然后递归调用 $\mathit{\text{dfs}}(x,y,k-1)$，并将结果累加到答案中。

在主函数中，我们调用 $\mathit{\text{dfs}}(startRow,startColumn,maxMove)$，即从起始坐标 $(\mathit{\text{startRow}},\mathit{\text{startColumn}})$ 出发，还剩下 $\mathit{\text{maxMove}}$ 步可以移动的情况下，可以移出边界的路径数量。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(m\times n\times k)$，空间复杂度 $O(m\times n\times k)$。其中 $m$ 和 $n$ 分别是网格的行数和列数，而 $k$ 是可以移动的步数，本题中 $k=\mathit{\text{maxMove}}\le 50$。

func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
	f := make([][][]int, m)
	for i := range f {
		f[i] = make([][]int, n)
		for j := range f[i] {
			f[i][j] = make([]int, maxMove+1)
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	const mod int = 1e9 + 7
	var dfs func(int, int, int) int
	dirs := [5]int{-1, 0, 1, 0, -1}
	dfs = func(i, j, k int) int {
		if i < 0 || i >= m || j < 0 || j >= n {
			if k >= 0 {
				return 1
			}
			return 0
		}
		if k <= 0 {
			return 0
		}
		if f[i][j][k] != -1 {
			return f[i][j][k]
		}
		ans := 0
		for d := 0; d < 4; d++ {
			x, y := i+dirs[d], j+dirs[d+1]
			ans = (ans + dfs(x, y, k-1)) % mod
		}
		f[i][j][k] = ans
		return ans
	}
	return dfs(startRow, startColumn, maxMove)
}

力扣原题 · Doocs 题解来源