LeetCode Go · 动态规划（5）

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

来源与许可

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

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

799. 香槟塔

中等2 种解法

标签：动态规划

题目、示例与约束

我们把玻璃杯摆成金字塔的形状，其中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯将盛有香槟。

从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）

例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。

现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（ i 和 j 都从0开始）。

 

示例 1:
输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.00000
解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。

示例 2:
输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.50000
解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。

示例 3:

输入: poured = 100000009, query_row = 33, query_glass = 17
输出: 1.00000

 

提示:

• 0 <= poured <= 109
• 0 <= query_glass <= query_row < 100

方法一：模拟 · Go 实现

思考

从塔顶倒 $poured$ 杯，求指定杯的容积（至多 $1$）。行数至多 $99$，按层模拟溢出。

一杯超过 $1$ 则多出的一半流向左下与右下。先填当前杯再下溢，查到目标行即可。

我们直接模拟倒香槟的过程。

定义一个二维数组 $f$，其中 $f[i][j]$ 表示第 $i$ 层第 $j$ 个玻璃杯中的香槟量。初始时 $f[0][0]=poured$。

对于每一层，如果当前杯子的香槟量 $f[i][j]$ 大于 $1$，香槟会流向下一层的两个杯子，流入的量为 $\frac{f[i][j]-1}{2}$，即当前杯子的香槟量减去 $1$ 后除以 $2$，然后当前杯子的香槟量更新为 $1$。

模拟结束，返回 $f[query\mathrm{\_}row][query\mathrm{\_}glass]$ 即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 为层数，即 $\text{query\_row}$。

func champagneTower(poured int, query_row int, query_glass int) float64 {
	f := [101][101]float64{}
	f[0][0] = float64(poured)
	for i := 0; i <= query_row; i++ {
		for j := 0; j <= i; j++ {
			if f[i][j] > 1 {
				half := (f[i][j] - 1) / 2.0
				f[i][j] = 1
				f[i+1][j] += half
				f[i+1][j+1] += half
			}
		}
	}
	return f[query_row][query_glass]
}

方法二：模拟（空间优化） · Go 实现

思考

第 $i$ 行只依赖第 $i-1$ 行，整表不必保留。一行滚动，溢出写入下一行数组。查询杯可能未满，与 $1$ 取最小。

由于每一层的香槟量只与上一层的香槟量有关，因此我们可以用滚动数组的方式优化空间复杂度，将二维数组优化为一维数组。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为层数，即 $\text{query\_row}$。

func champagneTower(poured int, query_row int, query_glass int) float64 {
	f := []float64{float64(poured)}
	for i := 1; i <= query_row; i++ {
		g := make([]float64, i+1)
		for j, v := range f {
			if v > 1 {
				half := (v - 1) / 2.0
				g[j] += half
				g[j+1] += half
			}
		}
		f = g
	}
	return math.Min(1, f[query_glass])
}

力扣原题 · Doocs 题解来源

801. 使序列递增的最小交换次数

困难1 种解法

标签：数组、动态规划

题目、示例与约束

我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。

• 例如，如果 nums1 = [1,2,3,8] ， nums2 =[5,6,7,4] ，你可以交换 i = 3 处的元素，得到 nums1 =[1,2,3,4] 和 nums2 =[5,6,7,8] 。

返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。

数组 arr 严格递增 且  arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。

注意：

• 用例保证可以实现操作。

 

示例 1:

输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
输出: 1
解释: 
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。

示例 2:

输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
输出: 1

 

提示:

• 2 <= nums1.length <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 2 * 105

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

思考

每个下标可选择交换或不交换，穷举全部 $2^n$ 方案在 $n\le {10}^5$ 时不可行。某一位置能否保持两条序列严格递增，只取决于它与前一位置在交换后的相对大小。

为此记录做到当前位置且「本位置不换 / 本位置交换」的最少次数。转移按与前一位是否已经递增、以及交叉后是否仍递增分情况讨论；转移只依赖上一位置的两个状态，滚动两个变量即可。

定义 $a$, $b$ 分别表示使得下标 $[0..i]$ 的元素序列严格递增，且第 $i$ 个元素不交换、交换的最小交换次数。下标从 $0$ 开始。

当 $i=0$ 时，有 $a=0$, $b=1$。

当 $i>0$ 时，我们先将此前 $a$, $b$ 的值保存在 $x$, $y$ 中，然后分情况讨论：

如果 $nums1[i-1]\ge nums1[i]$ 或者 $nums2[i-1]\ge nums2[i]$，为了使得两个序列均严格递增，下标 $i-1$ 和 $i$ 对应的元素的相对位置必须发生变化。也就是说，如果前一个位置交换了，那么当前位置不交换，因此有 $a=y$；如果前一个位置没有交换，那么当前位置必须交换，因此有 $b=x+1$。

否则，下标 $i-1$ 和 $i$ 对应的元素的相对位置可以不发生变化，那么有 $b=y+1$。另外，如果满足 $nums1[i-1]<nums2[i]$ 并且 $nums2[i-1]<nums1[i]$，那么下标 $i-1$ 和 $i$ 对应的元素的相对位置可以发生变化，此时 $a$ 和 $b$ 可以取较小值，因此有 $a=min(a,y)$ 和 $b=min(b,x+1)$。

最后，返回 $a$ 和 $b$ 中较小值即可。

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

func minSwap(nums1 []int, nums2 []int) int {
	a, b, n := 0, 1, len(nums1)
	for i := 1; i < n; i++ {
		x, y := a, b
		if nums1[i-1] >= nums1[i] || nums2[i-1] >= nums2[i] {
			a, b = y, x+1
		} else {
			b = y + 1
			if nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i] {
				a = min(a, y)
				b = min(b, x+1)
			}
		}
	}
	return min(a, b)
}

力扣原题 · Doocs 题解来源

805. 数组的均值分割

困难1 种解法

标签：位运算、数组、哈希表、数学、动态规划、位掩码、中途相遇

题目、示例与约束

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。

如果可以完成则返回true ， 否则返回 false  。

注意：对于数组 arr ,  average(arr) 是 arr 的所有元素的和除以 arr 长度。

 

示例 1:

输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

示例 2:

输入: nums = [3,1]
输出: false

 

提示:

• 1 <= nums.length <= 30
• 0 <= nums[i] <= 104

方法一：折半查找 + 二进制枚举 · Go 实现

思考

将数组分成两个非空子集且平均值相等，等价于存在大小为 $k$ 的子集其和为 $k\cdot \mathrm{avg}$。 $n\le 30$ 时 $2^n$ 枚举偏慢，但折半后每半约 $15$ 个数，二进制枚举可接受。

先把每个数变为 $n\cdot a_i-S$，则目标转化为「存在非空真子集其和为 $0$」。左半子集和放入集合，右半枚举时若自身为 $0$ 或相反数已在左半出现（且不是全集对全集），即可判定。

根据题目要求，要判断是否可以将数组 $\mathit{\text{nums}}$ 划分为两个子数组 $A$ 和 $B$，使得两个子数组的平均值相等。

我们记数组 $\mathit{\text{nums}}$ 的和为 $s$，元素个数为 $n$。子数组 $A$ 的和以及个数分别为 $s_1$ 和 $k$，那么子数组 $B$ 的和为 $s_2=s-s_1$，个数为 $n-k$，即：

$$\frac{s_1}{k}=\frac{s_2}{n-k}=\frac{s-s_1}{n-k}$$

整理可得：

$$s_1\times (n-k)=(s-s_1)\times k$$

化简可得：

$$\frac{s_1}{k}=\frac{s}{n}$$

也就是说，要我们找出一个子数组 $A$，使得其平均值等于数组 $\mathit{\text{nums}}$ 的平均值。我们考虑将数组 $\mathit{\text{nums}}$ 每个元素都减去数组 $\mathit{\text{nums}}$ 的平均值，这样问题就转化为了在数组 $\mathit{\text{nums}}$ 中找出一个子数组，使得其和为 $0$。

但是，数组 $\mathit{\text{nums}}$ 的平均值可能不是整数，浮点数计算可能存在精度问题，我们不妨将数组 $\mathit{\text{nums}}$ 中的每个元素都乘以 $n$，即 $nums[i]\leftarrow nums[i]\times n$，上述式子就变成：

$$\frac{s_1\times n}{k}=s$$

此时我们将数组 $\mathit{\text{nums}}$ 中每个元素都减去整数 $s$，题目就转化为：在数组 $nums$ 中找出一个子数组 $A$，使得其和为 $0$。

数组 $\mathit{\text{nums}}$ 的长度范围为 $[1,30]$，如果我们使用暴力枚举子数组的方法，时间复杂度为 $O(2^n)$，会超时。我们可以使用折半查找的方法，将时间复杂度降低到 $O(2^{n/2})$。

我们将数组 $\mathit{\text{nums}}$ 分成左右两部分，那么子数组 $A$ 可能存在三种情况：

1. 子数组 $A$ 完全在数组 $\mathit{\text{nums}}$ 的左半部分；
2. 子数组 $A$ 完全在数组 $\mathit{\text{nums}}$ 的右半部分；
3. 子数组 $A$ 一部分在数组 $\mathit{\text{nums}}$ 的左半部分，一部分在数组 $\mathit{\text{nums}}$ 的右半部分。

我们可以使用二进制枚举的方法，先枚举左半部分所有子数组的和，如果存在一个子数组和为 $0$，直接返回 true，否则我们将其存入哈希表 $\mathit{\text{vis}}$ 中；然后枚举右半部分所有子数组的和，如果存在一个子数组和为 $0$，直接返回 true，否则我们判断此时哈希表 $\mathit{\text{vis}}$ 中是否存在该和的相反数，如果存在，直接返回 true。

需要注意的是，我们不能同时全选左半部分和右半部分，因为这样会导致子数组 $B$ 为空，这是不符合题意的。在实现上，我们只需要考虑数组的 $n-1$ 个数。

时间复杂度 $O(n\times 2^{\frac{n}{2}})$，空间复杂度 $O(2^{\frac{n}{2}})$。

func splitArraySameAverage(nums []int) bool {
	n := len(nums)
	if n == 1 {
		return false
	}
	s := 0
	for _, v := range nums {
		s += v
	}
	for i, v := range nums {
		nums[i] = v*n - s
	}
	m := n >> 1
	vis := map[int]bool{}
	for i := 1; i < 1<<m; i++ {
		t := 0
		for j, v := range nums[:m] {
			if (i >> j & 1) == 1 {
				t += v
			}
		}
		if t == 0 {
			return true
		}
		vis[t] = true
	}
	for i := 1; i < 1<<(n-m); i++ {
		t := 0
		for j, v := range nums[m:] {
			if (i >> j & 1) == 1 {
				t += v
			}
		}
		if t == 0 || (i != (1<<(n-m))-1 && vis[-t]) {
			return true
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

808. 分汤

中等1 种解法

标签：数学、动态规划、概率与统计

题目、示例与约束

你有两种汤，A 和 B，每种初始为 n 毫升。在每一轮中，会随机选择以下四种操作中的一种，每种操作的概率为 0.25，且与之前的所有轮次 无关：

1. 从汤 A 取 100 毫升，从汤 B 取 0 毫升
2. 从汤 A 取 75 毫升，从汤 B 取 25 毫升
3. 从汤 A 取 50 毫升，从汤 B 取 50 毫升
4. 从汤 A 取 25 毫升，从汤 B 取 75 毫升

注意：

• 不存在从汤 A 取 0 ml 和从汤 B 取 100 ml 的操作。
• 汤 A 和 B 在每次操作中同时被取出。
• 如果一次操作要求你取出比剩余的汤更多的量，请取出该汤剩余的所有部分。

操作过程在任何回合中任一汤被取完后立即停止。

返回汤 A 在 B 前取完的概率，加上两种汤在 同一回合 取完概率的一半。返回值在正确答案 10-5 的范围内将被认为是正确的。

 

示例 1:

输入：n = 50
输出：0.62500
解释：
如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

示例 2:

输入：n = 100
输出：0.71875
解释：
如果我们选择第一个操作，A 首先将变为空。
如果我们选择第二个操作，A 将在执行操作 [1, 2, 3] 时变为空，然后 A 和 B 在执行操作 4 时同时变空。
如果我们选择第三个操作，A 将在执行操作 [1, 2] 时变为空，然后 A 和 B 在执行操作 3 时同时变空。
如果我们选择第四个操作，A 将在执行操作 1 时变为空，然后 A 和 B 在执行操作 2 时同时变空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.71875。

 

提示:

• 0 <= n <= 109

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

思考

四种操作等概率减少汤量，求 A 先倒完的概率（同时倒完计 $1/2$）。 $n$ 可达 ${10}^9$，按毫升逐步模拟不可行；注意到每次至少减少 $25\mathrm{ml}$，可把状态缩到 $\lceil n/25\rceil$ 的格点。

记忆化搜索 $dfs(i,j)$ 表示剩余 $(i,j)$ 份时的概率，边界按谁先耗尽返回 $1$、 $0$ 或 $1/2$。 $n$ 很大时 A 几乎必然先空，代码在 $n>4800$ 时直接返回 $1$，避免状态爆炸。

在这道题中，由于每次操作都是 $25$ 的倍数，因此，我们可以将每 $25ml$ 的汤视为一份。这样就能将数据规模缩小到 $\lceil \frac{n}{25}\rceil$。

我们设计一个函数 $dfs(i,j)$，表示当前剩余 $i$ 份汤 $A$ 和 $j$ 份汤 $B$ 的结果概率。

当 $i\le 0$ 并且 $j\le 0$ 时，表示两种汤都分配完了，此时应该返回 $0.5$；当 $i\le 0$ 时，表示汤 $A$ 先分配完了，此时应该返回 $1$；当 $j\le 0$ 时，表示汤 $B$ 先分配完了，此时应该返回 $0$。

接下来，对于每一次操作，我们都有四种选择，即：

• 从 $i$ 份汤 $A$ 中取出 $4$ 份，从 $j$ 份汤 $B$ 中取出 $0$ 份；
• 从 $i$ 份汤 $A$ 中取出 $3$ 份，从 $j$ 份汤 $B$ 中取出 $1$ 份；
• 从 $i$ 份汤 $A$ 中取出 $2$ 份，从 $j$ 份汤 $B$ 中取出 $2$ 份；
• 从 $i$ 份汤 $A$ 中取出 $1$ 份，从 $j$ 份汤 $B$ 中取出 $3$ 份；

每一种选择的概率都是 $0.25$，因此，我们可以得到：

$$dfs(i,j)=0.25\times (dfs(i-4,j)+dfs(i-3,j-1)+dfs(i-2,j-2)+dfs(i-1,j-3))$$

记忆化搜索即可。

另外，我们发现在 $n=4800$ 时，结果为 $0.999994994426$，而题目要求的精度为 ${10}^{-5}$，并且随着 $n$ 的增大，结果越来越接近 $1$，因此，当 $n>4800$ 时，直接返回 $1$ 即可。

时间复杂度 $O(C^2)$，空间复杂度 $O(C^2)$。本题中 $C=200$。

func soupServings(n int) float64 {
	if n > 4800 {
		return 1
	}
	f := [200][200]float64{}
	var dfs func(i, j int) float64
	dfs = func(i, j int) float64 {
		if i <= 0 && j <= 0 {
			return 0.5
		}
		if i <= 0 {
			return 1.0
		}
		if j <= 0 {
			return 0
		}
		if f[i][j] > 0 {
			return f[i][j]
		}
		ans := 0.25 * (dfs(i-4, j) + dfs(i-3, j-1) + dfs(i-2, j-2) + dfs(i-1, j-3))
		f[i][j] = ans
		return ans
	}
	return dfs((n+24)/25, (n+24)/25)
}

力扣原题 · Doocs 题解来源

813. 最大平均值和的分组

中等2 种解法

标签：数组、动态规划、前缀和

题目、示例与约束

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个非空子数组，且数组内部是连续的 。 分数 由每个子数组内的平均值的总和构成。

注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。

返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。

 

示例 1:

输入: nums = [9,1,2,3,9], k = 3
输出: 20.00000
解释: 
nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20. 
我们也可以把 nums 分成[9, 1], [2], [3, 9]. 
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.

示例 2:

输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000

 

提示:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 104
• 1 <= k <= nums.length

方法一：前缀和 + 记忆化搜索 · Go 实现

思考

把数组分成至多 $k$ 段、最大化各段平均值之和。段的分界未知，朴素子集划分过多； $n,k\le 100$，按「从 $i$ 起还剩 $k$ 段」搜索并记忆化即可。

前缀和使一段 $[i,j)$ 的平均值 $O(1)$ 可得。 $k=1$ 时整段只能作为最后一组；否则枚举第一段右端，递归剩余。

我们可以先预处理得到前缀和数组 $s$，方便快速得到子数组的和。

接下来，我们设计一个函数 $\mathit{\text{dfs}}(i,k)$，表示从数组下标 $i$ 开始，最多分成 $k$ 组的最大平均值和。答案为 $\mathit{\text{dfs}}(0,k)$。

函数 $\mathit{\text{dfs}}(i,k)$ 的执行逻辑如下：

当 $i=n$ 时，表示已经遍历到数组末尾，此时返回 $0$。

当 $k=1$ 时，表示只剩下一组，此时返回从下标 $i$ 开始到数组末尾的平均值。

否则，我们在 $[i+1,n)$ 的区间内枚举下一个分组的开始位置 $j$，计算从 $i$ 到 $j-1$ 的平均值 $\frac{s[j]-s[i]}{j-i}$，加上 $\mathit{\text{dfs}}(j,k-1)$ 的结果，取所有结果的最大值。

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

func largestSumOfAverages(nums []int, k int) float64 {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	f := make([][]float64, n)
	for i := range f {
		f[i] = make([]float64, k+1)
	}
	var dfs func(int, int) float64
	dfs = func(i, k int) float64 {
		if i == n {
			return 0
		}
		if f[i][k] > 0 {
			return f[i][k]
		}
		if k == 1 {
			return float64(s[n]-s[i]) / float64(n-i)
		}
		ans := 0.0
		for j := i + 1; j < n; j++ {
			ans = math.Max(ans, float64(s[j]-s[i])/float64(j-i)+dfs(j, k-1))
		}
		f[i][k] = ans
		return ans
	}
	return dfs(0, k)
}

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

思考

记忆化搜索的递归深度与枚举顺序可以改写成递推，去掉递归常数。 $f[i][j]$ 表示前 $i$ 个数分成 $j$ 组的最大平均值和，内层枚举上一组分界 $h$。

边界 $f[i][1]$ 即前 $i$ 个数的平均值。答案为 $f[n][k]$，复杂度同为 $O(n^{2}k)$。

我们可以将方法一的记忆化搜索转化为动态规划。

定义 $f[i][j]$ 表示数组 $\mathit{\text{nums}}$ 的前 $i$ 个元素最多分成 $j$ 组的最大平均值和。答案为 $f[n][k]$。

对于 $f[i][j]$，我们可以枚举上一组的结束位置 $h$，计算 $f[h][j-1]$，加上 $\frac{s[i]-s[h]}{i-h}$ 的结果，取所有结果的最大值。

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

func largestSumOfAverages(nums []int, k int) float64 {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	f := make([][]float64, n+1)
	for i := range f {
		f[i] = make([]float64, k+1)
	}
	for i := 1; i <= n; i++ {
		f[i][1] = float64(s[i]) / float64(i)
		for j := 2; j <= min(i, k); j++ {
			for h := 0; h < i; h++ {
				f[i][j] = max(f[i][j], f[h][j-1]+float64(s[i]-s[h])/float64(i-h))
			}
		}
	}
	return f[n][k]
}

力扣原题 · Doocs 题解来源

818. 赛车

困难1 种解法

标签：动态规划、A* 搜索

题目、示例与约束

你的赛车可以从位置 0 开始，并且速度为 +1 ，在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 'A' 和倒车指令 'R' 组成的指令序列自动行驶。

• 当收到指令 'A' 时，赛车这样行驶：
  • position += speed
  • speed *= 2
• 当收到指令 'R' 时，赛车这样行驶：
  • 如果速度为正数，那么speed = -1
  • 否则 speed = 1
  当前所处位置不变。

例如，在执行指令 "AAR" 后，赛车位置变化为 0 --> 1 --> 3 --> 3 ，速度变化为 1 --> 2 --> 4 --> -1 。

给你一个目标位置 target ，返回能到达目标位置的最短指令序列的长度。

 

示例 1：

输入：target = 3
输出：2
解释：
最短指令序列是 "AA" 。
位置变化 0 --> 1 --> 3 。

示例 2：

输入：target = 6
输出：5
解释：
最短指令序列是 "AAARA" 。
位置变化 0 --> 1 --> 3 --> 7 --> 7 --> 6 。

 

提示：

• 1 <= target <= 104

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

思考

指令序列对应在数轴上加速或掉头，目标位置可达 ${10}^4$，直接 BFS 状态（位置、速度）偏多。注意到连续 $k$ 次 A 到达 $2^k-1$，任何目标都可由「越过再回头」或「中途回头再加速」拼成。

令 $dp[i]$ 为到达位置 $i$ 的最少指令。若 $i=2^k-1$ 则恰好 $k$ 次 A；否则比较「冲到 $2^k-1$ 再回头」以及在第 $k-1$ 次加速后提前回头走 $j$ 步再折返的代价，取最小。

设 $dp[i]$ 表示到达位置 $i$ 的最短指令序列的长度。答案为 $dp[target]$。

对于任意位置 $i$，都有 $2^{k-1}\le i<2^k$，并且我们可以有三种方式到达位置 $i$：

• 如果 $i$ 等于 $2^k-1$，那么我们可以直接执行 $k$ 个 A 指令到达位置 $i$，此时 $dp[i]=k$；
• 否则，我们可以先执行 $k$ 个 A 指令到达位置 $2^k-1$，然后执行 R 指令，剩余距离为 $2^k-1-i$，此时 $dp[i]=dp[2^k-1-i]+k+1$；我们也可以先执行 $k-1$ 个 A 指令到达位置 $2^{k-1}-1$，然后执行 R 指令，接着执行 $j$（其中 $0\le j<k$） 个 A，再执行 R，剩余距离为 $i-2^{k-1}+2^j$，此时 $dp[i]=dp[i-2^{k-1}+2^j]+k-1+j+2$。求出 $dp[i]$ 的最小值即可。

时间复杂度 $O(n\log n)$，其中 $n$ 为 $target$。

func racecar(target int) int {
	dp := make([]int, target+1)
	for i := 1; i <= target; i++ {
		k := bits.Len(uint(i))
		if i == (1<<k)-1 {
			dp[i] = k
			continue
		}
		dp[i] = dp[(1<<k)-1-i] + k + 1
		for j := 0; j < k; j++ {
			dp[i] = min(dp[i], dp[i-(1<<(k-1))+(1<<j)]+k-1+j+2)
		}
	}
	return dp[target]
}

力扣原题 · Doocs 题解来源

823. 带因子的二叉树

中等1 种解法

标签：数组、哈希表、动态规划、排序

题目、示例与约束

给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。

用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。

 

示例 1:

输入: arr = [2, 4]
输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]

示例 2:

输入: arr = [2, 4, 5, 10]
输出: 7
解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

 

提示：

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 109
• arr 中的所有值 互不相同

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

思考

以数组中的数为结点、且孩子之积等于父结点，统计可构成的带标号二叉树。数组长度 $\le 1000$，值互不相同，应按值从小到大构造，以便孩子先于父亲算完。

令 $f[i]$ 为以 $arr[i]$ 为根的方案数，枚举左孩子 $b$，若 $a/b$ 也在数组中则累加 $f[b]\cdot f[c]$。每个结点至少有一种单结点树，最后对 $f$ 求和取模。

我们可以枚举 $arr$ 中的每一个数 $a$ 作为二叉树的根节点（根节点一定最大），然后枚举枚举左子树的值 $b$，若 $a$ 能被 $b$ 整除，则右子树的值为 $a/b$，若 $a/b$ 也在 $arr$ 中，则可以构成一棵二叉树。此时，以 $a$ 为根节点的二叉树的个数为 $f(a)=f(b)\times f(a/b)$，其中 $f(b)$ 和 $f(a/b)$ 分别为左子树和右子树的二叉树个数。

因此，我们先将 $arr$ 排序，然后用 $f[i]$ 表示以 $arr[i]$ 为根节点的二叉树的个数，最终答案即为 $f[0]+f[1]+\cdots +f[n-1]$。注意答案可能很大，需要对 ${10}^9+7$ 取模。

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

func numFactoredBinaryTrees(arr []int) int {
	const mod int = 1e9 + 7
	sort.Ints(arr)
	f := make([]int, len(arr))
	idx := map[int]int{}
	for i, v := range arr {
		f[i] = 1
		idx[v] = i
	}
	for i, a := range arr {
		for j := 0; j < i; j++ {
			b := arr[j]
			if c := a / b; a%b == 0 {
				if k, ok := idx[c]; ok {
					f[i] = (f[i] + f[j]*f[k]) % mod
				}
			}
		}
	}
	ans := 0
	for _, v := range f {
		ans = (ans + v) % mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

828. 统计子串中的唯一字符

困难1 种解法

标签：哈希表、字符串、动态规划

题目、示例与约束

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

 

示例 1：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2：

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

示例 3：

输入：s = "LEETCODE"
输出：92

 

提示：

• 1 <= s.length <= 105
• s 只包含大写英文字符

方法一：计算每个字符的贡献 · Go 实现

思考

子串数量达 $O(n^2)$， $n\le {10}^5$ 时不能枚举。一个字符在某个子串中「唯一」当且仅当该子串覆盖它、且不覆盖同字母的相邻两次出现。

对每种字母记下出现下标，两端补哨兵。第 $i$ 次出现可与左侧空档、右侧空档独立组合，贡献为相邻间隔之积。对所有字母求和。

对于字符串 $s$ 的每个字符 $c_i$，当它在某个子字符串中仅出现一次时，它会对这个子字符串统计唯一字符时有贡献。

因此，我们只需要对每个字符 $c_i$，计算有多少子字符串仅包含该字符一次即可。

我们用一个哈希表或者长度为 $26$ 的数组 $d$，按照下标顺序存储每个字符在 $s$ 中所有出现的位置。

对于每个字符 $c_i$，我们遍历 $d[c_i]$ 中的每个位置 $p$，找出左侧相邻的位置 $l$ 和右侧相邻的位置 $r$，那么从位置 $p$ 向左右两边扩散，满足要求的子字符串的数量就是 $(p-l)\times (r-p)$。我们对每个字符都进行这样的操作，累加所有字符的贡献，即可得到答案。

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

func uniqueLetterString(s string) (ans int) {
	d := make([][]int, 26)
	for i := range d {
		d[i] = []int{-1}
	}
	for i, c := range s {
		d[c-'A'] = append(d[c-'A'], i)
	}
	for _, v := range d {
		v = append(v, len(s))
		for i := 1; i < len(v)-1; i++ {
			ans += (v[i] - v[i-1]) * (v[i+1] - v[i])
		}
	}
	return
}

力扣原题 · Doocs 题解来源

837. 新 21 点

中等3 种解法

标签：数学、动态规划、滑动窗口、概率与统计

题目、示例与约束

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。

爱丽丝的分数不超过 n 的概率是多少？

与实际答案误差不超过 10-5 的答案将被视为正确答案。

 

示例 1：

输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张牌，然后停止。

示例 2：

输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。

示例 3：

输入：n = 21, k = 17, maxPts = 10
输出：0.73278

 

提示：

• 0 <= k <= n <= 104
• 1 <= maxPts <= 104

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

思考

从 $0$ 开始每次均匀加 $[1,\mathit{\text{maxPts}}]$，达到 $k$ 停止，求点数不超过 $n$ 的概率。 $k,n\le {10}^4$，按每次抽牌展开博弈树不可行，应对「当前点数」做记忆化。

$dfs(i)$ 为已有 $i$ 点时的成功概率。 $i\ge k$ 时停止并按是否 $\le n$ 返回； $i=k-1$ 可闭式算出。其余用相邻状态的差分把转移从 $O(\mathit{\text{maxPts}})$ 降到 $O(1)$。

我们设计一个函数 $dfs(i)$，表示当前分数为 $i$ 时，到最终停止抽取数字时，分数不超过 $n$ 的概率。那么答案就是 $dfs(0)$。

函数 $dfs(i)$ 的计算方法如下：

• 如果 $i\ge k$，那么停止抽取数字，如果 $i\le n$，返回 $1$，否则返回 $0$；
• 否则，可以在 $[1,..\mathit{\text{maxPts}}]$ 范围内抽取下一个数字 $j$，那么 $dfs(i)=\frac{1}{maxPts}\sum _{j=1}^{maxPts}dfs(i+j)$。

这里我们可以使用记忆化搜索来加速计算。

以上方法的时间复杂度为 $O(k\times \mathit{\text{maxPts}})$，会超出时间限制，我们需要优化一下。

当 $i<k$ 时，以下等式成立：

$$\begin{array}{rlr}dfs(i)& =(dfs(i+1)+dfs(i+2)+\cdots +dfs(i+\mathit{\text{maxPts}}))/& (1)\end{array}$$

当 $i<k-1$ 时，以下等式成立：

$$\begin{array}{rlr}dfs(i+1)& =(dfs(i+2)+dfs(i+3)+\cdots +dfs(i+\mathit{\text{maxPts}}+1))/\mathit{\text{maxPts}}& (2)\end{array}$$

因此，当 $i<k-1$ 时，我们将等式 $(1)$ 减去等式 $(2)$，得到：

$$\begin{array}{rl}dfs(i)-dfs(i+1)& =(dfs(i+1)-dfs(i+\mathit{\text{maxPts}}+1))/\mathit{\text{maxPts}}\end{array}$$

即：

$$\begin{array}{rl}dfs(i)& =dfs(i+1)+(dfs(i+1)-dfs(i+\mathit{\text{maxPts}}+1))/\mathit{\text{maxPts}}\end{array}$$

如果 $i=k-1$，有：

$$\begin{array}{rlrl}dfs(i)& =dfs(k-1)& =dfs(k)+dfs(k+1)+\cdots +dfs(k+\mathit{\text{maxPts}}-1)/\mathit{\text{maxPts}}& (3)\end{array}$$

我们假设有 $i$ 个数不超过 $n$，那么 $k+i-1\le n$，又因为 $i\le \mathit{\text{maxPts}}$，所以 $i\le min(n-k+1,\mathit{\text{maxPts}})$，因此等式 $(3)$ 可以写成：

$$\begin{array}{rl}dfs(k-1)& =min(n-k+1,\mathit{\text{maxPts}})/\mathit{\text{maxPts}}\end{array}$$

综上所述，有以下状态转移方程：

$$\begin{array}{rl}dfs(i)& =\{\begin{array}{ll}1,& i\ge k,i\le n\\ 0,& i\ge k,i>n\\ min(n-k+1,\mathit{\text{maxPts}})/\mathit{\text{maxPts}},& i=k-1\\ dfs(i+1)+(dfs(i+1)-dfs(i+\mathit{\text{maxPts}}+1))/\mathit{\text{maxPts}},& i<k-1\end{array}\end{array}$$

时间复杂度 $O(k+\mathit{\text{maxPts}})$，空间复杂度 $O(k+\mathit{\text{maxPts}})$。其中 $k$ 为最大分数。

func new21Game(n int, k int, maxPts int) float64 {
	f := make([]float64, k)
	var dfs func(int) float64
	dfs = func(i int) float64 {
		if i >= k {
			if i <= n {
				return 1
			}
			return 0
		}
		if i == k-1 {
			return float64(min(n-k+1, maxPts)) / float64(maxPts)
		}
		if f[i] > 0 {
			return f[i]
		}
		f[i] = dfs(i+1) + (dfs(i+1)-dfs(i+maxPts+1))/float64(maxPts)
		return f[i]
	}
	return dfs(0)
}

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

思考

方法一已经从高分往低分填好这张表。同一转移是： $f[i]$ 由 $f[i+1]$ 与窗口右端 $f[i+\mathit{\text{maxPts}}+1]$ 推出。

$[k,min(n,k+\mathit{\text{maxPts}}))$ 的终止态为 $1$，其余为 $0$。答案为 $f[0]$，时间仍是线性的。

方法一已经按上述转移填表。下面直接写出同一组递推。

定义 $f[i]$ 表示当前分数为 $i$ 时，到最终停止抽取数字时，分数不超过 $n$ 的概率。那么答案就是 $f[0]$。

当 $k\le i\le min(n,k+\mathit{\text{maxPts}}-1)$ 时，有 $f[i]=1$。

当 $i=k-1$ 时，有 $f[i]=min(n-k+1,\mathit{\text{maxPts}})/\mathit{\text{maxPts}}$。

当 $i<k-1$ 时，有 $f[i]=f[i+1]+(f[i+1]-f[i+\mathit{\text{maxPts}}+1])/\mathit{\text{maxPts}}$。

时间复杂度 $O(k+\mathit{\text{maxPts}})$，空间复杂度 $O(k+\mathit{\text{maxPts}})$。其中 $k$ 为最大分数。

func new21Game(n int, k int, maxPts int) float64 {
	if k == 0 {
		return 1
	}
	f := make([]float64, k+maxPts)
	for i := k; i < min(n+1, k+maxPts); i++ {
		f[i] = 1
	}
	f[k-1] = float64(min(n-k+1, maxPts)) / float64(maxPts)
	for i := k - 2; i >= 0; i-- {
		f[i] = f[i+1] + (f[i+1]-f[i+maxPts+1])/float64(maxPts)
	}
	return f[0]
}

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

思考

从 $0$ 开始每次均匀加 $[1,\mathit{\text{maxPts}}]$，达到 $k$ 停止，求点数不超过 $n$ 的概率。 $k$ 可达 ${10}^4$，按每次抽牌展开不可行。

差分之后，除了闭式的 $k-1$，每个状态都先访问更大的分数。从 $0$ 走到 $k$ 的调用链长度为 $k$，栈会溢出。

更大的分数在从高往低填时已经就绪。令 $f[i]$ 为当前点数 $i$ 的成功概率，终止区间先写成 $1$，再从 $k-2$ 填到 $0$。

令 $f[i]$ 表示当前分数为 $i$ 时，到最终停止抽取数字时，分数不超过 $n$ 的概率。答案为 $f[0]$。

$f[i]$ 的取值如下：

• 如果 $i\ge k$，那么停止抽取数字，如果 $i\le n$，则为 $1$，否则为 $0$；
• 否则，可以在 $[1,..\mathit{\text{maxPts}}]$ 范围内抽取下一个数字 $j$，那么 $f[i]=\frac{1}{maxPts}\sum _{j=1}^{maxPts}f[i+j]$。

每个状态只依赖更大的分数，因此从 $k-2$ 填到 $0$。当 $k=0$ 时尚未抽牌，答案为 $1$。

以上方法的时间复杂度为 $O(k\times \mathit{\text{maxPts}})$，会超出时间限制，我们需要优化一下。

当 $i<k$ 时，以下等式成立：

$$\begin{array}{rlr}f[i]& =(f[i+1]+f[i+2]+\cdots +f[i+\mathit{\text{maxPts}}])/& (1)\end{array}$$

当 $i<k-1$ 时，以下等式成立：

$$\begin{array}{rlr}f[i+1]& =(f[i+2]+f[i+3]+\cdots +f[i+\mathit{\text{maxPts}}+1])/\mathit{\text{maxPts}}& (2)\end{array}$$

因此，当 $i<k-1$ 时，我们将等式 $(1)$ 减去等式 $(2)$，得到：

$$\begin{array}{rl}f[i]-f[i+1]& =(f[i+1]-f[i+\mathit{\text{maxPts}}+1])/\mathit{\text{maxPts}}\end{array}$$

即：

$$\begin{array}{rl}f[i]& =f[i+1]+(f[i+1]-f[i+\mathit{\text{maxPts}}+1])/\mathit{\text{maxPts}}\end{array}$$

如果 $i=k-1$，有：

$$\begin{array}{rlrl}f[i]& =f[k-1]& =f[k]+f[k+1]+\cdots +f[k+\mathit{\text{maxPts}}-1]/\mathit{\text{maxPts}}& (3)\end{array}$$

我们假设有 $i$ 个数不超过 $n$，那么 $k+i-1\le n$，又因为 $i\le \mathit{\text{maxPts}}$，所以 $i\le min(n-k+1,\mathit{\text{maxPts}})$，因此等式 $(3)$ 可以写成：

$$\begin{array}{rl}f[k-1]& =min(n-k+1,\mathit{\text{maxPts}})/\mathit{\text{maxPts}}\end{array}$$

综上所述，有以下状态转移方程：

$$\begin{array}{rl}f[i]& =\{\begin{array}{ll}1,& i\ge k,i\le n\\ 0,& i\ge k,i>n\\ min(n-k+1,\mathit{\text{maxPts}})/\mathit{\text{maxPts}},& i=k-1\\ f[i+1]+(f[i+1]-f[i+\mathit{\text{maxPts}}+1])/\mathit{\text{maxPts}},& i<k-1\end{array}\end{array}$$

时间复杂度 $O(k+\mathit{\text{maxPts}})$，空间复杂度 $O(k+\mathit{\text{maxPts}})$。其中 $k$ 为最大分数。

func new21Game(n int, k int, maxPts int) float64 {
	if k == 0 {
		return 1
	}
	f := make([]float64, k+maxPts)
	for i := k; i < min(n+1, k+maxPts); i++ {
		f[i] = 1
	}
	f[k-1] = float64(min(n-k+1, maxPts)) / float64(maxPts)
	for i := k - 2; i >= 0; i-- {
		f[i] = f[i+1] + (f[i+1]-f[i+maxPts+1])/float64(maxPts)
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

838. 推多米诺

中等1 种解法

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

题目、示例与约束

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

• dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
• dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
• dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。

返回表示最终状态的字符串。

 

示例 1：

输入：dominoes = "RR.L"
输出："RR.L"
解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：

输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

 

提示：

• n == dominoes.length
• 1 <= n <= 105
• dominoes[i] 为 'L'、'R' 或 '.'

方法一：多源  BFS · Go 实现

思考

多米诺同时向左右倒，相向作用会抵消。 $n\le {10}^5$，模拟每一秒全体倾倒偏慢。力从已倒下的牌向外传播，等价于多源 BFS。

初始所有 $L$、 $R$ 入队。某格只在同一时刻收到一种力才倒下；同时收到左右力则保持竖直。按时间分层扩展即可得到最终状态。

把所有初始受到推力的骨牌（L  或  R）视作 源点，它们会同时向外扩散各自的力。用队列按时间层级（0, 1, 2 …）进行  BFS：

我们定义 $\text{time[i]}$  记录第  i  张骨牌第一次受力的时刻，-1  表示尚未受力，定义 $\text{force[i]}$  是一个长度可变的列表，存放该骨牌在同一时刻收到的方向（'L'、'R'）。初始时把所有  L/R  的下标压入队列，并将它们的时间置  0。

当弹出下标  i 时，若  $\text{force[i]}$  只有一个方向，骨牌就会倒向该方向  $f$。设下一张骨牌下标为

$$j=\{\begin{array}{ll}i-1,& f=L,\\ i+1,& f=R.\end{array}$$

若  $0\le j<n$：

• 若 $\text{time[j]}=-1$，说明  j  从未受力，记录 $\text{time[j]}=\text{time[i]}+1$ 并入队，同时把  $f$ 写入  $\text{force[j]}$。
• 若 $\text{time[j]}=\text{time[i]}+1$，说明它在同一“下一刻”已受过另一股力，此时只把  $f$ 追加到  $\text{force[j]}$，形成对冲；后续因  len(force[j])==2，它将保持竖直。

队列清空后，所有  $\text{force[i]}$  长度为  1  的位置倒向对应方向；长度为  2  的位置保持  .。最终将字符数组拼接为答案。

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

func pushDominoes(dominoes string) string {
	n := len(dominoes)
	q := []int{}
	time := make([]int, n)
	for i := range time {
		time[i] = -1
	}
	force := make([][]byte, n)
	for i, c := range dominoes {
		if c != '.' {
			q = append(q, i)
			time[i] = 0
			force[i] = append(force[i], byte(c))
		}
	}

	ans := bytes.Repeat([]byte{'.'}, n)
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		if len(force[i]) > 1 {
			continue
		}
		f := force[i][0]
		ans[i] = f
		j := i - 1
		if f == 'R' {
			j = i + 1
		}
		if 0 <= j && j < n {
			t := time[i]
			if time[j] == -1 {
				q = append(q, j)
				time[j] = t + 1
				force[j] = append(force[j], f)
			} else if time[j] == t+1 {
				force[j] = append(force[j], f)
			}
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

845. 数组中的最长山脉

中等2 种解法

标签：数组、双指针、动态规划、枚举

题目、示例与约束

把符合下列属性的数组 arr 称为 山脉数组 ：

• arr.length >= 3
• 存在下标 i（0 < i < arr.length - 1），满足
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

 

示例 1：

输入：arr = [2,1,4,7,3,2,5]
输出：5
解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。

示例 2：

输入：arr = [2,2,2]
输出：0
解释：不存在山脉子数组。

 

提示：

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 104

 

进阶：

• 你可以仅用一趟扫描解决此问题吗？
• 你可以用 O(1) 空间解决此问题吗？

方法一：预处理 + 枚举 · Go 实现

思考

山形子数组先严格上升再严格下降，长度至少为 $3$。 $n\le {10}^4$，枚举峰并分别向两侧扩展可行，但会重复走同一段坡。

预处理 $f[i]$ 为以 $i$ 结尾的最长上升长度， $g[i]$ 为以 $i$ 开头的最长下降长度。仅当两侧都大于 $1$ 时， $f[i]+g[i]-1$ 才是一座山。

我们定义两个数组 $f$ 和 $g$，其中 $f[i]$ 表示以 $arr[i]$ 结尾的最长上升子序列的长度，而 $g[i]$ 表示以 $arr[i]$ 开头的最长下降子序列的长度。那么对于每个下标 $i$，如果 $f[i]>1$ 且 $g[i]>1$，那么以 $arr[i]$ 为山顶的山脉的长度为 $f[i]+g[i]-1$，我们只需要枚举所有的 $i$，找出最大的那个值即可。

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

func longestMountain(arr []int) (ans int) {
	n := len(arr)
	f := make([]int, n)
	g := make([]int, n)
	for i := range f {
		f[i] = 1
		g[i] = 1
	}
	for i := 1; i < n; i++ {
		if arr[i] > arr[i-1] {
			f[i] = f[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if arr[i] > arr[i+1] {
			g[i] = g[i+1] + 1
			if f[i] > 1 {
				ans = max(ans, f[i]+g[i]-1)
			}
		}
	}
	return
}

方法二：一次遍历（枚举左侧山脚） · Go 实现

思考

两个辅助数组可以省掉。从左山脚出发一次扫描：先爬升到峰，再下降到右山脚，用区间长度更新答案，然后把左指针移到当前右端。

无法形成峰的位置直接前进。整段数组每个元素至多被左右指针各经过常数次。

我们可以枚举山脉的左侧山脚，然后向右寻找山脉的右侧山脚。我们可以使用两个指针 $l$ 和 $r$，其中 $l$ 表示左侧山脚的下标， $r$ 表示右侧山脚的下标，初始时 $l=0$,$r=0$，然后我们向右移动 $r$，找到山顶的位置，此时判断 $r$ 是否满足 $r+1<n$ 并且 $arr[r]>arr[r+1]$，如果满足，我们向右继续移动 $r$，直到找到右侧山脚的位置，此时山脉的长度为 $r-l+1$，我们更新答案，然后将 $l$ 的值更新为 $r$，继续寻找下一个山脉。

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

func longestMountain(arr []int) (ans int) {
	n := len(arr)
	for l, r := 0, 0; l+2 < n; l = r {
		r = l + 1
		if arr[l] < arr[r] {
			for r+1 < n && arr[r] < arr[r+1] {
				r++
			}
			if r+1 < n && arr[r] > arr[r+1] {
				for r+1 < n && arr[r] > arr[r+1] {
					r++
				}
				ans = max(ans, r-l+1)
			} else {
				r++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

871. 最低加油次数

困难1 种解法

标签：贪心、数组、动态规划、堆（优先队列）

题目、示例与约束

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

 

示例 1：

输入：target = 1, startFuel = 1, stations = []
输出：0
解释：可以在不加油的情况下到达目的地。

示例 2：

输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：无法抵达目的地，甚至无法到达第一个加油站。

示例 3：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠，所以返回 2 。

 

提示：

• 1 <= target, startFuel <= 109
• 0 <= stations.length <= 500
• 1 <= positioni < positioni+1 < target
• 1 <= fueli < 109

方法一：贪心 + 优先队列（大根堆） · Go 实现

思考

在加油站选择加油使到达终点的次数最少。 $target$ 很大而站数 $\le 500$，枚举加油子集可行但偏慢。关键是：走到下一站时若油不够，应补加「已经路过且油量最大」的站。

按位置扫描，把经过的油量放入大根堆；油箱为负就从堆中取出最大油量。堆空仍为负则不可达。终点当作最后一个站。

我们可以利用优先队列（大根堆） $\mathit{\text{pq}}$ 记录所有已经到达过的加油站的加油量，每次当油量不足时，贪心地取出最大加油量，即 $\mathit{\text{pq}}$ 的堆顶元素，并累计加油次数 $\mathit{\text{ans}}$。如果 $\mathit{\text{pq}}$ 为空并且当前油量仍然不足，说明无法到达目的地，返回 $-1$。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 表示加油站的数量。

func minRefuelStops(target int, startFuel int, stations [][]int) int {
	pq := &hp{}
	ans, pre := 0, 0
	stations = append(stations, []int{target, 0})
	for _, station := range stations {
		pos, fuel := station[0], station[1]
		dist := pos - pre
		startFuel -= dist
		for startFuel < 0 && pq.Len() > 0 {
			startFuel += heap.Pop(pq).(int)
			ans++
		}
		if startFuel < 0 {
			return -1
		}
		heap.Push(pq, fuel)
		pre = pos
	}
	return ans
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
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
}

力扣原题 · Doocs 题解来源

873. 最长的斐波那契子序列的长度

中等1 种解法

标签：数组、哈希表、动态规划

题目、示例与约束

如果序列 x1, x2, ..., xn 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 xi + xi+1 == xi+2

给定一个 严格递增 的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果不存在，返回  0 。

子序列 是通过从另一个序列 arr 中删除任意数量的元素（包括删除 0 个元素）得到的，同时不改变剩余元素顺序。例如，[3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的子序列。

 

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

 

提示：

• 3 <= arr.length <= 1000

• 1 <= arr[i] < arr[i + 1] <= 109

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

思考

在严格递增数组中找最长斐波那契子序列。 $n\le 1000$，枚举前两项再向后跳可行，但对同一对结尾会重复。

令 $f[i][j]$ 为以 $arr[j],arr[i]$ 结尾的最长长度。若 $arr[i]-arr[j]$ 出现在 $j$ 之前，则可接在那对后面。长度至少为 $3$ 才更新答案。

我们定义 $f[i][j]$ 表示以 $\mathit{\text{arr}}[i]$ 作为最后一个元素，以 $\mathit{\text{arr}}[j]$ 作为倒数第二个元素的最长斐波那契子序列的长度。初始时，对于任意的 $i\in [0,n)$ 和 $j\in [0,i)$，都有 $f[i][j]=2$。其余的元素都是 $0$。

我们用一个哈希表 $d$ 记录数组 $\mathit{\text{arr}}$ 中每个元素对应的下标。

然后，我们可以枚举 $\mathit{\text{arr}}[i]$ 和 $\mathit{\text{arr}}[j]$，其中 $i\in [2,n)$ 且 $j\in [1,i)$。假设当前枚举到的元素是 $\mathit{\text{arr}}[i]$ 和 $\mathit{\text{arr}}[j]$，我们可以得到 $\mathit{\text{arr}}[i]-\mathit{\text{arr}}[j]$，记作 $t$。如果 $t$ 在数组 $\mathit{\text{arr}}$ 中，且 $t$ 的下标 $k$ 满足 $k<j$，那么我们可以得到一个以 $\mathit{\text{arr}}[j]$ 和 $\mathit{\text{arr}}[i]$ 作为最后两个元素的斐波那契子序列，其长度为 $f[i][j]=max(f[i][j],f[j][k]+1)$。我们可以用这种方法不断更新 $f[i][j]$ 的值，然后更新答案。

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

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

func lenLongestFibSubseq(arr []int) (ans int) {
	n := len(arr)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
	}

	d := make(map[int]int)
	for i, x := range arr {
		d[x] = i
		for j := 0; j < i; j++ {
			f[i][j] = 2
		}
	}

	for i := 2; i < n; i++ {
		for j := 1; j < i; j++ {
			t := arr[i] - arr[j]
			if k, ok := d[t]; ok && k < j {
				f[i][j] = max(f[i][j], f[j][k]+1)
				ans = max(ans, f[i][j])
			}
		}
	}

	return
}

力扣原题 · Doocs 题解来源

877. 石子游戏

中等2 种解法

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

题目、示例与约束

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

 

示例 1：

输入：piles = [5,3,4,5]
输出：true
解释：
Alice 先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

示例 2：

输入：piles = [3,7,2,3]
输出：true

 

提示：

• 2 <= piles.length <= 500
• piles.length 是 偶数
• 1 <= piles[i] <= 500
• sum(piles[i]) 是 奇数

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

思考

两端取石子的零和博弈，求先手是否得分更高。堆数 $\le 500$，状态可用区间 $[i,j]$ 上「当前手相对对手的净收益」表示。

$dfs(i,j)$ 取 $piles[i]-dfs(i+1,j)$ 与 $piles[j]-dfs(i,j-1)$ 的较大者。先手净收益为正即获胜。题目条件下先手必胜，但代码仍按区间 DP 写出。

我们设计一个函数 $dfs(i,j)$，表示从第 $i$ 堆石子到第 $j$ 堆石子，当前玩家与另一个玩家的石子数量之差的最大值。那么答案就是 $dfs(0,n-1)>0$。

函数 $dfs(i,j)$ 的计算方法如下：

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

最后，我们只需要判断 $dfs(0,n-1)>0$ 即可。

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

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

func stoneGame(piles []int) bool {
	n := len(piles)
	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(piles[i]-dfs(i+1, j), piles[j]-dfs(i, j-1))
		}
		return f[i][j]
	}
	return dfs(0, n-1) > 0
}

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

思考

记忆化搜索的区间转移可改成递推，去掉递归。 $f[i][j]$ 表示区间 $[i,j]$ 上当前手的净收益，由长度为 $1$ 的对角线向外填。

转移式与方法一相同。答案看 $f[0][n-1]$ 是否为正。

我们也可以使用动态规划的方法，定义 $f[i][j]$ 表示当前玩家在 $piles[i..j]$ 这部分石子中能够获得的最大石子数的差值。那么最后答案就是 $f[0][n-1]>0$。

初始时 $f[i][i]=piles[i]$，因为只有一堆石子，所以当前玩家只能拿取这堆石子，差值为 $piles[i]$。

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

• 如果当前玩家拿走了石子堆 $piles[i]$，那么剩下的石子堆为 $piles[i+1..j]$，此时轮到另一个玩家进行游戏，所以 $f[i][j]=piles[i]-f[i+1][j]$。
• 如果当前玩家拿走了石子堆 $piles[j]$，那么剩下的石子堆为 $piles[i..j-1]$，此时轮到另一个玩家进行游戏，所以 $f[i][j]=piles[j]-f[i][j-1]$。

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

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

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

相似题目：

• 486. 预测赢家

func stoneGame(piles []int) bool {
	n := len(piles)
	f := make([][]int, n)
	for i, x := range piles {
		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(piles[i]-f[i+1][j], piles[j]-f[i][j-1])
		}
	}
	return f[0][n-1] > 0
}

力扣原题 · Doocs 题解来源

879. 盈利计划

困难2 种解法

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

题目、示例与约束

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

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

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

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

 

示例 1：

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。

示例 2：

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

 

提示：

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

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

思考

每个犯罪可选或不可选，受人数与最低利润约束，方案数取模。犯罪与人数规模有限，状态可记「考虑到第 $i$ 项、已用 $j$ 人、已获利润（封顶到 $\mathit{\text{minProfit}}$）」。

记忆化 $dfs(i,j,k)$：不选则前进，人数够则再加选中的一支。利润封顶是为了让达到门槛后的状态合并。边界在物品用尽时看 $k$ 是否已达门槛。

我们设计一个函数 $dfs(i,j,k)$，表示从第 $i$ 个工作开始，且当前已经选择了 $j$ 个员工，且当前产生的利润为 $k$，这种情况下的方案数。那么答案就是 $dfs(0,0,0)$。

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

• 如果 $i=n$，表示所有工作都已经考虑过了，如果 $k\ge minProfit$，则方案数为 $1$，否则方案数为 $0$；
• 如果 $i<n$，我们可以选择不选择第 $i$ 个工作，此时方案数为 $dfs(i+1,j,k)$；如果 $j+group[i]\le n$，我们也可以选择第 $i$ 个工作，此时方案数为 $dfs(i+1,j+group[i],min(k+profit[i],minProfit))$。这里我们将利润上限限制在 $minProfit$，是因为利润超过 $minProfit$ 对我们的答案没有任何影响。

最后返回 $dfs(0,0,0)$ 即可。

为了避免重复计算，我们可以使用记忆化搜索的方法，用一个三维数组 $f$ 记录所有的 $dfs(i,j,k)$ 的结果。当我们计算出 $dfs(i,j,k)$ 的值后，我们将其存入 $f[i][j][k]$ 中。调用 $dfs(i,j,k)$ 时，如果 $f[i][j][k]$ 已经被计算过，我们直接返回 $f[i][j][k]$ 即可。

时间复杂度 $O(m\times n\times minProfit)$，空间复杂度 $O(m\times n\times minProfit)$。其中 $m$ 和 $n$ 分别为工作的数量和员工的数量，而 $minProfit$ 为至少产生的利润。

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	m := len(group)
	f := make([][][]int, m)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, minProfit+1)
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	const mod = 1e9 + 7
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if i >= m {
			if k >= minProfit {
				return 1
			}
			return 0
		}
		if f[i][j][k] != -1 {
			return f[i][j][k]
		}
		ans := dfs(i+1, j, k)
		if j+group[i] <= n {
			ans += dfs(i+1, j+group[i], min(k+profit[i], minProfit))
		}
		ans %= mod
		f[i][j][k] = ans
		return ans
	}
	return dfs(0, 0, 0)
}

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

思考

同一三维状态可按物品下标递推，避免递归。 $f[i][j][k]$ 表示前 $i$ 项、人数 $j$、利润至少 $k$ 的方案数。

不选抄上一件，选则从 $f[i-1][j-x][max(0,k-p)]$ 转移。空方案在利润 $0$ 处为 $1$。答案为 $f[m][n][\mathit{\text{minProfit}}]$。

我们定义 $f[i][j][k]$ 表示前 $i$ 个工作中，选择了不超过 $j$ 个员工，且至少产生 $k$ 的利润的方案数。初始时 $f[0][j][0]=1$，表示不选择任何工作，且至少产生 $0$ 的利润的方案数为 $1$。答案即为 $f[m][n][minProfit]$。

对于第 $i$ 个工作，我们可以选择参与或不参与。如果不参与，则 $f[i][j][k]=f[i-1][j][k]$；如果参与，则 $f[i][j][k]=f[i-1][j-group[i-1]][max(0,k-profit[i-1])]$。我们需要枚举 $j$ 和 $k$，并将所有的方案数相加。

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

时间复杂度 $O(m\times n\times minProfit)$，空间复杂度 $O(m\times n\times minProfit)$。其中 $m$ 和 $n$ 分别为工作的数量和员工的数量，而 $minProfit$ 为至少产生的利润。

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	m := len(group)
	f := make([][][]int, m+1)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, minProfit+1)
		}
	}
	for j := 0; j <= n; j++ {
		f[0][j][0] = 1
	}
	const mod = 1e9 + 7
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			for k := 0; k <= minProfit; k++ {
				f[i][j][k] = f[i-1][j][k]
				if j >= group[i-1] {
					f[i][j][k] += f[i-1][j-group[i-1]][max(0, k-profit[i-1])]
					f[i][j][k] %= mod
				}
			}
		}
	}
	return f[m][n][minProfit]
}

力扣原题 · Doocs 题解来源

887. 鸡蛋掉落

困难2 种解法

标签：数学、二分查找、动态规划

题目、示例与约束

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

 

示例 1：

输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 
如果它没碎，那么肯定能得出 f = 2 。 
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。 

示例 2：

输入：k = 2, n = 6
输出：3

示例 3：

输入：k = 3, n = 14
输出：4

 

提示：

• 1 <= k <= 100
• 1 <= n <= 104

方法一：记忆化搜索 + 二分查找 · Go 实现

思考

有 $k$ 个鸡蛋、 $n$ 层楼，求最坏情况下最少扔几次。朴素枚举扔的楼层是 $O(k{n}^2)$，在约束下偏慢。对固定鸡蛋数，最坏次数关于楼层单调，存在使「碎 / 不碎」两次子问题尽量均衡的楼层。

记忆化 $dfs(i,j)$ 表示 $i$ 层 $j$ 个蛋。对扔的楼层二分，比较碎与不碎的代价，取平衡点后再加一次。一层或一蛋有闭式。

我们设计一个函数 $dfs(i,j)$，表示有 $i$ 层楼以及 $j$ 个鸡蛋时，确定 $f$ 值的最小操作次数，那么答案就是 $dfs(n,k)$。

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

如果 $i<1$，说明楼层已经小于等于 $0$，此时返回 $0$；

如果 $j=1$，说明只有一个鸡蛋，那么只能从第一层开始一层一层试，最坏情况下需要试 $i$ 次，此时返回 $i$；

否则，我们考虑枚举第一个鸡蛋从第 $x$ 层扔下的情况，其中 $1\le x\le i$。如果鸡蛋在第 $x$ 层扔下时碎了，说明 $f<x$，此时我们接下来需要在 $x-1$ 层下方以及剩下的 $j-1$ 个鸡蛋确定 $f$ 值，总共需要的最小操作次数为 $dfs(x-1,j-1)+1$ 次；如果鸡蛋在第 $x$ 层扔下时没碎，说明 $f>x$，此时我们需要在第 $x+1$ 层及以上以及剩下的 $j$ 个鸡蛋确定 $f$ 值，总共需要的最小操作次数为 $dfs(i-x,j)+1$ 次。由于我们要保证最坏情况下操作次数最少，因此 $dfs(i,j)=\underset{1\le x\le i}{min}max(dfs(x-1,j-1),dfs(i-x,j))+1$。

如果按照这样的方式枚举，由于状态数有 $n\times k$，每个状态需要枚举 $n$ 次，那么总时间复杂度达到 $O(n^2\times k)$，这会超出时间限制，我们考虑如何进行优化。

我们注意到函数 $dfs(x-1,j-1)$ 随着 $x$ 的增大而单调递增，而函数 $dfs(i-x,j)$ 随着 $x$ 的增大而单调递减，因此存在一个最优的 $x$ 值使得 $max(dfs(x-1,j-1),dfs(i-x,j))$ 达到最小值。我们可以对 $x$ 进行二分查找，找出这个最优的 $x$ 值。其中 $x$ 是满足 $dfs(x-1,j-1)\le dfs(i-x,j)$ 的最大整数。这样我们可以将时间复杂度降低到 $O(n\times k\log n)$。

时间复杂度 $O(n\times k\log n)$，空间复杂度 $O(n\times k)$。其中 $n$ 和 $k$ 分别是楼层数和鸡蛋数。

func superEggDrop(k int, n int) int {
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i < 1 {
			return 0
		}
		if j == 1 {
			return i
		}
		if f[i][j] != 0 {
			return f[i][j]
		}
		l, r := 1, i
		for l < r {
			mid := (l + r + 1) >> 1
			a, b := dfs(mid-1, j-1), dfs(i-mid, j)
			if a <= b {
				l = mid
			} else {
				r = mid - 1
			}
		}
		f[i][j] = max(dfs(l-1, j-1), dfs(i-l, j)) + 1
		return f[i][j]
	}
	return dfs(n, k)
}

方法二：动态规划 + 二分查找 · Go 实现

思考

同一转移可改成表 $f[i][j]$，按层数与蛋数填，避免递归。一蛋时 $f[i][1]=i$。

内层仍用二分找平衡楼层。答案为 $f[n][k]$，渐近与方法一相同，常数更稳。

我们也可以使用动态规划的方法解决这个问题。

我们定义 $f[i][j]$ 表示有 $i$ 层楼以及 $j$ 个鸡蛋时，确定 $f$ 值的最小操作次数，那么答案就是 $f[n][k]$。

状态转移方程为 $f[i][j]=\underset{1\le x\le i}{min}max(f[x-1][j-1],f[i-x][j])+1$。

与方法一类似，我们可以使用二分查找来优化 $x$ 的枚举过程。

时间复杂度 $O(n\times k\log n)$，空间复杂度 $O(n\times k)$。其中 $n$ 和 $k$ 分别是楼层数和鸡蛋数。

func superEggDrop(k int, n int) int {
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		f[i][1] = i
	}
	for i := 1; i <= n; i++ {
		for j := 2; j <= k; j++ {
			l, r := 1, i
			for l < r {
				mid := (l + r + 1) >> 1
				a, b := f[mid-1][j-1], f[i-mid][j]
				if a <= b {
					l = mid
				} else {
					r = mid - 1
				}
			}
			f[i][j] = max(f[l-1][j-1], f[i-l][j]) + 1
		}
	}
	return f[n][k]
}

力扣原题 · Doocs 题解来源

898. 子数组按位或操作

中等1 种解法

标签：位运算、数组、动态规划

题目、示例与约束

给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。

子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。

子数组 是数组内连续的非空元素序列。

 

示例 1：

输入：arr = [0]
输出：1
解释：
只有一个可能的结果 0 。

示例 2：

输入：arr = [1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

示例 3：

输入：arr = [1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。

 

提示：

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 109

方法一：哈希表 · Go 实现

思考

统计所有子数组按位或的不同结果。 $n\le 5\cdot {10}^4$，枚举子数组是平方级。以 $i$ 结尾的或值集合，等于「上一结尾集合中每个值或上 $arr[i]$」再并上 $\{arr[i]\}$。

或运算只增不减，以 $i$ 结尾的不同或值至多 $O(\log A)$ 个。用集合滚动这些值，并入全局集合后取其大小。

题目求的是子数组按位或操作的结果的数量，如果我们枚举子数组的结束位置 $i$，那么以 $i-1$ 结尾的子数组按位或操作的结果的数量最多不超过 $32$ 个。这是因为，按位或是一个单调递增的操作。

因此，我们用一个哈希表 $ans$ 记录所有子数组按位或操作的结果，用一个哈希表 $s$ 记录以当前元素结尾的子数组按位或操作的结果，初始时 $s$ 只包含一个元素 $0$。

接下来，我们枚举子数组的结束位置 $i$，那么以 $i$ 结尾的子数组按位或操作的结果，是以 $i-1$ 结尾的子数组按位或操作的结果与 $a[i]$ 进行按位或操作的结果的集合，再加上 $a[i]$ 本身。我们用一个哈希表 $t$ 记录以 $i$ 结尾的子数组按位或操作的结果，然后我们更新 $s=t$，并将 $t$ 中的所有元素加入 $ans$。

最终，我们返回哈希表 $ans$ 中元素的数量即可。

时间复杂度 $O(n\times \log M)$，空间复杂度 $O(n\times \log M)$。其中 $n$ 和 $M$ 分别为数组长度和数组中元素的最大值。

func subarrayBitwiseORs(arr []int) int {
	ans := map[int]bool{}
	s := map[int]bool{}
	for _, x := range arr {
		t := map[int]bool{x: true}
		for y := range s {
			t[x|y] = true
		}
		for y := range t {
			ans[y] = true
		}
		s = t
	}
	return len(ans)
}

力扣原题 · Doocs 题解来源

902. 最大为 N 的数字组合

困难1 种解法

标签：数组、数学、字符串、二分查找、动态规划

题目、示例与约束

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

 

示例 1：

输入：digits = ["1","3","5","7"], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：

输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

示例 3:

输入：digits = ["7"], n = 8
输出：1

 

提示：

• 1 <= digits.length <= 9
• digits[i].length == 1
• digits[i] 是从 '1' 到 '9' 的数
• digits 中的所有值都 不同 
• digits 按 非递减顺序 排列
• 1 <= n <= 109

方法一：数位 DP · Go 实现

思考

用给定数位拼出不超过 $n$ 的正整数，按长度枚举全部排列会在接近 $n$ 的位数上重复展开相同前缀。方案数只取决于当前位、是否仍为前导零、以及是否贴着上界。

将 $n$ 写成字符串 $s$，记忆化搜索 $\mathit{\text{dfs}}(i,\mathit{\text{lead}},\mathit{\text{limit}})$：前导零可继续填 $0$，否则只能填 $\mathit{\text{digits}}$ 中的数字，并按 $\mathit{\text{limit}}$ 限制本界。处理完所有位后，非前导零的构造计为 $1$。

这道题实际上是求在给定区间 $[l,..r]$ 中，由 digits 中的数字生成的正整数的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 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$，记字符串 $s$ 的长度为 $m$。

接下来，我们设计一个函数 $\mathit{\text{dfs}}(i,\mathit{\text{lead}},\mathit{\text{limit}})$，表示当前处理到字符串的第 $i$ 位，到最后一位的方案数。其中：

• 数字 $i$ 表示当前处理到字符串 $s$ 的第 $i$ 位；
• 布尔值 $\mathit{\text{lead}}$ 表示是否只包含前导零；
• 布尔值 $\mathit{\text{limit}}$ 表示当前位置是否受到上界的限制。

函数的执行过程如下：

如果 $i$ 大于等于 $m$，说明我们已经处理完了所有的位数，此时如果 $\mathit{\text{lead}}$ 为真，说明当前的数字是前导零，我们应当返回 $0$；否则，我们应当返回 $1$。

否则，我们计算当前位置的上界 $\mathit{\text{up}}$，如果 $\mathit{\text{limit}}$ 为真，则 $up$ 为 $s[i]$ 对应的数字，否则 $up$ 为 $9$。

然后，我们在 $[0,\mathit{\text{up}}]$ 的范围内枚举当前位置的数字 $j$，如果 $j$ 为 $0$ 且 $\mathit{\text{lead}}$ 为真，我们递归计算 $\mathit{\text{dfs}}(i+1,\text{true},\mathit{\text{limit}}\wedge j=\mathit{\text{up}})$；否则，如果 $j$ 在 $\mathit{\text{digits}}$ 中，我们递归计算 $\mathit{\text{dfs}}(i+1,\text{false},\mathit{\text{limit}}\wedge j=\mathit{\text{up}})$。累加所有的结果即为答案。

最后，我们返回 $\mathit{\text{dfs}}(0,\text{true},\text{true})$ 即可。

时间复杂度 $O(\log n\times D)$，空间复杂度 $O(\log n)$。其中 $D=10$。

相似题目：

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

func atMostNGivenDigitSet(digits []string, n int) int {
	s := strconv.Itoa(n)
	m := len(s)
	f := make([]int, m)
	for i := range f {
		f[i] = -1
	}
	nums := map[int]bool{}
	for _, d := range digits {
		x, _ := strconv.Atoi(d)
		nums[x] = true
	}
	var dfs func(i int, lead, limit bool) int
	dfs = func(i int, lead, limit bool) int {
		if i >= m {
			if lead {
				return 0
			}
			return 1
		}
		if !lead && !limit && f[i] != -1 {
			return f[i]
		}
		up := 9
		if limit {
			up = int(s[i] - '0')
		}
		ans := 0
		for j := 0; j <= up; j++ {
			if j == 0 && lead {
				ans += dfs(i+1, true, limit && j == up)
			} else if nums[j] {
				ans += dfs(i+1, false, limit && j == up)
			}
		}
		if !lead && !limit {
			f[i] = ans
		}
		return ans
	}
	return dfs(0, true, true)
}

力扣原题 · Doocs 题解来源

903. DI 序列的有效排列

困难3 种解法

标签：字符串、动态规划、前缀和

题目、示例与约束

给定一个长度为 n 的字符串 s ，其中 s[i] 是:

• “D” 意味着减少，或者
• “I” 意味着增加

有效排列 是对有 n + 1 个在 [0, n]  范围内的整数的一个排列 perm ，使得对所有的 i：

• 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；
• 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回 有效排列  perm的数量 。因为答案可能很大，所以请返回你的答案对 109 + 7 取余。

 

示例 1：

输入：s = "DID"
输出：5
解释：
(0, 1, 2, 3) 的五个有效排列是：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

示例 2:

输入: s = "D"
输出: 1

 

提示:

• n == s.length
• 1 <= n <= 200
• s[i] 不是 'I' 就是 'D'

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

思考

长度为 $n$ 的 DI 串对应 $0..n$ 的排列， $n$ 可达 $200$，枚举排列不可行。关键在于相对名次：放完前 $i$ 个数后，下一个数在剩余数中的名次 $j$ 决定与上一位置的升降关系。

定义 $f[i][j]$ 为前 $i$ 个字符、以名次 $j$ 结尾的方案数。遇 'D' 时从更大的名次转移，遇 'I' 时从更小的名次转移；已用名次压缩到 $[0,i]$，得到立方级递推。

我们定义 $f[i][j]$ 表示字符串的前 $i$ 个字符中，以数字 $j$ 结尾的满足题目要求的排列的数量。初始时 $f[0][0]=1$，其余 $f[0][j]=0$。答案为 $\sum _{j=0}^{n}f[n][j]$。

考虑 $f[i][j]$，其中 $j\in [0,i]$。

如果第 $i$ 个字符 $s[i-1]$ 是 'D'，那么 $f[i][j]$ 可以从 $f[i-1][k]$ 转移而来，其中 $k\in [j+1,i]$，而由于 $k-1$ 最大只能为 $i-1$，我们将 $k$ 向左移动一位，那么 $k\in [j,i-1]$，因此有 $f[i][j]=\sum _{k=j}^{i-1}f[i-1][k]$。

如果第 $i$ 个字符 $s[i-1]$ 是 'I'，那么 $f[i][j]$ 可以从 $f[i-1][k]$ 转移而来，其中 $k\in [0,j-1]$，因此有 $f[i][j]=\sum _{k=0}^{j-1}f[i-1][k]$。

最终的答案即为 $\sum _{j=0}^{n}f[n][j]$。

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

func numPermsDISequence(s string) (ans int) {
	const mod = 1e9 + 7
	n := len(s)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	for i := 1; i <= n; i++ {
		if s[i-1] == 'D' {
			for j := 0; j <= i; j++ {
				for k := j; k < i; k++ {
					f[i][j] = (f[i][j] + f[i-1][k]) % mod
				}
			}
		} else {
			for j := 0; j <= i; j++ {
				for k := 0; k < j; k++ {
					f[i][j] = (f[i][j] + f[i-1][k]) % mod
				}
			}
		}
	}
	for j := 0; j <= n; j++ {
		ans = (ans + f[n][j]) % mod
	}
	return
}

方法二：前缀和优化 · Go 实现

思考

方法一每次转移要扫一段 $k$，同一行上相邻的 $j$ 共享几乎相同的区间和。用按方向滚动的前缀和在常数时间内得到 $\sum f[i-1][k]$，时间降为平方级，状态定义不变。

我们可以用前缀和优化状态转移，将时间复杂度降低到 $O(n^2)$。空间复杂度仍为 $O(n^2)$。

func numPermsDISequence(s string) (ans int) {
	const mod = 1e9 + 7
	n := len(s)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	for i := 1; i <= n; i++ {
		pre := 0
		if s[i-1] == 'D' {
			for j := i; j >= 0; j-- {
				pre = (pre + f[i-1][j]) % mod
				f[i][j] = pre
			}
		} else {
			for j := 0; j <= i; j++ {
				f[i][j] = pre
				pre = (pre + f[i-1][j]) % mod
			}
		}
	}
	for j := 0; j <= n; j++ {
		ans = (ans + f[n][j]) % mod
	}
	return
}

方法三：滚动数组优化 · Go 实现

思考

$f[i]$ 只依赖 $f[i-1]$，二维表中多数空间可以丢掉。用一维数组滚动，按 'D'/'I' 的方向维护累加和写入新一层，空间降至线性。

在方法二的基础上，我们使用滚动数组将空间复杂度优化到 $O(n)$。时间复杂度仍为 $O(n^2)$。

func numPermsDISequence(s string) (ans int) {
	const mod = 1e9 + 7
	n := len(s)
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; i <= n; i++ {
		pre := 0
		g := make([]int, n+1)
		if s[i-1] == 'D' {
			for j := i; j >= 0; j-- {
				pre = (pre + f[j]) % mod
				g[j] = pre
			}
		} else {
			for j := 0; j <= i; j++ {
				g[j] = pre
				pre = (pre + f[j]) % mod
			}
		}
		f = g
	}
	for j := 0; j <= n; j++ {
		ans = (ans + f[j]) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

907. 子数组的最小值之和

中等1 种解法

标签：栈、数组、动态规划、单调栈

题目、示例与约束

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

 

示例 1：

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

输入：arr = [11,81,94,43,3]
输出：444

 

提示：

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

 

方法一：单调栈 · Go 实现

思考

对每个子数组取最小值再求和，区间数为平方级，直接枚举不可行。改为贡献法：每个 $arr[i]$ 作为最小值出现的次数乘以自身。

用单调栈求左侧第一个更小、右侧第一个小于等于的边界，使相等元素只被一侧认领，避免重复。次数即为两侧跨度之积。

题目要求的是每个子数组的最小值之和，实际上相当于，对于每个元素 $arr[i]$，求以 $arr[i]$ 为最小值的子数组的个数，然后乘以 $arr[i]$，最后求和。

因此，题目的重点转换为：求以 $arr[i]$ 为最小值的子数组的个数。对于 $arr[i]$，我们找出其左边第一个小于 $arr[i]$ 的位置 $left[i]$，右侧第一个小于等于 $arr[i]$ 的位置 $right[i]$，则以 $arr[i]$ 为最小值的子数组的个数为 $(i-left[i])\times (right[i]-i)$。

注意，这里为什么要求右侧第一个小于等于 $arr[i]$ 的位置 $right[i]$，而不是小于 $arr[i]$ 的位置呢？这是因为，如果是右侧第一个小于 $arr[i]$ 的位置 $right[i]$，则会导致重复计算。

我们可以举个例子来说明，对于以下数组：

下标为 $3$ 的元素大小为 $2$，左侧第一个小于 $2$ 的元素下标为 $0$，如果我们求右侧第一个小于 $2$ 的元素下标，可以得到下标为 $7$。也即是说，子数组区间为 $(0,7)$。注意，这里是开区间。

0 4 3 2 5 3 2 1
*     ^       *

按照同样的方法，我们可以求出下标为 $6$ 的元素的子数组区间，可以发现，其子数组区间也为 $(0,7)$，也即是说，下标为 $3$ 和下标为 $6$ 的元素的子数组区间是重复的。这样就造成了重复计算。

0 4 3 2 5 3 2 1
*           ^ *

如果我们求的是右侧第一个小于等于其值的下标，就不会有重复问题，因为下标为 $3$ 的子数组区间变为 $(0,6)$，下标为 $6$ 的子数组区间为 $(0,7)$，两者不重复。

回到这道题上，我们只需要遍历数组，对于每个元素 $arr[i]$，利用单调栈求出其左侧第一个小于 $arr[i]$ 的位置 $left[i]$，右侧第一个小于等于 $arr[i]$ 的位置 $right[i]$，则以 $arr[i]$ 为最小值的子数组的个数为 $(i-left[i])\times (right[i]-i)$，然后乘以 $arr[i]$，最后求和即可。

注意数据的溢出以及取模操作。

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

func sumSubarrayMins(arr []int) (ans int) {
	n := len(arr)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = -1
		right[i] = n
	}
	stk := []int{}
	for i, v := range arr {
		for len(stk) > 0 && arr[stk[len(stk)-1]] >= v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && arr[stk[len(stk)-1]] > arr[i] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	const mod int = 1e9 + 7
	for i, v := range arr {
		ans += (i - left[i]) * (right[i] - i) * v % mod
		ans %= mod
	}
	return
}

力扣原题 · Doocs 题解来源

918. 环形子数组的最大和

中等1 种解法

标签：队列、数组、分治、动态规划、单调队列

题目、示例与约束

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

 

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：

输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

 

提示：

• n == nums.length
• 1 <= n <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104​​​​​​​

方法一：维护前缀最值 · Go 实现

思考

环形最大子段和有两种形态：不跨越端点时即普通最大子段；跨越时等于总和减去最小子段。一次扫描同时维护前缀最小与前缀最大，分别得到这两种量，最后取 $ans$ 与 $s-smi$ 的较大者。

求环形子数组的最大和，可以分为两种情况：

• 情况一：最大和的子数组不包含环形部分，即为普通的最大子数组和；
• 情况二：最大和的子数组包含环形部分，我们可以转换为：求数组总和减去最小子数组和。

因此，我们维护以下几个变量：

• 前缀和最小值 $pmi$，初始值为 $0$；
• 前缀和最大值 $pmx$，初始值为 $-\mathrm{\infty }$；
• 前缀和 $s$，初始值为 $0$；
• 最小子数组和 $smi$，初始值为 $\mathrm{\infty }$；
• 答案 $ans$，初始值为 $-\mathrm{\infty }$。

接下来，我们只需要遍历数组 $nums$，对于当前遍历到的元素 $x$，我们做以下更新操作：

• 更新前缀和 $s=s+x$；
• 更新答案 $ans=max(ans,s-pmi)$，即为情况一的答案（前缀和 $s$ 减去最小前缀和 $pmi$，可以得到最大子数组和）；
• 更新 $smi=min(smi,s-pmx)$，即为情况二的最小子数组和；
• 更新 $pmi=min(pmi,s)$，即为最小前缀和；
• 更新 $pmx=max(pmx,s)$，即为最大前缀和。

遍历结束，我们取 $ans$ 以及 $s-smi$ 的最大值作为答案返回即可。

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

func maxSubarraySumCircular(nums []int) int {
	const inf = 1 << 30
	pmi, pmx := 0, -inf
	ans, s, smi := -inf, 0, inf
	for _, x := range nums {
		s += x
		ans = max(ans, s-pmi)
		smi = min(smi, s-pmx)
		pmi = min(pmi, s)
		pmx = max(pmx, s)
	}
	return max(ans, s-smi)
}

力扣原题 · Doocs 题解来源

920. 播放列表的数量

困难2 种解法

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

题目、示例与约束

你的音乐播放器里有 n 首不同的歌，在旅途中，你计划听 goal 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：

• 每首歌 至少播放一次 。
• 一首歌只有在其他 k 首歌播放完之后才能再次播放。

给你 n、goal 和 k ，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 109 + 7 取余 的结果。

 

示例 1：

输入：n = 3, goal = 3, k = 1
输出：6
解释：有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1] 。

示例 2：

输入：n = 2, goal = 3, k = 0
输出：6
解释：有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2] 。

示例 3：

输入：n = 2, goal = 3, k = 1
输出：2
解释：有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2] 。

 

提示：

• 0 <= k < n <= goal <= 100

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

思考

长度为 $goal$ 的播放列表须恰好用到 $n$ 首不同歌，且同一首再次出现至少间隔 $k$。 $goal,n\le 100$，状态规模允许 DP。 $f[i][j]$ 表示听了 $i$ 首、其中 $j$ 首不同：新歌有 $n-j+1$ 种，老歌在 $j>k$ 时有 $j-k$ 种。目标为 $f[goal][n]$。

我们定义 $f[i][j]$ 表示听 $i$ 首歌，且这 $i$ 首歌中有 $j$ 首不同歌曲的播放列表的数量。初始时 $f[0][0]=1$。答案为 $f[goal][n]$。

对于 $f[i][j]$，我们可以选择没听过的歌，那么上一个状态为 $f[i-1][j-1]$，这样的选择有 $n-(j-1)=n-j+1$ 种，因此 $f[i][j]+=f[i-1][j-1]\times (n-j+1)$。我们也可以选择听过的歌，那么上一个状态为 $f[i-1][j]$，这样的选择有 $j-k$ 种，因此 $f[i][j]+=f[i-1][j]\times (j-k)$，其中 $j\ge k$。

综上，我们可以得到状态转移方程：

$$f[i][j]=\{\begin{array}{ll}1& i=0,j=0\\ f[i-1][j-1]\times (n-j+1)+f[i-1][j]\times (j-k)& i\ge 1,j\ge 1\end{array}$$

最终的答案为 $f[goal][n]$。

时间复杂度 $O(goal\times n)$，空间复杂度 $O(goal\times n)$。其中 $goal$ 和 $n$ 为题目中给定的参数。

func numMusicPlaylists(n int, goal int, k int) int {
	const mod = 1e9 + 7
	f := make([][]int, goal+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	for i := 1; i <= goal; i++ {
		for j := 1; j <= n; j++ {
			f[i][j] = f[i-1][j-1] * (n - j + 1)
			if j > k {
				f[i][j] += f[i-1][j] * (j - k)
			}
			f[i][j] %= mod
		}
	}
	return f[goal][n]
}

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

思考

第 $i$ 层只依赖第 $i-1$ 层的 $j-1$ 与 $j$，二维表可滚成一维，空间降至 $O(n)$。

我们注意到 $f[i][j]$ 只与 $f[i-1][j-1]$ 和 $f[i-1][j]$ 有关，因此我们可以使用滚动数组优化空间复杂度，将空间复杂度优化至 $O(n)$。

func numMusicPlaylists(n int, goal int, k int) int {
	const mod = 1e9 + 7
	f := make([]int, goal+1)
	f[0] = 1
	for i := 1; i <= goal; i++ {
		g := make([]int, goal+1)
		for j := 1; j <= n; j++ {
			g[j] = f[j-1] * (n - j + 1)
			if j > k {
				g[j] += f[j] * (j - k)
			}
			g[j] %= mod
		}
		f = g
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

926. 将字符串翻转到单调递增

中等1 种解法

标签：字符串、动态规划

题目、示例与约束

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

返回使 s 单调递增的最小翻转次数。

 

示例 1：

输入：s = "00110"
输出：1
解释：翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000。

 

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'

方法一：前缀和 + 枚举 · Go 实现

思考

单调递增即某分割点左侧全为 $0$、右侧全为 $1$。 $n\le {10}^5$，对每个分割点重扫代价过高。记全串 $0$ 的个数为 $\mathit{\text{tot}}$，枚举分割点时用前缀 $0$ 的个数 $\mathit{\text{cur}}$ 即可算出左侧翻 $1$、右侧翻 $0$ 的次数 $i-\mathit{\text{cur}}+\mathit{\text{tot}}-\mathit{\text{cur}}$，取最小者。

我们可以先统计字符串 $s$ 中 $0$ 的个数，记为 $tot$。定义一个答案变量 $ans$，初始时 $ans=tot$，表示将所有 $0$ 变成 $1$ 的翻转次数。

然后，我们可以枚举每个位置 $i$，将位置 $i$ 及其左边的所有 $1$ 变成 $0$，将位置 $i$ 右边的所有 $0$ 变成 $1$，计算这种情况下的翻转次数，即 $i+1-cur+tot-cur$，其中 $cur$ 表示位置 $i$ 及其左边的 $0$ 的个数，更新答案 $ans=min(ans,i+1-cur+tot-cur)$。

最后返回答案 $ans$ 即可。

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

func minFlipsMonoIncr(s string) int {
	tot := strings.Count(s, "0")
	ans, cur := tot, 0
	for i, c := range s {
		if c == '0' {
			cur++
		}
		ans = min(ans, i+1-cur+tot-cur)
	}
	return ans
}

力扣原题 · Doocs 题解来源

931. 下降路径最小和

中等1 种解法

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

题目、示例与约束

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

 

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径

 

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

方法一：动态规划（滚动数组） · Go 实现

思考

下降路径每步只能走到下一行相邻三列， $n\le 100$。枚举全部路径不可行。到达 $(i,j)$ 的最小和只依赖上一行 $j-1,j,j+1$。逐行递推，并用一维数组滚动，空间降为 $O(n)$。

定义 $f[i][j]$ 表示从第一行下降到第 $i$ 行第 $j$ 列的最小路径和：

$$f[i][j]=\mathit{\text{matrix}}[i][j]+min\{\begin{array}{rlr}& f[i-1][j-1],& j>0\\ & f[i-1][j],& 0\le j<n\\ & f[i-1][j+1],& j+1<n\end{array}$$

答案为 $\underset{0\le j<n}{min}f[n-1][j]$。

$f[i][j]$ 只依赖上一行，因此只用两个长度为 $n$ 的一维数组 $f$、 $g$ 滚动即可。

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

func minFallingPathSum(matrix [][]int) int {
	n := len(matrix)
	f := make([]int, n)
	for _, row := range matrix {
		g := make([]int, n)
		copy(g, f)
		for j, x := range row {
			if j > 0 {
				g[j] = min(g[j], f[j-1])
			}
			if j+1 < n {
				g[j] = min(g[j], f[j+1])
			}
			g[j] += x
		}
		f = g
	}
	return slices.Min(f)
}

力扣原题 · Doocs 题解来源

935. 骑士拨号器

中等2 种解法

标签：动态规划

题目、示例与约束

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。

象棋骑士可能的移动方式如下图所示:

我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。

给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。

你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。

因为答案可能很大，所以输出答案模 109 + 7.

 

示例 1：

输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。

示例 2：

输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

示例 3：

输入：n = 3131
输出：136006598
解释：注意取模

 

提示：

• 1 <= n <= 5000

方法一：递推 · Go 实现

思考

骑士在电话键盘上跳 $n-1$ 步， $n\le 5000$。每格的前驱固定，长度为 $i$ 且落在数字 $d$ 的方案只依赖上一跳的前驱。用长度为 $10$ 的数组递推 $n-1$ 轮，最后求和取模。

根据题目描述，我们需要计算出长度为 $n$ 的不同电话号码的数量。其中，每个数字的上一个数字只有固定的几个，我们可以列出每个数字的上一个数字：

当前数字	上一个数字
0	4, 6
1	6, 8
2	7, 9
3	4, 8
4	0, 3, 9
5
6	0, 1, 7
7	2, 6
8	1, 3
9	2, 4

我们可以通过递推的方式，计算出长度为 $n$ 的不同电话号码的数量。设 $f[i]$ 表示长度为 $i$ 的不同电话号码的数量，初始时 $f[1]=1$。对于长度为 $i$ 的电话号码，我们可以通过长度为 $i-1$ 的电话号码计算出来，因此我们可以得到递推关系：

$$\begin{array}{rl}g[0]& =f[4]+f[6]\\ g[1]& =f[6]+f[8]\\ g[2]& =f[7]+f[9]\\ g[3]& =f[4]+f[8]\\ g[4]& =f[0]+f[3]+f[9]\\ g[6]& =f[0]+f[1]+f[7]\\ g[7]& =f[2]+f[6]\\ g[8]& =f[1]+f[3]\\ g[9]& =f[2]+f[4]\end{array}$$

然后，我们将 $f$ 更新为 $g$，继续计算下一个长度的电话号码，直到计算出长度为 $n$ 的电话号码的数量。

最后，我们将 $f$ 中所有元素相加，取模 ${10}^9+7$，即为答案。

时间复杂度 $O(n)$，其中 $n$ 为电话号码的长度。空间复杂度 $O(|\mathrm{\Sigma }|)$，其中 $\mathrm{\Sigma }$ 为数字集合，本题中 $|\mathrm{\Sigma }|=10$。

func knightDialer(n int) (ans int) {
	f := make([]int, 10)
	for i := range f {
		f[i] = 1
	}
	const mod int = 1e9 + 7
	for i := 1; i < n; i++ {
		g := make([]int, 10)
		g[0] = (f[4] + f[6]) % mod
		g[1] = (f[6] + f[8]) % mod
		g[2] = (f[7] + f[9]) % mod
		g[3] = (f[4] + f[8]) % mod
		g[4] = (f[0] + f[3] + f[9]) % mod
		g[6] = (f[0] + f[1] + f[7]) % mod
		g[7] = (f[2] + f[6]) % mod
		g[8] = (f[1] + f[3]) % mod
		g[9] = (f[2] + f[4]) % mod
		f = g
	}
	for _, x := range f {
		ans = (ans + x) % mod
	}
	return
}

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

思考

方法一为线性于 $n$ 的递推。该转移是常系数线性，可写成 $10\times 10$ 矩阵，用快速幂在 $O(\log n)$ 次矩阵乘内得到 $T(n)$。

我们假设 $T(n)$ 表示一个 $1\times 10$ 的矩阵 $\left[\begin{array}{ccc}{F}_0& F_1& F_2\cdots F_9\end{array}\right]$，其中 $F_i$ 表示第 $i$ 个电话号码的数量。我们希望根据 $T(n-1)$ 推出 $T(n)$。也即是说，我们需要一个矩阵 $\mathit{\text{base}}$，使得 $T(n-1)\times \mathit{\text{base}}=T(n)$，即：

$$\left[\begin{array}{ccc}{F}_0& F_1& F_2\cdots F_9\end{array}\right]\times \mathit{\text{base}}=\left[\begin{array}{ccc}{F}_0^{\prime }& F_1^{\prime }& F_2^{\prime }\cdots F_9^{\prime }\end{array}\right]$$

由于 $F_i^{\prime }=\sum _j{F}_j$，其中 $j$ 是 $i$ 的上一个数字，所以矩阵 $\mathit{\text{base}}$ 的第 $1$ 列为：

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

依次类推，我们可以得到矩阵 $\mathit{\text{base}}$ 如下：

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

我们定义初始矩阵 $res=\left[\begin{array}{ccc}1& 1& 1\cdots 1\end{array}\right]$，与 $n-1$ 个 $\mathit{\text{base}}$ 矩阵相乘，即可得到 $T(n)$。最后，我们将 $T(n)$ 中所有元素相加，取模 ${10}^9+7$，即为答案。求 ${\mathit{\text{base}}}^{n-1}$，可以通过矩阵快速幂的方式，时间复杂度为 $O(\log n)$。

时间复杂度 $O(\log n)$，空间复杂度 $O(|\mathrm{\Sigma }{|}^2)$，其中 $\mathrm{\Sigma }$ 为数字集合，本题中 $|\mathrm{\Sigma }|=10$。

const mod = 1e9 + 7

func knightDialer(n int) int {
	base := [][]int{
		{0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
		{0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
		{1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{1, 1, 0, 0, 0, 0, 0, 1, 0, 0},
		{0, 0, 1, 0, 0, 0, 1, 0, 0, 0},
		{0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
		{0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
	}

	res := pow(base, n-1)
	ans := 0
	for _, x := range res[0] {
		ans = (ans + x) % mod
	}
	return ans
}

func mul(a, b [][]int) [][]int {
	m := len(a)
	n := 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]) % mod
			}
		}
	}
	return c
}

func pow(a [][]int, n int) [][]int {
	size := len(a)
	res := make([][]int, 1)
	res[0] = make([]int, size)
	for i := 0; i < size; i++ {
		res[0][i] = 1
	}

	for n > 0 {
		if n%2 == 1 {
			res = mul(res, a)
		}
		a = mul(a, a)
		n /= 2
	}

	return res
}

力扣原题 · Doocs 题解来源

940. 不同的子序列 II

困难2 种解法

标签：字符串、动态规划

题目、示例与约束

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

• 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

 

示例 1：

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

 

提示：

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

 

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

思考

不同非空子序列的个数， $n\le 2000$，不能枚举子集。以末字符分类： $f[c]$ 表示当前以 $c$ 结尾的不同子序列数。读入 $c$ 时，它可以接在此前任意子序列之后，也可以单独成串，故 $f[c]\leftarrow \sum f+1$，重复字符会覆盖旧的以 $c$ 结尾的集合。

我们定义 $f[i]$ 表示以第 $i$ 个小写字母结尾的不同子序列的个数。初始时 $f$ 中所有元素均为 $0$。

遍历字符串 $s$，对于当前字符 $c$，我们将 $f[c]$ 更新为 $\sum _{i=0}^{25}f[i]+1$。其中 $\sum _{i=0}^{25}f[i]$ 表示此前已经得到的所有不同子序列的个数，而 $+1$ 表示字符 $c$ 本身也可以作为一个子序列。

最后，答案为 $\sum _{i=0}^{25}f[i]$，对 ${10}^9+7$ 取余。

时间复杂度 $O(n\times C)$，空间复杂度 $O(C)$。其中 $n$ 是字符串 $s$ 的长度，而 $C$ 是字符集的大小，本题中 $C=26$。

func distinctSubseqII(s string) int {
	const mod int = 1e9 + 7
	f := [26]int{}
	for _, c := range s {
		x := 1
		for _, v := range f {
			x = (x + v) % mod
		}
		f[c-'a'] = x
	}
	ans := 0
	for _, v := range f {
		ans = (ans + v) % mod
	}
	return ans
}

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

思考

方法一每次更新要扫 $26$ 个格子。维护总和 $\mathit{\text{ans}}$，新增量为 $\mathit{\text{ans}}-f[i]+1$，即可 $O(1)$ 更新 $f[i]$ 与 $\mathit{\text{ans}}$。

在方法一的基础上，我们可以维护一个变量 $\mathit{\text{ans}}$ 表示当前 $f$ 数组中所有元素的和。每次更新 $f[i]$ 时，新增的不同子序列个数为 $\mathit{\text{ans}}-f[i]+1$，据此同时更新 $\mathit{\text{ans}}$ 与 $f[i]$ 即可。

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

相似题目：

• 1987. 不同的好子序列数目

func distinctSubseqII(s string) int {
	const mod int = 1e9 + 7
	f := [26]int{}
	ans := 0
	for _, c := range s {
		i := c - 'a'
		add := (ans + 1 + mod - f[i]) % mod
		ans = (ans + add) % mod
		f[i] = (f[i] + add) % mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

943. 最短超级串

困难1 种解法

标签：位运算、数组、字符串、动态规划、位掩码、哈密顿通路

题目、示例与约束

给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。

我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。

 

示例 1：

输入：words = ["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。

示例 2：

输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"

 

提示：

• 1 <= words.length <= 12
• 1 <= words[i].length <= 20
• words[i] 由小写英文字母组成
• words 中的所有字符串 互不相同

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

思考

最短超级串相当于一条经过每个单词恰好一次的路径，重叠尽量大。 $n\le 12$，状态可用子集表示。预处理 $g[i][j]$ 为 $i$ 接到 $j$ 的最大重叠，再 DP： $dp[S][j]$ 为走过集合 $S$、止于 $j$ 的最大重叠。记录前驱后逆推出顺序并拼接未覆盖的单词。

由于题目中字符串数组 words 的长度不超过 12，因此可以使用状态压缩的方法来表示字符串数组中的每个字符串是否被选中。

定义 $dp[i][j]$ 表示字符串当前选中状态为 $i$，且最后一个选中的字符串为 $s[j]$ 时，字符串重叠部分的最大长度。其中 $i$ 的二进制表示中的第 $j$ 位为 $1$ 表示字符串 $s[j]$ 被选中，为 $0$ 表示字符串 $s[j]$ 未被选中。重叠部分达到最大时，最终得到的字符串最短。我们只要求出重叠部分的最大值以及对应的字符串 $s[j]$，记录每一步状态转移，就能够逆推出最终的字符串。

字符串两两之间的重叠部分长度可以预处理出来，存储在二维数组 $g$ 中，其中 $g[i][j]$ 表示字符串 $s[i]$ 和字符串 $s[j]$ 之间的重叠部分长度。

动态规划的状态转移方程如下：

$$dp[i][j]=\underset{k\in \{0,1,\cdots ,n-1\}}{max}\{dp[i-2^j][k]+g[k][j]\}$$

时间复杂度 $O(2^n\times n^2)$，空间复杂度 $O(2^n\times n)$。其中 $n$ 为字符串数组 words 的长度。

func shortestSuperstring(words []string) string {
	n := len(words)
	g := make([][]int, n)
	for i, a := range words {
		g[i] = make([]int, n)
		for j, b := range words {
			if i != j {
				for k := min(len(a), len(b)); k > 0; k-- {
					if a[len(a)-k:] == b[:k] {
						g[i][j] = k
						break
					}
				}
			}
		}
	}
	dp := make([][]int, 1<<n)
	p := make([][]int, 1<<n)
	for i := 0; i < 1<<n; i++ {
		dp[i] = make([]int, n)
		p[i] = make([]int, n)
		for j := 0; j < n; j++ {
			p[i][j] = -1
			if ((i >> j) & 1) == 1 {
				pi := i ^ (1 << j)
				for k := 0; k < n; k++ {
					if ((pi >> k) & 1) == 1 {
						v := dp[pi][k] + g[k][j]
						if v > dp[i][j] {
							dp[i][j] = v
							p[i][j] = k
						}
					}
				}
			}
		}
	}
	j := 0
	for i := 0; i < n; i++ {
		if dp[(1<<n)-1][i] > dp[(1<<n)-1][j] {
			j = i
		}
	}
	arr := []int{j}
	vis := make([]bool, n)
	vis[j] = true
	for i := (1 << n) - 1; p[i][j] != -1; {
		k := i
		i ^= (1 << j)
		j = p[k][j]
		arr = append(arr, j)
		vis[j] = true
	}
	for i := 0; i < n; i++ {
		if !vis[i] {
			arr = append(arr, i)
		}
	}
	ans := &strings.Builder{}
	ans.WriteString(words[arr[n-1]])
	for i := n - 2; i >= 0; i-- {
		k := g[arr[i+1]][arr[i]]
		ans.WriteString(words[arr[i]][k:])
	}
	return ans.String()
}

力扣原题 · Doocs 题解来源

956. 最高的广告牌

困难2 种解法

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

题目、示例与约束

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。

返回 广告牌的最大可能安装高度 。如果没法安装广告牌，请返回 0 。

 

示例 1：

输入：[1,2,3,6]
输出：6
解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。

示例 2：

输入：[1,2,3,4,5,6]
输出：10
解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。

示例 3：

输入：[1,2]
输出：0
解释：没法安装广告牌，所以返回 0。

 

提示：

1. 0 <= rods.length <= 20
2. 1 <= rods[i] <= 1000
3. sum(rods[i]) <= 5000

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

思考

三分配钢筋：左柱、右柱或丢弃，使两柱等高且尽量高。 $n$ 不大但子集和较大，枚举 $3^n$ 不可行。状态只需“用到第 $i$ 根、当前高度差 $j$”的最大共同高度。三选一转移，差为 $0$ 时即为可行高度。记忆化避免重复。

我们设计一个函数 $dfs(i,j)$，表示从第 $i$ 根钢筋开始，且当前高度差为 $j$ 时，两边的最大共同高度。那么答案就是 $dfs(0,0)$。

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

如果 $i=n$，此时判断 $j$ 是否为 $0$，如果是则返回 $0$，否则返回 $-\mathrm{\infty }$。

如果 $i<n$，此时有三种情况：

1. 不选择第 $i$ 根钢筋，此时 $dfs(i,j)=dfs(i+1,j)$；
2. 选择第 $i$ 根钢筋，并且放置在原本高度较高的一边，那么 $dfs(i,j)=dfs(i+1,j+rods[i])$；
3. 选择第 $i$ 根钢筋，并且放置在高度较低的一边，此时共同高度增加了 $min(j,rods[i])$，那么 $dfs(i,j)=dfs(i+1,|rods[i]-j|)+min(j,rods[i])$。

我们取这三种情况下的最大值，即可得到 $dfs(i,j)$ 的值。

为了避免重复计算，我们使用一个二维数组 $f$ 来记录已经计算过的 $dfs(i,j)$ 的值，调用 $dfs(i,j)$ 时，如果 $f[i][j]$ 已经被计算过，则直接返回 $f[i][j]$。否则，我们计算 $dfs(i,j)$ 的值，并将其存入 $f[i][j]$。

时间复杂度 $O(n\times S)$，空间复杂度 $O(n\times S)$。其中 $n$ 和 $S$ 分别为 $rods$ 的长度和 $rods$ 中所有元素的和。

func tallestBillboard(rods []int) int {
	s := 0
	for _, x := range rods {
		s += x
	}
	n := len(rods)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, s+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= n {
			if j == 0 {
				return 0
			}
			return -(1 << 30)
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans := max(dfs(i+1, j), dfs(i+1, j+rods[i]))
		ans = max(ans, dfs(i+1, abs(j-rods[i]))+min(j, rods[i]))
		f[i][j] = ans
		return ans
	}
	return dfs(0, 0)
}

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

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

思考

搜索可改成自底向上： $f[i][j]$ 为前 $i$ 根、高度差 $j$ 的最大共同高度。转移与搜索相同，避免递归常数，答案为 $f[n][0]$。

我们定义 $f[i][j]$ 表示前 $i$ 根钢筋，两边高度差为 $j$ 时的最大共同高度。初始时 $f[0][0]=0$，其余 $f[i][j]=-\mathrm{\infty }$。我们求出所有 $rods[i]$ 的和，记为 $s$，那么 $j$ 的取值范围为 $[0,..s]$。

对于第 $i$ 根钢筋，我们可以不选择它，此时 $f[i][j]=f[i-1][j]$；也可以选择它，此时有三种情况：

1. 放置在原本高度较高的一边，即满足 $j\ge rods[i-1]$，此时 $f[i][j]=max(f[i][j],f[i-1][j-rods[i-1]])$；
2. 放置在原本高度较低的一遍，如果满足 $j+rods[i-1]\le s$，此时 $f[i][j]=max(f[i][j],f[i-1][j+rods[i-1]]+rods[i-1])$；如果满足 $j<rods[i-1]$，此时 $f[i][j]=max(f[i][j],f[i-1][rods[i-1]-j]+rods[i-1]-j)$。

综上，我们可以得到状态转移方程：

$$\begin{array}{rl}f[i][j]& =f[i-1][j]\\ f[i][j]& =max(f[i][j],f[i-1][j-rods[i-1]])& \mathit{\text{if }}j\ge rods[i-1]\\ f[i][j]& =max(f[i][j],f[i-1][j+rods[i-1]]+rods[i-1])& \mathit{\text{if }}j+rods[i-1]\le s\\ f[i][j]& =max(f[i][j],f[i-1][rods[i-1]-j]+rods[i-1]-j)& \mathit{\text{if }}j<rods[i-1]\end{array}$$

最终答案即为 $f[n][0]$。

时间复杂度 $O(n\times S)$，空间复杂度 $O(n\times S)$。其中 $n$ 和 $S$ 分别为 $rods$ 的长度和 $rods$ 中所有元素的和。

func tallestBillboard(rods []int) int {
	n := len(rods)
	s := 0
	for _, x := range rods {
		s += x
	}
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, s+1)
		for j := range f[i] {
			f[i][j] = -(1 << 30)
		}
	}
	f[0][0] = 0
	for i, t := 1, 0; i <= n; i++ {
		x := rods[i-1]
		t += x
		for j := 0; j <= t; j++ {
			f[i][j] = f[i-1][j]
			if j >= x {
				f[i][j] = max(f[i][j], f[i-1][j-x])
			}
			if j+x <= t {
				f[i][j] = max(f[i][j], f[i-1][j+x]+x)
			}
			if j < x {
				f[i][j] = max(f[i][j], f[i-1][x-j]+x-j)
			}
		}
	}
	return f[n][0]
}

力扣原题 · Doocs 题解来源

960. 删列造序 III

困难1 种解法

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

题目、示例与约束

给定由 n 个小写字母字符串组成的数组 strs ，其中每个字符串长度相等。

选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

比如，有 strs = ["abcdef","uvwxyz"] ，删除索引序列 {0, 2, 3} ，删除后为 ["bef", "vyz"] 。

假设，我们选择了一组删除索引 answer ，那么在执行删除操作之后，最终得到的数组的行中的 每个元素 都是按字典序排列的（即 (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) 和 (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) ，依此类推）。

请返回 answer.length 的最小可能值 。

 

示例 1：

输入：strs = ["babca","bbazb"]
输出：3
解释：
删除 0、1 和 4 这三列后，最终得到的数组是 strs = ["bc", "az"]。
这两行是分别按字典序排列的（即，strs[0][0] <= strs[0][1] 且 strs[1][0] <= strs[1][1]）。
注意，strs[0] > strs[1] —— 数组 strs 不一定是按字典序排列的。

示例 2：

输入：strs = ["edcba"]
输出：4
解释：如果删除的列少于 4 列，则剩下的行都不会按字典序排列。

示例 3：

输入：strs = ["ghi","def","abc"]
输出：0
解释：所有行都已按字典序排列。

 

提示：

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 100
• strs[i] 由小写英文字母组成

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

思考

可删任意列，使留下的列对每一行都非降，求最少删除。等价于在列下标上求最长“对所有行都非降”的子序列，删除数为 $n$ 减该长度。 $f[i]$ 以第 $i$ 列结尾，枚举 $j<i$ 且所有行 $s[j]\le s[i]$ 时转移。

我们定义 $f[i]$ 表示以第 $i$ 列结尾的最长不下降子序列的长度，初始时 $f[i]=1$，答案即为 $n-max(f)$。

考虑计算 $f[i]$，我们可以枚举 $j<i$，如果对于所有的字符串 $s$，有 $s[j]\le s[i]$，那么 $f[i]=max(f[i],f[j]+1)$。

最后，我们返回 $n-max(f)$。

时间复杂度 $O(n^2\times m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别是数组 $\mathit{\text{strs}}$ 每个字符串的长度和数组的长度。

func minDeletionSize(strs []string) int {
	n := len(strs[0])
	f := make([]int, n)
	for i := range f {
		f[i] = 1
	}
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			ok := true
			for _, s := range strs {
				if s[j] > s[i] {
					ok = false
					break
				}
			}
			if ok {
				f[i] = max(f[i], f[j]+1)
			}
		}
	}
	return n - slices.Max(f)
}

力扣原题 · Doocs 题解来源

964. 表示数字的最少运算符

困难1 种解法

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

题目、示例与约束

给定一个正整数 x，我们将会写出一个形如 x (op1) x (op2) x (op3) x ... 的表达式，其中每个运算符 op1，op2，… 可以是加、减、乘、除（+，-，*，或是 /）之一。例如，对于 x = 3，我们可以写出表达式 3 * 3 / 3 + 3 - 3，该式的值为 3 。

在写这样的表达式时，我们需要遵守下面的惯例：

• 除运算符（/）返回有理数。
• 任何地方都没有括号。
• 我们使用通常的操作顺序：乘法和除法发生在加法和减法之前。
• 不允许使用一元否定运算符（-）。例如，“x - x” 是一个有效的表达式，因为它只使用减法，但是 “-x + x” 不是，因为它使用了否定运算符。 

我们希望编写一个能使表达式等于给定的目标值 target 且运算符最少的表达式。返回所用运算符的最少数量。

 

示例 1：

输入：x = 3, target = 19
输出：5
解释：3 * 3 + 3 * 3 + 3 / 3 。表达式包含 5 个运算符。

示例 2：

输入：x = 5, target = 501
输出：8
解释：5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5 。表达式包含 8 个运算符。

示例 3：

输入：x = 100, target = 100000000
输出：3
解释：100 * 100 * 100 * 100 。表达式包含 3 个运算符。

 

提示：

• 2 <= x <= 100
• 1 <= target <= 2 * 108

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

思考

只用 $x$ 与四则运算凑出 $\mathit{\text{target}}$，运算符尽量少。 $x^k$ 是自然积木。 $v\le x$ 时用若干个 $x/x$ 加减即可。否则找到最小的 $k$ 使 $x^k\ge v$，在“先凑 $x^{k-1}$ 再补差”与“先凑 $x^k$ 再减去多余”（当多余小于 $v$）之间取优，记忆化搜索。

我们定义一个函数 $dfs(v)$，表示用 $x$ 凑成数字 $v$ 所需要的最少运算符数量。那么答案就是 $dfs(target)$。

函数 $dfs(v)$ 的执行逻辑如下：

如果 $x\ge v$，那么此时可以用 $v$ 个 $x/x$ 相加来得到 $v$，运算符数量为 $v\times 2-1$；也可以用 $x$ 减去 $(x-v)$ 个 $x/x$ 来得到 $v$，运算符数量为 $(x-v)\times 2$。取两者的最小值。

否则，我们从 $k=2$ 开始枚举 $x^k$，找到第一个 $x^k\ge v$ 的 $k$：

• 如果此时 $x^k-v\ge v$，那么只能先得到 $x^{k-1}$，然后再递归计算 $dfs(v-x^{k-1})$，此时运算符数量为 $k-1+dfs(v-x^{k-1})$；
• 如果此时 $x^k-v<v$，那么可以按照上面的方式得到 $v$，此时运算符数量为 $k-1+dfs(v-x^{k-1})$；也可以先得到 $x^k$，再递归计算 $dfs(x^k-v)$，此时运算符数量为 $k+dfs(x^k-v)$。取两者的最小值。

为了避免重复计算，我们使用记忆化搜索的方式实现 $dfs$ 函数。

时间复杂度 $O({\log }_{x}target)$，空间复杂度 $O({\log }_{x}target)$。

func leastOpsExpressTarget(x int, target int) int {
	f := map[int]int{}
	var dfs func(int) int
	dfs = func(v int) int {
		if x > v {
			return min(v*2-1, 2*(x-v))
		}
		if val, ok := f[v]; ok {
			return val
		}
		k := 2
		y := x * x
		for y < v {
			y *= x
			k++
		}
		ans := k - 1 + dfs(v-y/x)
		if y-v < v {
			ans = min(ans, k+dfs(y-v))
		}
		f[v] = ans
		return ans
	}
	return dfs(target)
}

力扣原题 · Doocs 题解来源