LeetCode Go · 动态规划（10）

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

来源与许可

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

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

1774. 最接近目标价格的甜点成本

中等1 种解法

标签：数组、动态规划、回溯、背包问题、混合背包

题目、示例与约束

你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：

• 必须选择 一种 冰激凌基料。
• 可以添加 一种或多种 配料，也可以不添加任何配料。
• 每种类型的配料 最多两份 。

给你以下三个输入：

• baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
• toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
• target ，一个整数，表示你制作甜点的目标价格。

你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。

 

示例 1：

输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
输出：10
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 7
- 选择 1 份 0 号配料：成本 1 x 3 = 3
- 选择 0 份 1 号配料：成本 0 x 4 = 0
总成本：7 + 3 + 0 = 10 。

示例 2：

输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
输出：17
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 3
- 选择 1 份 0 号配料：成本 1 x 4 = 4
- 选择 2 份 1 号配料：成本 2 x 5 = 10
- 选择 0 份 2 号配料：成本 0 x 100 = 0
总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。

示例 3：

输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
输出：8
解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。

示例 4：

输入：baseCosts = [10], toppingCosts = [1], target = 1
输出：10
解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。

 

提示：

• n == baseCosts.length
• m == toppingCosts.length
• 1 <= n, m <= 10
• 1 <= baseCosts[i], toppingCosts[i] <= 104
• 1 <= target <= 104

方法一：枚举子集和 + 排序 + 二分查找 · Go 实现

思考

基料必选一种，每种配料 $0/1/2$ 份，成本和尽量接近 $\mathit{\text{target}}$。配料种数很小，可枚举配料子集和。

把配料复制一份后 DFS 得到所有可达和并排序。枚举基料与一半子集和，在另一半里二分最接近 $\mathit{\text{target}}$ 的补齐，并列时取较小成本。

每种类型的配料最多可以选两份，因此，我们可以复制一份配料，然后利用 DFS 枚举子集之和。在实现上，我们可以只枚举一半的配料的所有子集和，然后在另一半配料子集和中，利用二分查找找到最接近的配料。

时间复杂度 $O(n\times 2^m\times \log 2^m)$。

相似题目：

• 1755. 最接近目标值的子序列和

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	arr := []int{}
	var dfs func(int, int)
	dfs = func(i, t int) {
		if i >= len(toppingCosts) {
			arr = append(arr, t)
			return
		}
		dfs(i+1, t)
		dfs(i+1, t+toppingCosts[i])
	}
	dfs(0, 0)
	sort.Ints(arr)
	const inf = 1 << 30
	ans, d := inf, inf
	// 选择一种冰激淋基料
	for _, x := range baseCosts {
		// 枚举子集和
		for _, y := range arr {
			// 二分查找
			i := sort.SearchInts(arr, target-x-y)
			for j := i - 1; j < i+1; j++ {
				if j >= 0 && j < len(arr) {
					t := abs(x + y + arr[j] - target)
					if d > t || (d == t && ans > x+y+arr[j]) {
						d = t
						ans = x + y + arr[j]
					}
				}
			}
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

1787. 使所有区间的异或结果为零

困难1 种解法

标签：位运算、数组、哈希表、动态规划、计数

题目、示例与约束

给你一个整数数组 nums​​​ 和一个整数 k​​​​​ 。区间 [left, right]（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。

返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。

 

示例 1：

输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]

示例 2：

输入：nums = [3,4,5,2,1,7,3,4,7], k = 3
输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]

示例 3：

输入：nums = [1,2,4,1,2,5,1,2,6], k = 3
输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]

 

提示：

• 1 <= k <= nums.length <= 2000
• ​​​​​​0 <= nums[i] < 210

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

思考

每个长 $k$ 的窗口异或为 $0$，推出 $nums[i]=nums[i+k]$，即答案以 $k$ 为周期，且一个周期异或为 $0$。值不超过 $2^{10}$，可按余数组 DP。

$f[j]$ 表示当前已处理的组异或为 $j$ 的最少修改。一组要么全改成新值（代价为组大小），要么改成组内已有的 $v$（省下 $cnt[v]$）。滚动到第 $k$ 组后取 $f[0]$。

注意到数组 nums 在修改之后，任意长度为 $k$ 的区间异或结果都等于 $0$，那么对于任意的 $i$，都有：

$$nums[i]\oplus nums[i+1]\oplus ...\oplus nums[i+k-1]=0$$

以及

$$nums[i+1]\oplus nums[i+2]\oplus ...\oplus nums[i+k]=0$$

结合上面两个等式以及异或运算的性质，可以得到 $nums[i]\oplus nums[i+k]=0$，即 $nums[i]=nums[i+k]$，我们发现，修改后的数组 nums 中的元素是以周期为 $k$ 的循环，对模 $k$ 同余的一组数必然只能取固定值，同时需要满足前 $k$ 个数异或结果为 $0$。

我们先对每一组 $i$ 进行计数，每一组的元素个数为 $size[i]$，每一组值为 $v$ 的元素个数为 $cnt[i][v]$。

接下来，我们可以用动态规划来求解。设 $f[i][j]$ 表示前 $i+1$ 组异或和为 $j$ 的最小修改次数。由于每一组的值只与前一组的值有关，因此我们可以用滚动数组优化空间复杂度。

重新定义 $f[j]$ 表示处理到当前组，且异或和为 $j$ 的最小修改次数。

状态转移时，有两种选择：一是将当前组的数全部都修改为同一个值，那么我们可以选择上一个代价最小的那个，加上这一组的元素个数 $size[i]$，此时的代价为 $minf[0..n]+size[i]$；二是将当前组的数全部修改为当前组的某个值 $j$，枚举 $j$ 以及当前组的元素 $v$，那么前面的代价为 $f[j\oplus v]$，此时的代价为 $f[j\oplus v]+size[i]-cnt[i][v]$。取最小值即可。

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

时间复杂度 $O(2^C\times k+n)$。其中 $n$ 是数组 nums 的长度，而 $C$ 为 nums 中元素二进制表示的最大位数，本题中 $C=10$。

func minChanges(nums []int, k int) int {
	n := 1 << 10
	cnt := make([]map[int]int, k)
	for i := range cnt {
		cnt[i] = map[int]int{}
	}
	size := make([]int, k)
	for i, v := range nums {
		cnt[i%k][v]++
		size[i%k]++
	}
	f := make([]int, n)
	for i := 1; i < n; i++ {
		f[i] = 0x3f3f3f3f
	}
	for i, sz := range size {
		g := make([]int, n)
		x := slices.Min(f) + sz
		for i := range g {
			g[i] = x
		}
		for j := 0; j < n; j++ {
			for v, c := range cnt[i] {
				g[j] = min(g[j], f[j^v]+sz-c)
			}
		}
		f = g
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

1799. N 次操作后的最大分数和

困难1 种解法

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

题目、示例与约束

给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。

在第 i 次操作时（操作编号从 1 开始），你需要：

• 选择两个元素 x 和 y 。
• 获得分数 i * gcd(x, y) 。
• 将 x 和 y 从 nums 中删除。

请你返回 n 次操作后你能获得的分数和最大为多少。

函数 gcd(x, y) 是 x 和 y 的最大公约数。

 

示例 1：

输入：nums = [1,2]
输出：1
解释：最优操作是：
(1 * gcd(1, 2)) = 1

示例 2：

输入：nums = [3,4,6,8]
输出：11
解释：最优操作是：
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

示例 3：

输入：nums = [1,2,3,4,5,6]
输出：14
解释：最优操作是：
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

 

提示：

• 1 <= n <= 7
• nums.length == 2 * n
• 1 <= nums[i] <= 106

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

思考

每次选两个剩余数，第 $i$ 次得分 $i\cdot gcd$。 $n\le 7$ 故 $m=2n\le 14$，可用子集 DP 枚举配对顺序。

预处理两两 $gcd$。 $f[k]$ 表示用掉掩码 $k$ 中元素的最大得分；仅当已用个数为偶数时，枚举一对 $i,j$ 从 $k$ 去掉它们并加上 $\mathit{\text{cnt}}/2\cdot g[i][j]$。

全部用完的 $f[2^m-1]$ 即为答案。

我们可以先预处理得到数组 nums 中任意两个数的最大公约数，存储在二维数组 $g$ 中，其中 $g[i][j]$ 表示 $nums[i]$ 和 $nums[j]$ 的最大公约数。

然后定义 $f[k]$ 表示当前操作后的状态为 $k$ 时，可以获得的最大分数和。假设 $m$ 为数组 nums 中的元素个数，那么状态一共有 $2^m$ 种，即 $k$ 的取值范围为 $[0,2^m-1]$。

从小到大枚举所有状态，对于每个状态 $k$，先判断此状态的二进制位中 $1$ 的个数 $cnt$ 是否为偶数，是则进行如下操作：

枚举 $k$ 中二进制位为 1 的位置，假设为 $i$ 和 $j$，则 $i$ 和 $j$ 两个位置的元素可以进行一次操作，此时可以获得的分数为 $\frac{cnt}{2}\times g[i][j]$，更新 $f[k]$ 的最大值。

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

时间复杂度 $O(2^m\times m^2)$，空间复杂度 $O(2^m)$。其中 $m$ 为数组 nums 中的元素个数。

func maxScore(nums []int) int {
	m := len(nums)
	g := [14][14]int{}
	for i := 0; i < m; i++ {
		for j := i + 1; j < m; j++ {
			g[i][j] = gcd(nums[i], nums[j])
		}
	}
	f := make([]int, 1<<m)
	for k := 0; k < 1<<m; k++ {
		cnt := bits.OnesCount(uint(k))
		if cnt%2 == 0 {
			for i := 0; i < m; i++ {
				if k>>i&1 == 1 {
					for j := i + 1; j < m; j++ {
						if k>>j&1 == 1 {
							f[k] = max(f[k], f[k^(1<<i)^(1<<j)]+cnt/2*g[i][j])
						}
					}
				}
			}
		}
	}
	return f[1<<m-1]
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

力扣原题 · Doocs 题解来源

1815. 得到新鲜甜甜圈的最多组数

困难1 种解法

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

题目、示例与约束

有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。

当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。

你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多 有多少组人会感到开心。

 

示例 1：

输入：batchSize = 3, groups = [1,2,3,4,5,6]
输出：4
解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。

示例 2：

输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出：4

 

提示：

• 1 <= batchSize <= 9
• 1 <= groups.length <= 30
• 1 <= groups[i] <= 109

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

思考

一组开心当且仅当轮到它时余下甜甜圈恰为 $0$，即此前人数之和能被 $\mathit{\text{batchSize}}$ 整除。组数不超过 $30$，穷举排列为 $30!$，不可行。

余数为 $0$ 的组不影响后续，可先全部计入答案。其余组只保留对 $\mathit{\text{batchSize}}$ 的余数；每个余数至多出现 $30$ 次，可用 $5$ 位计数，全部余数装进一个整数 $state$。记忆化 $dfs(state,mod)$ 枚举再安排一个余数，并在 $mod=0$ 时给当前组加一分。

题目实际上要我们找到一种安排顺序，使得前缀和（这里指的是“人数”）与 $batchSize$ 取模后为 $0$ 的组数最多。因此，我们可以将所有顾客按组分成两类：

• 人数为 $batchSize$ 的整数倍的顾客，这些顾客不会对下一组顾客的甜甜圈产生影响，我们可以贪心地优先安排这些组的顾客，那么这些组的顾客都会感到开心，“初始答案”为这些组的数量；
• 人数不为 $batchSize$ 的整数倍的顾客，这些顾客的安排顺序会影响下一组顾客的甜甜圈。我们可以对这里每一组的人数 $v$ 模 $batchSize$，得到的这些余数构成一个集合，集合中的元素值范围是 $[1,2...,batchSize-1]$。数组 $groups$ 的长度最大为 $30$，因此，每个余数的数量最大不超过 $30$。我们可以用 $5$ 个二进制位来表示一个余数的数量，而 $batchSize$ 最大为 $9$，那么表示这些余数以及对应的数量总共需要的二进制位就是 $5\times (9-1)=40$。我们可以用一个 $64$ 位整数 $state$ 来表示。

接下来，我们设计一个函数 $dfs(state,mod)$，表示安排状态为 $state$，且当前前缀余数为 $mod$ 时，能使得多少组感到开心。那么我们在“初始答案”加上 $dfs(state,0)$，即为最终答案。

函数 $dfs(state,mod)$ 的实现逻辑如下：

我们枚举 $1$ 到 $batchSize-1$ 的每一个余数 $i$，如果余数 $i$ 的数量不为 $0$，那么我们可以将余数 $i$ 的数量减去 $1$，将当前前缀余数加上 $i$ 并且对 $batchSize$ 取模，然后递归调用函数 $dfs$，求出子状态的最优解，取最大值即可。最后判断 $mod$ 是否为 $0$，如果为 $0$，我们在最大值上加 $1$ 后返回，否则直接返回最大值。

过程中，我们可以使用记忆化搜索来避免状态的重复计算。

时间复杂度不超过 $O({10}^7)$，空间复杂度不超过 $O({10}^6)$。

func maxHappyGroups(batchSize int, groups []int) (ans int) {
	state := 0
	for _, v := range groups {
		i := v % batchSize
		if i == 0 {
			ans++
		} else {
			state += 1 << (i * 5)
		}
	}
	f := map[int]int{}
	var dfs func(int, int) int
	dfs = func(state, mod int) int {
		if v, ok := f[state]; ok {
			return v
		}
		res := 0
		x := 0
		if mod == 0 {
			x = 1
		}
		for i := 1; i < batchSize; i++ {
			if state>>(i*5)&31 != 0 {
				t := dfs(state-1<<(i*5), (mod+i)%batchSize)
				res = max(res, t+x)
			}
		}
		f[state] = res
		return res
	}
	ans += dfs(state, 0)
	return
}

力扣原题 · Doocs 题解来源

1824. 最少侧跳次数

中等1 种解法

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

题目、示例与约束

给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

• 比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。

这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

• 比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。

这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

 

示例 1：

输入：obstacles = [0,1,2,3,0]
输出：2 
解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。

示例 2：

输入：obstacles = [0,1,1,3,3,0]
输出：0
解释：跑道 2 没有任何障碍，所以不需要任何侧跳。

示例 3：

输入：obstacles = [0,2,1,0,3,0]
输出：2
解释：最优方案如上图所示。总共有 2 次侧跳。

 

提示：

• obstacles.length == n + 1
• 1 <= n <= 5 * 105
• 0 <= obstacles[i] <= 3
• obstacles[0] == obstacles[n] == 0

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

思考

三条跑道上有障碍，只能在同一点侧跳，求到达终点的最少侧跳次数。若按位置与跑道搜索全部路径，状态虽为 $O(n)$，但若不记忆化会重复扩张。

定义 $f[j]$ 为当前点处于跑道 $j$ 的最少侧跳。有障碍的跑道置为无穷；其余跑道可沿原跑道前进，或先跳到当前点上花费最少的跑道再侧跳一次。滚动长度为 $3$ 的数组即可从起点推到终点。

我们定义 $f[i][j]$ 表示青蛙到达第 $i$ 个点，且处于第 $j$ 条跑道（下标从 $0$ 开始）的最小侧跳次数。

注意到青蛙起始位置处于第 $2$ 条跑道（题目这里下标从 $1$ 开始），因此 $f[0][1]$ 的值为 $0$，而 $f[0][0]$ 和 $f[0][2]$ 的值均为 $1$。答案为 $min(f[n][0],f[n][1],f[n][2])$

对于 $i$ 从 $1$ 到 $n$ 的每个位置，我们可以枚举青蛙当前所处的跑道 $j$，如果 $obstacles[i]=j+1$，说明第 $j$ 条跑道上有障碍，此时 $f[i][j]$ 的值为正无穷；否则，青蛙可以选择不跳跃，此时 $f[i][j]$ 的值为 $f[i-1][j]$，或者青蛙可以从其它跑道侧跳过来，此时 $f[i][j]=min(f[i][j],min(f[i][0],f[i][1],f[i][2])+1)$。

在代码实现上，我们可以将第一维空间优化掉，只用一个长度为 $3$ 的数组 $f$ 来维护。

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

func minSideJumps(obstacles []int) int {
	f := [3]int{1, 0, 1}
	const inf = 1 << 30
	for _, v := range obstacles[1:] {
		for j := 0; j < 3; j++ {
			if v == j+1 {
				f[j] = inf
				break
			}
		}
		x := min(f[0], min(f[1], f[2])) + 1
		for j := 0; j < 3; j++ {
			if v != j+1 {
				f[j] = min(f[j], x)
			}
		}
	}
	return min(f[0], min(f[1], f[2]))
}

力扣原题 · Doocs 题解来源

1866. 恰有 K 根木棍可以看到的排列数目

困难2 种解法

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

题目、示例与约束

有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。请你将这些木棍排成一排，并满足从左侧 可以看到 恰好 k 根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。

• 例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。

给你 n 和 k ，返回符合题目要求的排列 数目 。由于答案可能很大，请返回对 109 + 7 取余 的结果。

 

示例 1：

输入：n = 3, k = 2
输出：3
解释：[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。

示例 2：

输入：n = 5, k = 5
输出：1
解释：[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。

示例 3：

输入：n = 20, k = 11
输出：647427950
解释：总共有 647427950 (mod 109 + 7) 种能满足恰好有 11 根木棍可以看到的排列。

 

提示：

• 1 <= n <= 1000
• 1 <= k <= n

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

思考

从左侧能看到 $k$ 根的排列数，看见当且仅当它是到目前为止的最高。 $n\le 1000$，枚举排列不可行。

设 $f[i][j]$ 为 $i$ 根中恰看见 $j$ 根的方案。最长一根放在末尾则一定看见，前 $i-1$ 根看见 $j-1$ 根；否则末尾是其余 $i-1$ 种高度之一，看见数不变。按此递推到 $f[n][k]$。

我们定义 $f[i][j]$ 表示长度为 $i$ 的排列中，恰有 $j$ 根木棍可以看到的排列数目。初始时 $f[0][0]=1$，其余 $f[i][j]=0$。答案为 $f[n][k]$。

考虑最后一根木棍是否可以看到，如果可以看到，那么它一定是最长的，那么它的前面有 $i-1$ 根木棍，恰有 $j-1$ 根木棍可以看到，即 $f[i-1][j-1]$；如果最后一根木棍不可以看到，那么它可以是除了最长的木棍之外的任意一根，那么它的前面有 $i-1$ 根木棍，恰有 $j$ 根木棍可以看到，即 $f[i-1][j]\times (i-1)$。

因此，状态转移方程为：

$$f[i][j]=f[i-1][j-1]+f[i-1][j]\times (i-1)$$

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

时间复杂度 $O(n\times k)$，空间复杂度 $O(n\times k)$。其中 $n$ 和 $k$ 分别是题目中给定的两个整数。

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

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

思考

方法一的 $f[i][j]$ 只依赖上一行的 $j$ 与 $j-1$，二维数组可以压成一维。为避免覆盖尚未使用的 $f[j-1]$，内层按 $j$ 从大到小更新，空间降为 $O(k)$。

我们注意到 $f[i][j]$ 只跟 $f[i-1][j-1]$ 和 $f[i-1][j]$ 有关，因此可以使用一维数组优化空间复杂度。

时间复杂度 $O(n\times k)$，空间复杂度 $O(k)$。其中 $n$ 和 $k$ 分别是题目中给定的两个整数。

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

力扣原题 · Doocs 题解来源

1871. 跳跃游戏 VII

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 '0' 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

• i + minJump <= j <= min(i + maxJump, s.length - 1) 且
• s[j] == '0'.

如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。

 

示例 1：

输入：s = "011010", minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。

示例 2：

输入：s = "01101110", minJump = 2, maxJump = 3
输出：false

 

提示：

• 2 <= s.length <= 105
• s[i] 要么是 '0' ，要么是 '1'
• s[0] == '0'
• 1 <= minJump <= maxJump < s.length

方法一：前缀和 + 动态规划 · Go 实现

思考

从 $0$ 起只能跳到距离在 $[minJump,maxJump]$ 内的 '0'，问能否到达末尾。 $n\le {10}^5$，对每个位置再扫跳跃区间会超时。

$f[i]$ 表示 $i$ 可达，当且仅当 $s[i]{=}^{\prime }{0}^{\prime }$ 且区间 $[i-maxJump,i-minJump]$ 中存在可达点。用 $f$ 的前缀和在 $O(1)$ 内查询该区间，从左到右更新即可。

我们定义一个长度为 $n+1$ 的前缀和数组 $pre$，其中 $pre[i]$ 表示 $s$ 的前 $i$ 个位置中能够到达的个数。定义一个长度为 $n$ 的布尔数组 $f$，其中 $f[i]$ 表示 $s[i]$ 是否能够到达。初始时 $pre[1]=1$，而 $f[0]=true$。

考虑 $i\in [1,n)$，如果 $s[i]=0$，那么我们需要判断 $s$ 的前 $i$ 个位置中是否存在一个位置 $j$，满足 $j$ 能够到达且 $j$ 到 $i$ 的距离在 $[minJump,maxJump]$ 之间。如果存在这样的位置 $j$，那么我们就有 $f[i]=true$，否则 $f[i]=false$。在判断 $j$ 是否存在时，我们可以通过前缀和数组 $pre$ 在 $O(1)$ 的时间内判断是否存在这样的位置 $j$。

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

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

func canReach(s string, minJump int, maxJump int) bool {
	n := len(s)
	pre := make([]int, n+1)
	pre[1] = 1
	f := make([]bool, n)
	f[0] = true
	for i := 1; i < n; i++ {
		if s[i] == '0' {
			l, r := max(0, i-maxJump), i-minJump
			f[i] = l <= r && pre[r+1]-pre[l] > 0
		}
		pre[i+1] = pre[i]
		if f[i] {
			pre[i+1]++
		}
	}
	return f[n-1]
}

力扣原题 · Doocs 题解来源

1872. 石子游戏 VIII

困难2 种解法

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

题目、示例与约束

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：

1. 选择一个整数 x > 1 ，并且 移除 最左边的 x 个石子。
2. 将 移除 的石子价值之 和 累加到该玩家的分数中。
3. 将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。

当只剩下 一个 石子时，游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差，Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下，Alice 和 Bob 的 分数之差 。

 

示例 1：

输入：stones = [-1,2,-3,4,-5]
输出：5
解释：
- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。

示例 2：

输入：stones = [7,-6,5,10,5,-2,-6]
输出：13
解释：
- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。

示例 3：

输入：stones = [-10,-12]
输出：-22
解释：
- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。

 

提示：

• n == stones.length
• 2 <= n <= 105
• -104 <= stones[i] <= 104

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

思考

每次合并最左至少两堆，得分加上新的前缀和，双方都要最大化自己与对手的分差。 $n\le {10}^5$，不能搜索所有切分。

合并不改变前缀和数组 $s$。从下标 $i$ 开始，当前玩家可以取 $s[i]$ 并让对手面对 $i+1$，或把决策权继续右移。 $dfs(i)=max(dfs(i+1),s[i]-dfs(i+1))$，起点为 $i=1$（至少取前两堆）。记忆化后线性个状态。

根据题目描述，每次取走最左边的 $x$ 个石子，把它们的和加到自己的分数中，然后把一个价值为这个和的石子放在最左边，相当于把这 $x$ 个石子合并成了一个价值为这个和的石子，前缀和不变。

我们可以用一个长度为 $n$ 的前缀和数组 $s$ 来表示数组 $stones$ 的前缀和，其中 $s[i]$ 表示 $stones[0..i]$ 的元素和。

接下来，我们设计一个函数 $dfs(i)$，表示当前从 $stones[i:]$ 中取石子，返回当前玩家能得到的最大分数差。

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

• 如果 $i\ge n-1$，说明当前只能取走全部石子，因此返回 $s[n-1]$。
• 否则，我们可以选择从 $stones[i+1:]$ 中取走全部石子，得到的分数差为 $dfs(i+1)$；也可以选择取走 $stones[:i]$ 的石子，得到的分数差为 $s[i]-dfs(i+1)$。我们取两种情况中的最大值，即为当前玩家能得到的最大分数差。

最终，我们可以得到 Alice 和 Bob 的分数之差为 $dfs(1)$，即 $Alice$ 必须从 $stones[1:]$ 中取石子开始游戏。

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

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

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

方法三：前缀和 + 动态规划 · Go 实现

思考

每次合并最左至少两堆，得分加上新的前缀和，双方都要最大化自己与对手的分差。 $n\le {10}^5$，不能搜索所有切分。

从下标 $i$ 开始，当前玩家可以取 $s[i]$ 并让对手面对 $i+1$，或把决策继续右移。这个递推总会先调用 $i+1$，调用链长度为 $n$，栈会溢出。

下一格在从右往左走时已经就绪。令 $f[i]$ 为面对 $stones[i:]$ 的最大分差， $f[n-1]=s[n-1]$，从 $i=n-2$ 填到 $1$。

根据题目描述，每次取走最左边的 $x$ 个石子，把它们的和加到自己的分数中，然后把一个价值为这个和的石子放在最左边，相当于把这 $x$ 个石子合并成了一个价值为这个和的石子，前缀和不变。

我们可以用一个长度为 $n$ 的前缀和数组 $s$ 来表示数组 $stones$ 的前缀和，其中 $s[i]$ 表示 $stones[0..i]$ 的元素和。

令 $f[i]$ 表示当前从 $stones[i:]$ 中取石子时，当前玩家能得到的最大分数差。答案为 $f[1]$，因为 Alice 至少要取走前两堆。边界 $f[n-1]=s[n-1]$，此时只剩最后一堆，玩家只能取走它。

我们从 $i=n-2$ 填到 $1$。把决策继续右移，得到的分数差为 $f[i+1]$；取走 $stones[0..i]$ 得到 $s[i]$，对手面对 $f[i+1]$，当前分差为 $s[i]-f[i+1]$。取两者的较大值：

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

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

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

力扣原题 · Doocs 题解来源

1879. 两个数组最小的异或值之和

困难3 种解法

标签：位运算、数组、动态规划、位掩码、匈牙利算法、二分图、SSP 算法

题目、示例与约束

给你两个整数数组 nums1 和 nums2 ，它们长度都为 n 。

两个数组的 异或值之和 为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) （下标从 0 开始）。

• 比方说，[1,2,3] 和 [3,2,1] 的 异或值之和 等于 (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4 。

请你将 nums2 中的元素重新排列，使得 异或值之和 最小 。

请你返回重新排列之后的 异或值之和 。

 

示例 1：

输入：nums1 = [1,2], nums2 = [2,3]
输出：2
解释：将 nums2 重新排列得到 [3,2] 。
异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2 。

示例 2：

输入：nums1 = [1,0,3], nums2 = [5,3,4]
输出：8
解释：将 nums2 重新排列得到 [5,4,3] 。
异或值之和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8 。

 

提示：

• n == nums1.length
• n == nums2.length
• 1 <= n <= 14
• 0 <= nums1[i], nums2[i] <= 107

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

思考

将 $nums2$ 重排后与 $nums1$ 对应异或再求和，求最小值。 $n\le 14$，排列有 $n!$ 种，穷举偏紧，适合状压。

$f[i][j]$ 表示已配 $nums1$ 的前 $i$ 个、所用 $nums2$ 下标集合为 $j$ 的最小异或和。枚举 $j$ 中最后一个匹配的 $k$，由 $f[i-1][j\oplus 2^k]$ 转移。

我们注意到 $n\le 14$，因此，我们可以考虑使用状态压缩动态规划的方法求解本题。

我们用一个长度为 $n$ 的二进制数表示当前的状态，第 $i$ 位为 $1$ 表示 $nums2[i]$ 已经被选择，为 $0$ 表示 $nums2[i]$ 还未被选择。

我们定义 $f[i][j]$ 表示 $nums1$ 的前 $i$ 个数中，选择了 $nums2$ 的 $i$ 个数，且当前所选数字的状态为 $j$ 时，数组 $nums1$ 和 $nums2$ 的异或值之和的最小值。初始时 $f[0][0]=0$，其余 $f[i][j]=+\mathrm{\infty }$。

我们可以枚举 $nums1$ 的第 $i$ 个数 $x$，然后在 $[0,2^n)$ 的范围内枚举状态 $j$，转移方程为 $f[i][j]=min(f[i][j],f[i-1][j\oplus 2^k]+(x\oplus nums2[k]))$，其中 $k$ 是 $j$ 的二进制表示中的某个 $1$ 所在的位置。

最后答案为 $f[n][2^n-1]$。

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

func minimumXORSum(nums1 []int, nums2 []int) int {
	n := len(nums1)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, 1<<n)
		for j := range f[i] {
			f[i][j] = 1 << 30
		}
	}
	f[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := 0; j < 1<<n; j++ {
			for k := 0; k < n; k++ {
				if j>>k&1 == 1 {
					f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+(nums1[i-1]^nums2[k]))
				}
			}
		}
	}
	return f[n][(1<<n)-1]
}

方法二：状态压缩动态规划（枚举优化） · Go 实现

思考

方法一的三重循环里，状态 $j$ 的二进制 $1$ 的个数应等于 $i$，大量 $j$ 无效。可以去掉 $i$ 这一维，按 $nums1$ 的元素依次更新，并对 $j$ 逆序枚举，使转移用到的是上一轮的值，时间仍为 $O(n^2{2}^n)$ 但常系数更好。

我们也可以直接在 $[0,2^n)$ 范围内枚举状态 $i$，假设 $i$ 的二进制表示中有 $k$ 个 $1$，那么当前枚举的就是 $nums1$ 的第 $k$ 个数，下标为 $k-1$。状态转移方程为 $f[i]=min(f[i],f[i\oplus 2^j]+(nums1[k-1]\oplus nums2[j]))$，其中 $j$ 是 $i$ 的二进制表示中的某个 $1$ 所在的位置。

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

func minimumXORSum(nums1 []int, nums2 []int) int {
	n := len(nums1)
	f := make([]int, 1<<n)
	for i := range f {
		f[i] = 1 << 30
	}
	f[0] = 0
	for _, x := range nums1 {
		for j := (1 << n) - 1; j >= 0; j-- {
			for k := 0; k < n; k++ {
				if j>>k&1 == 1 {
					f[j] = min(f[j], f[j^(1<<k)]+(x^nums2[k]))
				}
			}
		}
	}
	return f[(1<<n)-1]
}

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

思考

也可以按掩码 $i$ 本身枚举：令 $k=i$ 中 $1$ 的个数减一，表示正在放置 $nums1[k]$，再枚举 $i$ 中的某一位作为所用的 $nums2[j]$。这样每个状态只处理一次，空间为 $O(2^n)$，时间为 $O(n{2}^n)$。

$f[i][j]$ 只与上一行有关，去掉第一维后用长度为 $2^n$ 的数组即可。

func minimumXORSum(nums1 []int, nums2 []int) int {
	n := len(nums1)
	f := make([]int, 1<<n)
	for i := range f {
		f[i] = 1 << 30
	}
	f[0] = 0
	for i := 0; i < 1<<n; i++ {
		k := bits.OnesCount(uint(i)) - 1
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				f[i] = min(f[i], f[i^1<<j]+(nums1[k]^nums2[j]))
			}
		}
	}
	return f[(1<<n)-1]
}

力扣原题 · Doocs 题解来源

1883. 准时抵达会议现场的最小跳过休息次数

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。

当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。

• 例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。

然而，为了能准时到达，你可以选择 跳过 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。

• 例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。

返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。

 

示例 1：

输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。

示例 2：

输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。

示例 3：

输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。

 

提示：

• n == dist.length
• 1 <= n <= 1000
• 1 <= dist[i] <= 105
• 1 <= speed <= 106
• 1 <= hoursBefore <= 107

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

思考

除最后一段外，每走完一条路若未整点则向上取整休息。可跳过若干次休息，求最少跳过次数使总时间不超过 $hoursBefore$。枚举跳过哪些路为指数级。

$f[i][j]$ 为走完前 $i$ 条路且跳过 $j$ 次的最短用时：不跳则对 $f[i-1][j]+d_i/s$ 向上取整，跳则直接累加。浮点取整用 $eps$ 修正。从 $j=0$ 起找第一个不超过时限的 $j$。

我们定义 $f[i][j]$ 表示考虑前 $i$ 条道路，恰好跳过 $j$ 次休息时间的最短用时。初始时 $f[0][0]=0$，其余 $f[i][j]=\mathrm{\infty }$。

由于我们可以选择跳过或者不跳过第 $i$ 条道路的休息时间，因此我们可以列出状态转移方程：

$$f[i][j]=min\{\begin{array}{rl}\lceil f[i-1][j]+\frac{d_i}{s}\rceil & \mathit{\text{不跳过第 }}i\mathit{\text{ 条道路的休息时间}}\\ f[i-1][j-1]+\frac{d_i}{s}& \mathit{\text{跳过第 }}i\mathit{\text{ 条道路的休息时间}}\end{array}$$

其中 $\lceil x\rceil$ 表示将 $x$ 向上取整。需要注意的是，由于我们需要保证恰好跳过 $j$ 次休息时间，因此我们必须有 $j\le i$；另外，如果 $j=0$，不能跳过任何休息时间。

由于浮点数运算以及向上取整运算可能会带来精度误差，因此我们引入一个常量 $eps={10}^{-8}$ 表示一个极小的正实数，在浮点数取整前先减去 $eps$，最后在比较 $f[n][j]$ 和 $hoursBefore$ 时，需要加上 $eps$。

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

func minSkips(dist []int, speed int, hoursBefore int) int {
	n := len(dist)
	f := make([][]float64, n+1)
	for i := range f {
		f[i] = make([]float64, n+1)
		for j := range f[i] {
			f[i][j] = 1e20
		}
	}
	f[0][0] = 0
	eps := 1e-8
	for i := 1; i <= n; i++ {
		for j := 0; j <= i; j++ {
			if j < i {
				f[i][j] = math.Min(f[i][j], math.Ceil(f[i-1][j]+float64(dist[i-1])/float64(speed)-eps))
			}
			if j > 0 {
				f[i][j] = math.Min(f[i][j], f[i-1][j-1]+float64(dist[i-1])/float64(speed))
			}
		}
	}
	for j := 0; j <= n; j++ {
		if f[n][j] <= float64(hoursBefore) {
			return j
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1884. 鸡蛋掉落-两枚鸡蛋

中等1 种解法

标签：数学、动态规划

题目、示例与约束

给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

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

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

 

示例 1：

输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。

示例 2：

输入：n = 100
输出：14
解释：
一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。

 

提示：

• 1 <= n <= 1000

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

思考

两枚鸡蛋测临界楼层，求最坏情况下最少次数。若第一枚从固定楼层扔起再线性扫，策略未必最优。 $n\le 1000$，可按层数 DP。

$f[i]$ 为 $i$ 层两枚蛋的最少次数。第一枚在相对第 $j$ 层扔下：碎则上面还需 $j-1$ 次线性测，不碎则下面变成 $f[i-j]$ 的子问题。对最坏情形取 $max$，再对 $j$ 取 $min$。

我们定义 $f[i]$ 表示有两枚鸡蛋，在 $i$ 层楼中确定 $f$ 的最小操作次数。初始时 $f[0]=0$，其余 $f[i]=+\mathrm{\infty }$。答案为 $f[n]$。

考虑 $f[i]$，我们可以枚举第一枚鸡蛋从第 $j$ 层楼扔下，其中 $1\le j\le i$，此时有两种情况：

• 鸡蛋碎了，此时我们剩余一枚鸡蛋，需要在 $j-1$ 层楼中确定 $f$，这需要 $j-1$ 次操作，因此总操作次数为 $1+(j-1)$；
• 鸡蛋没碎，此时我们剩余两枚鸡蛋，需要在 $i-j$ 层楼中确定 $f$，这需要 $f[i-j]$ 次操作，因此总操作次数为 $1+f[i-j]$。

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

$$f[i]=\underset{1\le j\le i}{min}\{1+max(j-1,f[i-j])\}$$

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

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

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

力扣原题 · Doocs 题解来源

1888. 使二进制字符串字符交替的最少反转次数

中等1 种解法

标签：字符串、动态规划、滑动窗口

题目、示例与约束

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

 

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

 

提示：

• 1 <= s.length <= 105
• s[i] 要么是 '0' ，要么是 '1' 。

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

思考

可把串看成环（类型 1 把首字符移到末尾），再翻转若干位变成交替串。枚举所有旋转再逐位比较为 $O(n^2)$， $n\le {10}^5$ 不可行。

目标只有 $0101\dots$ 与 $1010\dots$ 两种，且二者代价互补。把 $s+s$ 上长为 $n$ 的窗口看作一次旋转，滑动时增减两端与目标的差异，取 $min(cnt,n-cnt)$ 的最小值。

我们注意到，操作 $1$ 的作用实际上是让字符串成为一个环，而操作 $2$ 是使得环中的一段长度为 $n$ 的子串变成交替二进制串。

因此，我们只需要枚举每个长度为 $n$ 的子串，计算将其变成交替二进制串的代价，取最小值即可。

我们可以预先计算出字符串 $s$ 与两种交替二进制串的差异数量，记为 $\mathit{\text{cnt}}$，则将 $s$ 变成第一种交替二进制串的代价为 $\mathit{\text{cnt}}$，将 $s$ 变成第二种交替二进制串的代价为 $n-\mathit{\text{cnt}}$。我们初始化 $\mathit{\text{ans}}=min(\mathit{\text{cnt}},n-\mathit{\text{cnt}})$。

接下来，我们枚举每个长度为 $n$ 的子串，更新 $\mathit{\text{cnt}}$ 的值。对于每个位置 $i$，我们将 $s[i]$ 从第一种交替二进制串的差异数量中减去，并将 $s[i]$ 加入到第二种交替二进制串的差异数量中。更新 $\mathit{\text{ans}}=min(\mathit{\text{ans}},\mathit{\text{cnt}},n-\mathit{\text{cnt}})$。

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

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

func minFlips(s string) int {
	n := len(s)
	target := "01"
	cnt := 0
	for i := range s {
		if s[i] != target[i&1] {
			cnt++
		}
	}
	ans := min(cnt, n-cnt)
	for i := range s {
		if s[i] != target[i&1] {
			cnt--
		}
		if s[i] != target[(i+n)&1] {
			cnt++
		}
		ans = min(ans, min(cnt, n-cnt))
	}
	return ans
}

力扣原题 · Doocs 题解来源

1896. 反转表达式值的最少操作次数

困难1 种解法

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

题目、示例与约束

给你一个 有效的 布尔表达式，用字符串 expression 表示。这个字符串包含字符 '1'，'0'，'&'（按位 与 运算），'|'（按位 或 运算），'(' 和 ')' 。

• 比方说，"()1|1" 和 "(1)&()" 不是有效 布尔表达式。而 "1"， "(((1))|(0))" 和 "1|(0&(1))" 是 有效 布尔表达式。

你的目标是将布尔表达式的 值 反转 （也就是将 0 变为 1 ，或者将 1 变为 0），请你返回达成目标需要的 最少操作 次数。

• 比方说，如果表达式 expression = "1|1|(0&0)&1" ，它的 值 为 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1 。我们想要执行操作将 新的 表达式的值变成 0 。

可执行的 操作 如下：

• 将一个 '1' 变成一个 '0' 。
• 将一个 '0' 变成一个 '1' 。
• 将一个 '&' 变成一个 '|' 。
• 将一个 '|' 变成一个 '&' 。

注意：'&' 的 运算优先级 与 '|' 相同 。计算表达式时，括号优先级 最高 ，然后按照 从左到右 的顺序运算。

 

示例 1：

输入：expression = "1&(0|1)"
输出：1
解释：我们可以将 "1&(0|1)" 变成 "1&(0&1)" ，执行的操作为将一个 '|' 变成一个 '&' ，执行了 1 次操作。
新表达式的值为 0 。

示例 2：

输入：expression = "(0&0)&(0&0&0)"
输出：3
解释：我们可以将 "(0&0)&(0&0&0)" 变成 "(0|1)|(0&0&0)" ，执行了 3 次操作。
新表达式的值为 1 。

示例 3：

输入：expression = "(0|(1|0&1))"
输出：1
解释：我们可以将 "(0|(1|0&1))" 变成 "(0|(0|0&1))" ，执行了 1 次操作。
新表达式的值为 0 。

 

提示：

• 1 <= expression.length <= 105
• expression 只包含 '1'，'0'，'&'，'|'，'(' 和 ')'
• 所有括号都有与之匹配的对应括号。
• 不会有空的括号（也就是说 "()" 不是 expression 的子字符串）。

方法一 · Go 实现

思考

合法布尔表达式由 $0/1$、 $\mathrm{\&}$、 $|$ 与括号组成，一次操作可把数字或运算符改成另一种，求改变整个表达式值的最少次数。表达式长度达 ${10}^5$，不能对每种改法重新求值。

每个子表达式只需知道当前值，以及把它变成相反值的代价。叶子 $0/1$ 翻转为 $1$；两个子式用 $\mathrm{\&}$ 或 $|$ 连接时，可根据左右值与运算符分类讨论：改运算符、只改一侧或两侧。用栈按括号与优先级解析，自底向上合并即可。

每个子表达式记为二元组 $(\mathit{\text{val}},\mathit{\text{cost}})$：当前布尔值，以及把它改成相反值的最少操作次数。数字 $0/1$ 的翻转代价是 $1$。

$\mathrm{\&}$ 与 $|$ 优先级相同，按从左到右计算，括号优先。两个栈分别保存子表达式和运算符。读到运算符时，先把栈里已有的同级运算归约；读到右括号时，归约到对应的左括号。

设左右子式为 $(v_1,c_1)$、 $(v_2,c_2)$。

• 运算符是 $\mathrm{\&}$，两端都是 $1$：结果为 $1$，把其中一端改成 $0$，代价 $min(c_1,c_2)$。
• 两端都是 $0$：结果为 $0$。两端都改成 $1$ 的代价是 $c_1+c_2$；把 $\mathrm{\&}$ 改成 $|$ 并至少改一端的代价是 $1+min(c_1,c_2)$。
• 只有一端是 $0$：结果为 $0$。把这个 $0$ 改成 $1$，或把 $\mathrm{\&}$ 改成 $|$，取较小代价。
• 运算符是 $|$ 时，三种情况与上面对偶。

归约结束后，栈顶的 $\mathit{\text{cost}}$ 就是答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是表达式的长度。

func minOperationsToFlip(expression string) int {
	type pair struct{ val, cost int }
	nums := make([]pair, 0)
	ops := make([]byte, 0)
	merge := func(op byte) {
		b := nums[len(nums)-1]
		a := nums[len(nums)-2]
		nums = nums[:len(nums)-2]
		v1, c1, v2, c2 := a.val, a.cost, b.val, b.cost
		val, cost := 0, 0
		if op == '&' {
			val = v1 & v2
			if v1 == 1 && v2 == 1 {
				cost = min(c1, c2)
			} else if v1 == 0 && v2 == 0 {
				cost = min(c1+c2, 1+min(c1, c2))
			} else if v1 == 0 {
				cost = min(c1, 1)
			} else {
				cost = min(c2, 1)
			}
		} else {
			val = v1 | v2
			if v1 == 0 && v2 == 0 {
				cost = min(c1, c2)
			} else if v1 == 1 && v2 == 1 {
				cost = min(c1+c2, 1+min(c1, c2))
			} else if v1 == 1 {
				cost = min(c1, 1)
			} else {
				cost = min(c2, 1)
			}
		}
		nums = append(nums, pair{val, cost})
	}
	for i := 0; i < len(expression); i++ {
		c := expression[i]
		if c == '(' {
			ops = append(ops, c)
		} else if c == '0' || c == '1' {
			nums = append(nums, pair{int(c - '0'), 1})
		} else if c == '&' || c == '|' {
			for len(ops) > 0 && (ops[len(ops)-1] == '&' || ops[len(ops)-1] == '|') {
				merge(ops[len(ops)-1])
				ops = ops[:len(ops)-1]
			}
			ops = append(ops, c)
		} else {
			for ops[len(ops)-1] != '(' {
				merge(ops[len(ops)-1])
				ops = ops[:len(ops)-1]
			}
			ops = ops[:len(ops)-1]
		}
	}
	for len(ops) > 0 {
		merge(ops[len(ops)-1])
		ops = ops[:len(ops)-1]
	}
	return nums[0].cost
}

力扣原题 · Doocs 题解来源

1900. 最佳运动员的比拼回合

困难1 种解法

标签：记忆化、动态规划

题目、示例与约束

n 名运动员参与一场锦标赛，所有运动员站成一排，并根据 最开始的 站位从 1 到 n 编号（运动员 1 是这一排中的第一个运动员，运动员 2 是第二个运动员，依此类推）。

锦标赛由多个回合组成（从回合 1 开始）。每一回合中，这一排从前往后数的第 i 名运动员需要与从后往前数的第 i 名运动员比拼，获胜者将会进入下一回合。如果当前回合中运动员数目为奇数，那么中间那位运动员将轮空晋级下一回合。

• 例如，当前回合中，运动员 1, 2, 4, 6, 7 站成一排
  • 运动员 1 需要和运动员 7 比拼
  • 运动员 2 需要和运动员 6 比拼
  • 运动员 4 轮空晋级下一回合

每回合结束后，获胜者将会基于最开始分配给他们的原始顺序（升序）重新排成一排。

编号为 firstPlayer 和 secondPlayer 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前，完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时，其中任意一个都有获胜的可能，因此你可以 裁定 谁是这一回合的获胜者。

给你三个整数 n、firstPlayer 和 secondPlayer 。返回一个由两个值组成的整数数组，分别表示两位最佳运动员在本场锦标赛中比拼的 最早 回合数和 最晚 回合数。

 

示例 1：

输入：n = 11, firstPlayer = 2, secondPlayer = 4
输出：[3,4]
解释：
一种能够产生最早回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：2, 3, 4, 5, 6, 11
回合 3：2, 3, 4
一种能够产生最晚回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：1, 2, 3, 4, 5, 6
回合 3：1, 2, 4
回合 4：2, 4

示例 2：

输入：n = 5, firstPlayer = 1, secondPlayer = 5
输出：[1,1]
解释：两名最佳运动员 1 和 5 将会在回合 1 进行比拼。
不存在使他们在其他回合进行比拼的可能。

 

提示：

• 2 <= n <= 28
• 1 <= firstPlayer < secondPlayer <= n

方法一：记忆化搜索 + 二进制枚举 · Go 实现

思考

若按回合完整模拟淘汰赛，每一轮需在 $\lfloor n/2\rfloor$ 场对决中枚举胜负，状态随剩余人数指数增长，且 $n$ 最大为 $28$，直接搜索难以复用中间结果。

注意到两名指定选手以外的胜负，只影响下一轮他们的相对名次与剩余人数；一旦两人相遇即可终止。因此状态可压缩为 $(l,r,n)$，即当前序列中两人的下标与总人数。

为此对前半区用二进制枚举胜者，并强制 $l$、 $r$ 晋级，再按原顺序重编号后递归。记忆化后同一三元组只计算一次，最早与最晚回合分别取最小值与最大值加一。

我们定义一个函数 $\text{dfs}(l,r,n)$，表示在当前回合中，编号为 $l$ 和 $r$ 的运动员在 $n$ 名运动员中比拼的最早和最晚回合数。

函数 $\text{dfs}(l,r,n)$ 的执行逻辑如下：

1. 如果 $l+r=n-1$，说明两名运动员在当前回合中比拼，返回 $[1,1]$。
2. 如果 $f[l][r][n]\ne 0$，说明之前已经计算过这个状态，直接返回结果。
3. 初始化最早回合数为正无穷大，最晚回合数为负无穷大。
4. 计算当前回合中前半部分的运动员数目 $m=n/2$。
5. 枚举前半部分的所有可能的胜者组合（使用二进制枚举），对于每一种组合：
   • 根据当前组合确定哪些运动员获胜。
   • 确定当前回合中编号为 $l$ 和 $r$ 的运动员在当前回合中的位置。
   • 统计当前回合中编号为 $l$ 和 $r$ 的运动员在剩余运动员中的位置，记为 $a$ 和 $b$，以及剩余运动员的总数 $c$。
   • 递归调用 $\text{dfs}(a,b,c)$，获取当前状态的最早和最晚回合数。
   • 更新最早回合数和最晚回合数。
6. 将计算结果存储在 $f[l][r][n]$ 中，并返回最早和最晚回合数。

答案为 $\text{dfs}(\text{firstPlayer}-1,\text{secondPlayer}-1,n)$。

var f [30][30][31]int

func earliestAndLatest(n int, firstPlayer int, secondPlayer int) []int {
	return dfs(firstPlayer-1, secondPlayer-1, n)
}

func dfs(l, r, n int) []int {
	if f[l][r][n] != 0 {
		return decode(f[l][r][n])
	}
	if l+r == n-1 {
		f[l][r][n] = encode(1, 1)
		return []int{1, 1}
	}

	min, max := 1<<30, -1<<31
	m := n >> 1

	for i := 0; i < (1 << m); i++ {
		win := make([]bool, n)
		for j := 0; j < m; j++ {
			if (i>>j)&1 == 1 {
				win[j] = true
			} else {
				win[n-1-j] = true
			}
		}
		if n&1 == 1 {
			win[m] = true
		}
		win[n-1-l] = false
		win[n-1-r] = false
		win[l] = true
		win[r] = true

		a, b, c := 0, 0, 0
		for j := 0; j < n; j++ {
			if j == l {
				a = c
			}
			if j == r {
				b = c
			}
			if win[j] {
				c++
			}
		}

		t := dfs(a, b, c)
		if t[0]+1 < min {
			min = t[0] + 1
		}
		if t[1]+1 > max {
			max = t[1] + 1
		}
	}

	f[l][r][n] = encode(min, max)
	return []int{min, max}
}

func encode(x, y int) int {
	return (x << 8) | y
}

func decode(val int) []int {
	return []int{val >> 8, val & 255}
}

力扣原题 · Doocs 题解来源

1908. Nim 游戏 II 🔒

中等1 种解法

标签：位运算、脑筋急转弯、数组、数学、动态规划、博弈、Nim 游戏、无偏博弈

题目、示例与约束

Alice 和 Bob 交替进行一个游戏，由 Alice 先手。

在游戏中，共有 n 堆石头。在每个玩家的回合中，玩家需要 选择 任一非空石头堆，从中移除任意 非零 数量的石头。如果不能移除任意的石头，就输掉游戏，同时另一人获胜。

给定一个整数数组 piles ，piles[i] 为 第 i 堆石头的数量，如果 Alice 能获胜返回 true ，反之返回 false 。

Alice 和 Bob 都会采取 最优策略 。

 

示例 1：

输入：piles = [1]
输出：true
解释：只有一种可能的情况：
- 第一回合，Alice 移除了第 1 堆中 1 块石头。piles = [0]。
- 第二回合，Bob 没有任何石头可以移除。Alice 获胜。

示例 2：

输入：piles = [1,1]
输出：false
解释：可以证明，Bob一定能获胜。一种可能的情况：
- 第一回合，Alice 移除了第 1 堆中 1 块石头。 piles = [0,1]。
- 第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0]。
- 第三回合，Alice 没有任何石头可以移除。Bob 获胜。

示例 3：

输入：piles = [1,2,3]
输出：false
解释：可以证明，Bob一定能获胜。一种可能的情况：
- 第一回合，Alice 移除了第 3 堆中 3 块石头。 piles = [1,2,0]。
- 第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [1,1,0]。
- 第三回合，Alice 移除了第 1 堆中 1 块石头。piles = [0,1,0]。
- 第四回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0,0]。
- 第三回合，Alice 没有任何石头可以移除。Bob 获胜。

 

提示：

• n == piles.length
• 1 <= n <= 7
• 1 <= piles[i] <= 7

 

进阶：你能想出一个 线性时间 的解决方案吗？虽然这一答案可能超出了面试所需的范围，但了解它可能会很有趣。

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

思考

Nim 的必胜条件虽可用异或和刻画，但本题堆数与堆石子数均不超过 $7$，状态总数为 $7^7$，直接按博弈定义搜索即可验证。

一局为必胜，当且仅当存在一步使后手面对必败态。将各堆石子数做成元组作为状态，记忆化后枚举「选一堆并取走 $1$ 至全部」。

若所有后继皆为必胜，则当前必败。入口对初始元组调用即可。

我们发现，一共最多有 $7$ 堆石头，每堆石头最多有 $7$ 个，那么一共有 $7^7$ 种状态，因此我们可以用一个八进制数来表示当前的状态。

接下来，我们用记忆化搜索的方法来解决这个问题。定义一个函数 $dfs(piles)$，表示当前的状态为 $piles$ 时，当前玩家是否能获胜。

函数 $dfs(piles)$ 的执行过程如下：

• 如果 $piles$ 所表示的状态已经被计算过，直接返回结果；
• 否则，我们枚举每一堆石头，尝试移除 $1,2,3,...,x$ 个石头，如果移除后的状态 $pile{s}^{\prime }$ 不能获胜，那么当前玩家就能获胜，返回结果。
• 如果所有的移除方案都不能获胜，那么当前玩家不能获胜，返回结果。

时间复杂度 $O(7^7\times 7^2)$，空间复杂度 $O(7^7)$。

func nimGame(piles []int) bool {
	memo := map[int]bool{}
	p := make([]int, 8)
	p[0] = 1
	for i := 1; i < 8; i++ {
		p[i] = p[i-1] * 8
	}
	f := func(piles []int) int {
		st := 0
		for i, x := range piles {
			st += x * p[i]
		}
		return st
	}
	var dfs func(piles []int) bool
	dfs = func(piles []int) bool {
		st := f(piles)
		if v, ok := memo[st]; ok {
			return v
		}
		for i, x := range piles {
			for j := 1; j <= x; j++ {
				piles[i] -= j
				if !dfs(piles) {
					piles[i] += j
					memo[st] = true
					return true
				}
				piles[i] += j
			}
		}
		memo[st] = false
		return false
	}
	return dfs(piles)
}

力扣原题 · Doocs 题解来源

1911. 最大交替子序列和

中等2 种解法

标签：数组、动态规划

题目、示例与约束

一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。

• 比方说，数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。

给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从 0 开始编号）。

一个数组的 子序列 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列（加粗元素），但是 [2,4,2] 不是。

 

示例 1：

输入：nums = [4,2,5,3]
输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。

示例 2：

输入：nums = [5,6,7,8]
输出：8
解释：最优子序列为 [8] ，交替和为 8 。

示例 3：

输入：nums = [6,2,1,2,4,5]
输出：10
解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

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

思考

交替和按子序列中的奇偶位置加减。枚举所有子序列为指数级； $n\le {10}^5$ 必须线性递推。

记 $f[i]$ 为前 $i$ 个元素、末项处于奇数位（需减去）时的最大交替和， $g[i]$ 为末项处于偶数位（需加上）时的最大值。当前值 $x$ 要么接在另一奇偶之后，要么不选。

转移为 $f[i]=max(g[i-1]-x,f[i-1])$， $g[i]=max(f[i-1]+x,g[i-1])$，答案取二者在 $n$ 处的较大值。

我们定义 $f[i]$ 表示从前 $i$ 个元素中选出的子序列，且最后一个元素为奇数下标时的最大交替和，定义 $g[i]$ 表示从前 $i$ 个元素中选出的子序列，且最后一个元素为偶数下标时的最大交替和。初始时 $f[0]=g[0]=0$。答案为 $max(f[n],g[n])$。

我们考虑第 $i$ 个元素 $nums[i-1]$：

如果选取该元素且该元素为奇数下标，那么上一个元素必须为偶数下标，且只能从前 $i-1$ 个元素中选取，因此 $f[i]=g[i-1]-nums[i-1]$；如果不选取该元素，那么 $f[i]=f[i-1]$。

同理，如果选取该元素且该元素为偶数下标，那么上一个元素必须为奇数下标，且只能从前 $i-1$ 个元素中选取，因此 $g[i]=f[i-1]+nums[i-1]$；如果不选取该元素，那么 $g[i]=g[i-1]$。

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

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

最终答案为 $max(f[n],g[n])$。

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

func maxAlternatingSum(nums []int) int64 {
	n := len(nums)
	f := make([]int, n+1)
	g := make([]int, n+1)
	for i, x := range nums {
		i++
		f[i] = max(g[i-1]-x, f[i-1])
		g[i] = max(f[i-1]+x, g[i-1])
	}
	return int64(max(f[n], g[n]))
}

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

思考

相邻状态只依赖上一位置的 $f$、 $g$，数组可以压成两个变量，按从左到右同时更新，空间由 $O(n)$ 降为 $O(1)$。

$f[i]$ 和 $g[i]$ 只与上一位置有关，用两个变量滚动即可，空间复杂度 $O(1)$。

func maxAlternatingSum(nums []int) int64 {
	var f, g int
	for _, x := range nums {
		f, g = max(g-x, f), max(f+x, g)
	}
	return int64(max(f, g))
}

力扣原题 · Doocs 题解来源

1931. 用三种不同颜色为网格涂色

困难1 种解法

标签：动态规划、图的着色

题目、示例与约束

给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 109 + 7 取余 的结果。

 

示例 1：

输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。

示例 2：

输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。

示例 3：

输入：m = 5, n = 5
输出：580986

 

提示：

• 1 <= m <= 5
• 1 <= n <= 1000

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

思考

相邻格颜色必须不同。逐格涂色状态过多； $m\le 5$、 $n\le 1000$，一列只有 $3^m$ 种涂法，其中合法者更少。

先筛出列内相邻不同的掩码，再预处理两列对应位均不同的转移表。 $f[j]$ 表示上一列状态为 $j$ 的方案数，按列滚动相加。

首列只计合法掩码，其后 $n-1$ 轮转移，答案对所有状态求和并取模。

我们注意到，网格的行数不超过 $5$，那么一列中最多有 $3^5=243$ 种不同的颜色方案。

因此，我们定义 $f[i][j]$ 表示前 $i$ 列中，第 $i$ 列的涂色状态为 $j$ 的方案数。状态 $f[i][j]$ 由 $f[i-1][k]$ 转移而来，其中 $k$ 是第 $i-1$ 列的涂色状态，且 $k$ 和 $j$ 满足不同颜色相邻的要求。即：

$$f[i][j]=\sum _{k\in \mathit{\text{valid}}(j)}f[i-1][k]$$

其中 $\mathit{\text{valid}}(j)$ 表示状态 $j$ 的所有合法前驱状态。

最终的答案即为 $f[n][j]$ 的总和，其中 $j$ 是任意合法的状态。

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

时间复杂度 $O((m+n)\times 3^{2m})$，空间复杂度 $O(3^m)$。其中 $m$ 和 $n$ 分别是网格的行数和列数。

func colorTheGrid(m int, n int) (ans int) {
	f1 := func(x int) bool {
		last := -1
		for i := 0; i < m; i++ {
			if x%3 == last {
				return false
			}
			last = x % 3
			x /= 3
		}
		return true
	}
	f2 := func(x, y int) bool {
		for i := 0; i < m; i++ {
			if x%3 == y%3 {
				return false
			}
			x /= 3
			y /= 3
		}
		return true
	}
	mx := int(math.Pow(3, float64(m)))
	valid := map[int]bool{}
	f := make([]int, mx)
	for i := 0; i < mx; i++ {
		if f1(i) {
			valid[i] = true
			f[i] = 1
		}
	}
	d := map[int][]int{}
	for i := range valid {
		for j := range valid {
			if f2(i, j) {
				d[i] = append(d[i], j)
			}
		}
	}
	const mod int = 1e9 + 7
	for k := 1; k < n; k++ {
		g := make([]int, mx)
		for i := range valid {
			for _, j := range d[i] {
				g[i] = (g[i] + f[j]) % mod
			}
		}
		f = g
	}
	for _, x := range f {
		ans = (ans + x) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

1937. 扣分后的最大得分

中等1 种解法

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

题目、示例与约束

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分 减少 abs(c1 - c2) 。

请你返回你能得到的 最大 得分。

abs(x) 定义为：

• 如果 x >= 0 ，那么值为 x 。
• 如果 x < 0 ，那么值为 -x 。

 

示例 1：

输入：points = [[1,2,3],[1,5,1],[3,1,1]]
输出：9
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
你的总得分增加 3 + 5 + 3 = 11 。
但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
你的最终得分为 11 - 2 = 9 。

示例 2：

输入：points = [[1,5],[2,3],[4,2]]
输出：11
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。
你的总得分增加 5 + 3 + 4 = 12 。
但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。
你的最终得分为 12 - 1 = 11 。

 

提示：

• m == points.length
• n == points[r].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 0 <= points[r][c] <= 105

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

思考

每行恰选一格，相邻行列距计入罚分。若对上一行枚举列 $k$，单行已是 $O(n^2)$，总格数 ${10}^5$ 时不可行。

$f[j]+k$ 在 $k\le j$ 时与 $j$ 无关的部分可预计算：自左维护 $f[k]+k$ 的前缀最大，自右维护 $f[k]-k$ 的后缀最大，当前格 $O(1)$ 转移。

滚动一行数组，空间 $O(n)$，时间与格数线性。

我们定义 $f[i][j]$ 表示选取前 $i-1$ 行，并且第 $i-1$ 行选择第 $j$ 列的格子时的最大得分。初始时 $f[0][j]=points[0][j]$。

对于 $i>0$ 的情况，对于 $f[i][j]$，我们考虑是从上一行的哪一列转移过来的，记上一行选择的列为 $k$，那么有：

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

其中 $n$ 表示列数。答案为 $\underset{0\le j<n}{max}f[m-1][j]$。

我们注意到 $f[i]$ 的值只跟 $f[i-1]$ 的值有关，因此我们可以使用滚动数组优化空间复杂度。

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

func maxPoints(points [][]int) int64 {
	n := len(points[0])
	const inf int64 = 1e18
	f := make([]int64, n)
	for _, p := range points {
		g := make([]int64, n)
		lmx, rmx := -inf, -inf
		for j := range p {
			lmx = max(lmx, f[j]+int64(j))
			g[j] = max(g[j], int64(p[j])+lmx-int64(j))
		}
		for j := n - 1; j >= 0; j-- {
			rmx = max(rmx, f[j]-int64(j))
			g[j] = max(g[j], int64(p[j])+rmx+int64(j))
		}
		f = g
	}
	return slices.Max(f)
}

力扣原题 · Doocs 题解来源

1947. 最大兼容性评分和

中等1 种解法

标签：位运算、数组、动态规划、回溯、位掩码、匈牙利算法、二分图、图的匹配、最小费用流、SSP 算法、完美匹配、网络流

题目、示例与约束

有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。

这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i] 是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。导师的答案用一个二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。

每个学生都会被分配给 一名 导师，而每位导师也会分配到 一名 学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。

• 例如，学生答案为[1, 0, 1] 而导师答案为 [0, 0, 1] ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。

请你找出最优的学生与导师的配对方案，以 最大程度上 提高 兼容性评分和 。

给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。

 

示例 1：

输入：students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
输出：8
解释：按下述方式分配学生和导师：
- 学生 0 分配给导师 2 ，兼容性评分为 3 。
- 学生 1 分配给导师 0 ，兼容性评分为 2 。
- 学生 2 分配给导师 1 ，兼容性评分为 3 。
最大兼容性评分和为 3 + 2 + 3 = 8 。

示例 2：

输入：students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
输出：0
解释：任意学生与导师配对的兼容性评分都是 0 。

 

提示：

• m == students.length == mentors.length
• n == students[i].length == mentors[j].length
• 1 <= m, n <= 8
• students[i][k] 为 0 或 1
• mentors[j][k] 为 0 或 1

方法一：预处理 + 回溯 · Go 实现

思考

学生与导师一一匹配，最大化答案之和。 $m\le 8$，全排列 $8!$ 可接受，不必费用流。

先算每对学生与导师的相同题数 $g[i][j]$，再回溯分配未使用的导师，记录最大和。

$\mathit{\text{vis}}$ 避免重复占用，搜完 $m$ 个学生即更新答案。

我们可以先预处理出每个学生 $i$ 和导师 $j$ 之间的兼容性评分 $g[i][j]$，然后使用回溯算法求解。

定义一个函数 $\mathit{\text{dfs}}(i,s)$，其中 $i$ 表示当前处理到第 $i$ 个学生， $s$ 表示当前的兼容性评分和。

在 $\mathit{\text{dfs}}(i,s)$ 中，如果 $i\ge m$，表示所有学生都已经分配完毕，此时更新答案为 $max(\mathit{\text{ans}},s)$。否则，我们枚举第 $i$ 个学生可以分配给哪个导师，然后递归处理下一个学生。过程中，我们用一个数组 $\mathit{\text{vis}}$ 记录哪些导师已经被分配过，以避免重复分配。

我们调用 $\mathit{\text{dfs}}(0,0)$ 即可得到最大的兼容性评分和。

时间复杂度 $O(m!)$，空间复杂度 $O(m^2)$。其中 $m$ 为学生和导师的数量。

func maxCompatibilitySum(students [][]int, mentors [][]int) (ans int) {
	m, n := len(students), len(students[0])
	g := make([][]int, m)
	vis := make([]bool, m)
	for i, x := range students {
		g[i] = make([]int, m)
		for j, y := range mentors {
			for k := 0; k < n; k++ {
				if x[k] == y[k] {
					g[i][j]++
				}
			}
		}
	}
	var dfs func(int, int)
	dfs = func(i, s int) {
		if i == m {
			ans = max(ans, s)
			return
		}
		for j := 0; j < m; j++ {
			if !vis[j] {
				vis[j] = true
				dfs(i+1, s+g[i][j])
				vis[j] = false
			}
		}
	}
	dfs(0, 0)
	return
}

力扣原题 · Doocs 题解来源

1955. 统计特殊子序列的数目

困难2 种解法

标签：数组、动态规划

题目、示例与约束

特殊序列 是由 正整数 个 0 ，紧接着 正整数 个 1 ，最后 正整数 个 2 组成的序列。

• 比方说，[0,1,2] 和 [0,0,1,1,1,2] 是特殊序列。
• 相反，[2,1,0] ，[1] 和 [0,1,2,0] 就不是特殊序列。

给你一个数组 nums （仅 包含整数 0，1 和 2），请你返回 不同特殊子序列的数目 。由于答案可能很大，请你将它对 109 + 7 取余 后返回。

一个数组的 子序列 是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。如果两个子序列的 下标集合 不同，那么这两个子序列是 不同的 。

 

示例 1：

输入：nums = [0,1,2,2]
输出：3
解释：特殊子序列为 [0,1,2,2]，[0,1,2,2] 和 [0,1,2,2] 。

示例 2：

输入：nums = [2,2,0,0]
输出：0
解释：数组 [2,2,0,0] 中没有特殊子序列。

示例 3：

输入：nums = [0,1,2,0,1,2]
输出：7
解释：特殊子序列包括：
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 2

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

思考

特殊子序列为若干 $0$、若干 $1$、若干 $2$ 依次拼接。子序列个数指数级， $n\le {10}^5$ 必须按结尾数字计数。

$f[i][j]$ 表示前 $i$ 个元素中以 $j$ 结尾的特殊子序列数。遇 $0$ 可在旧的 $0$ 序列后追加或单开； $1$、 $2$ 同理只能接在前一阶段或同阶段之后。

模 ${10}^9+7$ 后答案为 $f[n-1][2]$。

我们定义 $f[i][j]$ 表示前 $i+1$ 个元素中，以 $j$ 结尾的特殊子序列的个数。初始时 $f[i][j]=0$，如果 $nums[0]=0$，则 $f[0][0]=1$。

对于 $i>0$，我们考虑 $nums[i]$ 的值：

如果 $nums[i]=0$：如果我们不选择 $nums[i]$，则 $f[i][0]=f[i-1][0]$；如果我们选择 $nums[i]$，那么 $f[i][0]=f[i-1][0]+1$，因为我们可以在任何一个以 $0$ 结尾的特殊子序列后面加上一个 $0$ 得到一个新的特殊子序列，也可以将 $nums[i]$ 单独作为一个特殊子序列。因此 $f[i][0]=2\times f[i-1][0]+1$。其余的 $f[i][j]$ 与 $f[i-1][j]$ 相等。

如果 $nums[i]=1$：如果我们不选择 $nums[i]$，则 $f[i][1]=f[i-1][1]$；如果我们选择 $nums[i]$，那么 $f[i][1]=f[i-1][1]+f[i-1][0]$，因为我们可以在任何一个以 $0$ 或 $1$ 结尾的特殊子序列后面加上一个 $1$ 得到一个新的特殊子序列。因此 $f[i][1]=f[i-1][0]+2\times f[i-1][1]$。其余的 $f[i][j]$ 与 $f[i-1][j]$ 相等。

如果 $nums[i]=2$：如果我们不选择 $nums[i]$，则 $f[i][2]=f[i-1][2]$；如果我们选择 $nums[i]$，那么 $f[i][2]=f[i-1][2]+f[i-1][1]$，因为我们可以在任何一个以 $1$ 或 $2$ 结尾的特殊子序列后面加上一个 $2$ 得到一个新的特殊子序列。因此 $f[i][2]=f[i-1][1]+2\times f[i-1][2]$。其余的 $f[i][j]$ 与 $f[i-1][j]$ 相等。

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

$$\begin{array}{rl}f[i][0]& =2\times f[i-1][0]+1,nums[i]=0\\ f[i][1]& =f[i-1][0]+2\times f[i-1][1],nums[i]=1\\ f[i][2]& =f[i-1][1]+2\times f[i-1][2],nums[i]=2\\ f[i][j]& =f[i-1][j],nums[i]\ne j\end{array}$$

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

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

func countSpecialSubsequences(nums []int) int {
	const mod = 1e9 + 7
	n := len(nums)
	f := make([][3]int, n)
	if nums[0] == 0 {
		f[0][0] = 1
	}
	for i := 1; i < n; i++ {
		if nums[i] == 0 {
			f[i][0] = (2*f[i-1][0] + 1) % mod
			f[i][1] = f[i-1][1]
			f[i][2] = f[i-1][2]
		} else if nums[i] == 1 {
			f[i][0] = f[i-1][0]
			f[i][1] = (f[i-1][0] + 2*f[i-1][1]) % mod
			f[i][2] = f[i-1][2]
		} else {
			f[i][0] = f[i-1][0]
			f[i][1] = f[i-1][1]
			f[i][2] = (f[i-1][1] + 2*f[i-1][2]) % mod
		}
	}
	return f[n-1][2]
}

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

思考

转移只读上一行三个状态，可压成长度为 $3$ 的数组原地更新，空间降为常数。

我们注意到，上述的状态转移方程中， $f[i][j]$ 的值仅与 $f[i-1][j]$ 有关，因此我们可以去掉第一维，将空间复杂度优化到 $O(1)$。

func countSpecialSubsequences(nums []int) int {
	const mod = 1e9 + 7
	n := len(nums)
	f := [3]int{}
	if nums[0] == 0 {
		f[0] = 1
	}
	for i := 1; i < n; i++ {
		if nums[i] == 0 {
			f[0] = (2*f[0] + 1) % mod
		} else if nums[i] == 1 {
			f[1] = (f[0] + 2*f[1]) % mod
		} else {
			f[2] = (f[1] + 2*f[2]) % mod
		}
	}
	return f[2]
}

力扣原题 · Doocs 题解来源

1959. K 次调整数组大小浪费的最小总空间

中等1 种解法

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

题目、示例与约束

你正在设计一个动态数组。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 i 时刻数组中的元素数目。除此以外，你还有一个整数 k ，表示你可以 调整 数组大小的 最多 次数（每次都可以调整成 任意 大小）。

t 时刻数组的大小 sizet 必须大于等于 nums[t] ，因为数组需要有足够的空间容纳所有元素。t 时刻 浪费的空间 为 sizet - nums[t] ，总 浪费空间为满足 0 <= t < nums.length 的每一个时刻 t 浪费的空间 之和 。

在调整数组大小不超过 k 次的前提下，请你返回 最小总浪费空间 。

注意：数组最开始时可以为 任意大小 ，且 不计入 调整大小的操作次数。

 

示例 1：

输入：nums = [10,20], k = 0
输出：10
解释：size = [20,20].
我们可以让数组初始大小为 20 。
总浪费空间为 (20 - 10) + (20 - 20) = 10 。

示例 2：

输入：nums = [10,20,30], k = 1
输出：10
解释：size = [20,20,30].
我们可以让数组初始大小为 20 ，然后时刻 2 调整大小为 30 。
总浪费空间为 (20 - 10) + (20 - 20) + (30 - 30) = 10 。

示例 3：

输入：nums = [10,20,15,30,20], k = 2
输出：15
解释：size = [10,20,20,30,30].
我们可以让数组初始大小为 10 ，时刻 1 调整大小为 20 ，时刻 3 调整大小为 30 。
总浪费空间为 (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15 。

 

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 106
• 0 <= k <= nums.length - 1

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

思考

$k$ 次改容量等价于把数组切成 $k+1$ 段，每段浪费为「段内最大值乘长度减元素和」。枚举所有切法为指数级， $n\le 200$ 可用区间 DP。

先 $O(n^2)$ 预处理每段浪费 $g[i][j]$，再令 $f[i][j]$ 为前 $i$ 个元素分成 $j$ 段的最小浪费，枚举上一段终点转移。

答案 $f[n][k+1]$。

题目等价于我们将数组 $\mathit{\text{nums}}$ 分成 $k+1$ 段，那么每一段的浪费空间为该段的最大值乘以该段的长度减去该段的元素之和。我们累加每一段的浪费空间，即可得到总浪费空间。我们将 $k$ 加 $1$，那么就相当于将数组分成 $k$ 段。

因此，我们定义数组 $\mathit{\text{g}}[i][j]$ 表示 $\mathit{\text{nums}}[i..j]$ 的最大值乘以 $\mathit{\text{nums}}[i..j]$ 的长度减去 $\mathit{\text{nums}}[i..j]$ 的元素之和。我们在 $[0,n)$ 的范围内枚举 $i$，在 $[i,n)$ 的范围内枚举 $j$，用一个变量 $s$ 维护 $\mathit{\text{nums}}[i..j]$ 的元素之和，用一个变量 $\mathit{\text{mx}}$ 维护 $\mathit{\text{nums}}[i..j]$ 的最大值，那么我们可以得到：

$$\mathit{\text{g}}[i][j]=\mathit{\text{mx}}\times (j-i+1)-s$$

接下来，我们定义 $\mathit{\text{f}}[i][j]$ 表示前 $i$ 个元素分成 $j$ 段的最小浪费空间。我们初始化 $\mathit{\text{f}}[0][0]=0$，其余位置初始化为无穷大。我们在 $[1,n]$ 的范围内枚举 $i$，在 $[1,k]$ 的范围内枚举 $j$，然后我们枚举前 $j-1$ 段的最后一个元素 $h$，那么有：

$$\mathit{\text{f}}[i][j]=min(\mathit{\text{f}}[i][j],\mathit{\text{f}}[h][j-1]+\mathit{\text{g}}[h][i-1])$$

最终答案为 $\mathit{\text{f}}[n][k]$。

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

func minSpaceWastedKResizing(nums []int, k int) int {
	k++
	n := len(nums)
	g := make([][]int, n)
	for i := range g {
		g[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		s, mx := 0, 0
		for j := i; j < n; j++ {
			s += nums[j]
			mx = max(mx, nums[j])
			g[i][j] = mx*(j-i+1) - s
		}
	}
	f := make([][]int, n+1)
	inf := 0x3f3f3f3f
	for i := range f {
		f[i] = make([]int, k+1)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := 1; j <= k; j++ {
			for h := 0; h < i; h++ {
				f[i][j] = min(f[i][j], f[h][j-1]+g[h][i-1])
			}
		}
	}
	return f[n][k]
}

力扣原题 · Doocs 题解来源

1977. 划分数字的方案数

困难1 种解法

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

题目、示例与约束

你写下了若干 正整数 ，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是 非递减 的且 没有 任何数字有前导 0 。

请你返回有多少种可能的 正整数数组 可以得到字符串 num 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：num = "327"
输出：2
解释：以下为可能的方案：
3, 27
327

示例 2：

输入：num = "094"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。

示例 3：

输入：num = "0"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。

示例 4：

输入：num = "9999999999999"
输出：101

 

提示：

• 1 <= num.length <= 3500
• num 只含有数字 '0' 到 '9' 。

方法一：动态规划 + 前缀和 · Go 实现

思考

把数字串切成相邻非降、无前导零的整数。枚举全部切分指数级， $n\le 3500$ 需 $O(n^2)$ DP。

$dp[i][j]$ 为前 $i$ 位、末段长 $j$ 的方案。更短的前一段一定更小，可用前缀和一次加上；等长时用 LCP 比较大小再决定是否转移。

$dp[i][j]$ 同时存前缀和，答案为 $dp[n][n]$。

定义 $dp[i][j]$ 表示字符串 num 的前 $i$ 个字符，且最后一个数字的长度为 $j$ 时的方案数。显然答案为 $\sum _{j=0}^{n}dp[n][j]$。初始值 $dp[0][0]=1$。

对于 $dp[i][j]$，对应的上一个数的结尾应该是 $i-j$，我们可以枚举 $dp[i-j][k]$，其中 $k\le j$。对于 $k<j$ 的部分，即长度小于 $j$ 的方案数可以直接加给 $dp[i][j]$，即 $dp[i][j]=\sum _{k=0}^{j-1}dp[i-j][k]$。因为前一个数字更短，也就意味着它比当前数更小。这里可以用前缀和优化。

但是当 $k=j$ 时，我们需要判断同样长度的两个数字的大小关系。如果前一个数字比当前数字大，那么这种情况是不合法的，我们不应该将其加给 $dp[i][j]$。否则，我们可以将其加给 $dp[i][j]$。这里我们可以先用 $O(n^2)$ 的时间预处理得到“最长公共前缀”，然后用 $O(1)$ 的时间判断两个同样长度的数字的大小关系。

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

func numberOfCombinations(num string) int {
	n := len(num)
	lcp := make([][]int, n+1)
	dp := make([][]int, n+1)
	for i := range lcp {
		lcp[i] = make([]int, n+1)
		dp[i] = make([]int, n+1)
	}
	for i := n - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if num[i] == num[j] {
				lcp[i][j] = 1 + lcp[i+1][j+1]
			}
		}
	}
	cmp := func(i, j, k int) bool {
		x := lcp[i][j]
		return x >= k || num[i+x] >= num[j+x]
	}
	dp[0][0] = 1
	var mod int = 1e9 + 7
	for i := 1; i <= n; i++ {
		for j := 1; j <= i; j++ {
			v := 0
			if num[i-j] != '0' {
				if i-j-j >= 0 && cmp(i-j, i-j-j, j) {
					v = dp[i-j][j]
				} else {
					v = dp[i-j][min(j-1, i-j)]
				}
			}
			dp[i][j] = (dp[i][j-1] + v) % mod
		}
	}
	return dp[n][n]
}

力扣原题 · Doocs 题解来源

1981. 最小化目标值与所选元素的差

中等1 种解法

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

题目、示例与约束

给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。

从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。

返回 最小的绝对差 。

a 和 b 两数字的 绝对差 是 a - b 的绝对值。

 

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
输出：0
解释：一种可能的最优选择方案是：
- 第一行选出 1
- 第二行选出 5
- 第三行选出 7
所选元素的和是 13 ，等于目标值，所以绝对差是 0 。

示例 2：

输入：mat = [[1],[2],[3]], target = 100
输出：94
解释：唯一一种选择方案是：
- 第一行选出 1
- 第二行选出 2
- 第三行选出 3
所选元素的和是 6 ，绝对差是 94 。

示例 3：

输入：mat = [[1,2,9,8,7]], target = 6
输出：1
解释：最优的选择方案是选出第一行的 7 。
绝对差是 1 。

 

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 70
• 1 <= mat[i][j] <= 70
• 1 <= target <= 800

方法一：动态规划（分组背包） · Go 实现

思考

每行选一个数，使总和与 $\mathit{\text{target}}$ 的绝对差最小。指数枚举不可行；每行元素 $\le 70$，行数 $\le 70$，可达和可用集合滚动。

$f$ 为已选行之和的集合，新行对每个旧和加上该行每个值。最后在集合中取与 $\mathit{\text{target}}$ 最近者。

去重后状态远小于朴素乘积。

设 $f[i][j]$ 表示前 $i$ 行是否能选出元素和为 $j$，则有状态转移方程：

$$f[i][j]=\{\begin{array}{ll}1& \mathit{\text{如果存在 }}x\in row[i]\mathit{\text{ 使得 }}f[i-1][j-x]=1\\ 0& \mathit{\text{否则}}\end{array}$$

其中 $row[i]$ 表示第 $i$ 行的元素集合。

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

最后，遍历 $f$ 数组，找出最小的绝对差即可。

时间复杂度 $O(m^2\times n\times C)$，空间复杂度 $O(m\times C)$。其中 $m$ 和 $n$ 分别为矩阵的行数和列数；而 $C$ 为矩阵元素的最大值。

func minimizeTheDifference(mat [][]int, target int) int {
	f := []int{1}
	for _, row := range mat {
		mx := slices.Max(row)
		g := make([]int, len(f)+mx)
		for _, x := range row {
			for j := x; j < len(f)+x; j++ {
				g[j] |= f[j-x]
			}
		}
		f = g
	}
	ans := 1 << 30
	for j, v := range f {
		if v == 1 {
			ans = min(ans, abs(j-target))
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

1986. 完成任务的最少工作时间段

中等1 种解法

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

题目、示例与约束

你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。一个 工作时间段 中，你可以 至多 连续工作 sessionTime 个小时，然后休息一会儿。

你需要按照如下条件完成给定任务：

• 如果你在某一个时间段开始一个任务，你需要在 同一个 时间段完成它。
• 完成一个任务后，你可以 立马 开始一个新的任务。
• 你可以按 任意顺序 完成任务。

给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的 最少 数目的 工作时间段 。

测试数据保证 sessionTime 大于等于 tasks[i] 中的 最大值 。

 

示例 1：

输入：tasks = [1,2,3], sessionTime = 3
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
- 第二个工作时间段：完成第三个任务，花费 3 小时。

示例 2：

输入：tasks = [3,1,3,1,1], sessionTime = 8
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。
- 第二个工作时间段，完成最后一个任务，花费 1 小时。

示例 3：

输入：tasks = [1,2,3,4,5], sessionTime = 15
输出：1
解释：你可以在一个工作时间段以内完成所有任务。

 

提示：

• n == tasks.length
• 1 <= n <= 14
• 1 <= tasks[i] <= 10
• max(tasks[i]) <= sessionTime <= 15

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

思考

任务分配到若干容量为 $\mathit{\text{sessionTime}}$ 的时间段，段数最少。 $n\le 14$，子集 DP 可行。

先标记哪些子集能装进一段，再枚举状态 $i$ 的子集 $j$：若 $j$ 合法则 $f[i]=min(f[i\oplus j]+1)$。

全集的 $f$ 即为最少段数。

我们注意到 $n$ 不超过 $14$，因此，我们可以考虑使用状态压缩动态规划的方法求解本题。

我们用一个长度为 $n$ 的二进制数 $i$ 来表示当前的任务状态，其中 $i$ 的第 $j$ 位为 $1$，当且仅当第 $j$ 个任务被完成。我们用 $f[i]$ 表示完成状态为 $i$ 的所有任务所需要的最少工作时间段数。

我们可以枚举 $i$ 的所有子集 $j$，其中 $j$ 的二进制表示中的每一位都是 $i$ 的二进制表示中对应位的子集，即 $j\subseteq i$。如果 $j$ 对应的任务可以在一个工作时间段内完成，那么我们可以用 $f[i\oplus j]+1$ 来更新 $f[i]$，其中 $i\oplus j$ 表示 $i$ 和 $j$ 的按位异或。

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

时间复杂度 $O(n\times 3^n)$，空间复杂度 $O(2^n)$。其中 $n$ 为任务的数量。

func minSessions(tasks []int, sessionTime int) int {
	n := len(tasks)
	ok := make([]bool, 1<<n)
	f := make([]int, 1<<n)
	for i := 1; i < 1<<n; i++ {
		t := 0
		f[i] = 1 << 30
		for j, x := range tasks {
			if i>>j&1 == 1 {
				t += x
			}
		}
		ok[i] = t <= sessionTime
	}
	for i := 1; i < 1<<n; i++ {
		for j := i; j > 0; j = (j - 1) & i {
			if ok[j] {
				f[i] = min(f[i], f[i^j]+1)
			}
		}
	}
	return f[1<<n-1]
}

力扣原题 · Doocs 题解来源

1987. 不同的好子序列数目

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给你一个二进制字符串 binary 。 binary 的一个 子序列 如果是 非空 的且没有 前导 0 （除非数字是 "0" 本身），那么它就是一个 好 的子序列。

请你找到 binary 不同好子序列 的数目。

• 比方说，如果 binary = "001" ，那么所有 好 子序列为 ["0", "0", "1"] ，所以 不同 的好子序列为 "0" 和 "1" 。 注意，子序列 "00" ，"01" 和 "001" 不是好的，因为它们有前导 0 。

请你返回 binary 中 不同好子序列 的数目。由于答案可能很大，请将它对 109 + 7 取余 后返回。

一个 子序列 指的是从原数组中删除若干个（可以一个也不删除）元素后，不改变剩余元素顺序得到的序列。

 

示例 1：

输入：binary = "001"
输出：2
解释：好的二进制子序列为 ["0", "0", "1"] 。
不同的好子序列为 "0" 和 "1" 。

示例 2：

输入：binary = "11"
输出：2
解释：好的二进制子序列为 ["1", "1", "11"] 。
不同的好子序列为 "1" 和 "11" 。

示例 3：

输入：binary = "101"
输出：5
解释：好的二进制子序列为 ["1", "0", "1", "10", "11", "101"] 。
不同的好子序列为 "0" ，"1" ，"10" ，"11" 和 "101" 。

 

提示：

• 1 <= binary.length <= 105
• binary 只含有 '0' 和 '1' 。

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

思考

好子序列不以 $0$ 开头（单独的 $0$ 除外）。不同子序列若按集合计数，需避免重复拼接。

$f$ 统计以 $1$ 结尾、 $g$ 统计以 $1$ 开头且以 $0$ 结尾的不同串。遇 $0$ 时旧串均可补 $0$ 更新 $g$；遇 $1$ 时可补在 $f$、 $g$ 之后或单开。

若出现过 $0$，答案再加单独的 $0$。

我们定义 $f$ 表示以 $1$ 结尾的不同好子序列的数目，定义 $g$ 表示以 $0$ 结尾的且以 $1$ 开头的不同好子序列的数目。初始时 $f=g=0$。

对于一个二进制字符串，我们可以从左到右遍历每一位，假设当前位为 $c$，那么：

• 如果 $c=0$，那么我们可以在 $f$ 和 $g$ 个不同的好子序列拼上 $c$，因此更新 $g=(g+f)mod({10}^9+7)$；
• 如果 $c=1$，那么我们可以在 $f$ 和 $g$ 个不同的好子序列拼上 $c$，同时还可以单独拼上 $c$，因此更新 $f=(f+g+1)mod({10}^9+7)$。

如果字符串包含 $0$，那么最终答案为 $f+g+1$，否则答案为 $f+g$。

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

相似题目：

• 940. 不同的子序列 II

func numberOfUniqueGoodSubsequences(binary string) (ans int) {
	const mod int = 1e9 + 7
	f, g := 0, 0
	for _, c := range binary {
		if c == '0' {
			g = (g + f) % mod
			ans = 1
		} else {
			f = (f + g + 1) % mod
		}
	}
	ans = (ans + f + g) % mod
	return
}

力扣原题 · Doocs 题解来源

1994. 好子集的数目

困难1 种解法

标签：位运算、数组、哈希表、数学、动态规划、位掩码、计数、数论、筛法

题目、示例与约束

给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。

• 比方说，如果 nums = [1, 2, 3, 4] ：
  • [2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。
  • [1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。

请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。

nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

 

示例 1：

输入：nums = [1,2,3,4]
输出：6
解释：好子集为：
- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。

示例 2：

输入：nums = [4,2,3,15]
输出：5
解释：好子集为：
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 30

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

思考

好子集的乘积无平方因子，元素在 $[1,30]$。平方数倍数直接排除，其余数的质因子互异，可用 $10$ 个质数的掩码表示。

背包： $f[\mathit{\text{state}}]$ 为当前质因子集合的方案。按 $x$ 从大到小更新包含其掩码的状态。任意个 $1$ 乘在空集上，最后对非空状态求和。

注意到题目中 $nums[i]$ 的范围为 $[1,30]$，因此我们可以预处理出所有小于等于 $30$ 的质数，即 $[2,3,5,7,11,13,17,19,23,29]$。

好子集中，所有元素的乘积可以表示为一个或多个互不相同的质数的乘积，也即是说，每个质因数最多只能出现一次。因此，我们可以使用一个二进制数来表示一个子集中的质因数，其中二进制数的第 $i$ 位表示质数 $primes[i]$ 是否出现在子集中。

我们可以使用状态压缩动态规划的方法来求解本题。设 $f[i]$ 表示二进制数 $i$ 表示的子集中的质因数的乘积为一个或多个互不相同的质数的乘积的方案数。初始时 $f[0]=1$。

我们在 $[2,..30]$ 的范围内枚举一个数 $x$，如果 $x$ 不在 $nums$ 中，或者 $x$ 为 $4,9,25$ 的倍数，那么我们可以直接跳过。否则，我们可以将 $x$ 的质因数用一个二进制数 $mask$ 表示，然后我们从大到小枚举当前的状态 $state$，如果 $state$ 与 $mask$ 按位与的结果为 $mask$，那么我们可以从状态 $f[state\oplus mask]$ 转移到状态 $f[state]$，转移方程为 $f[state]=f[state]+cnt[x]\times f[state\oplus mask]$，其中 $cnt[x]$ 表示 $x$ 在 $nums$ 中出现的次数。

注意，我们没有从数字 $1$ 开始枚举，因为我们可以选择任意个数字 $1$，加入到好子集中。那么最终的答案为 $\sum _{i=1}{2}^{10}-1f[i]\times 2^{cnt[1]}$。

时间复杂度 $O(n+C\times M)$，空间复杂度 $O(M)$。其中 $n$ 为 $nums$ 的长度；而 $C$ 和 $M$ 分别为题目中 $nums[i]$ 的范围和状态的个数，本题中 $C=30$, $M=2^{10}$。

相似题目：

• 2572. 无平方子集计数

func numberOfGoodSubsets(nums []int) (ans int) {
	primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
	cnt := [31]int{}
	for _, x := range nums {
		cnt[x]++
	}
	const mod int = 1e9 + 7
	n := 10
	f := make([]int, 1<<n)
	f[0] = 1
	for i := 0; i < cnt[1]; i++ {
		f[0] = f[0] * 2 % mod
	}
	for x := 2; x < 31; x++ {
		if cnt[x] == 0 || x%4 == 0 || x%9 == 0 || x%25 == 0 {
			continue
		}
		mask := 0
		for i, p := range primes {
			if x%p == 0 {
				mask |= 1 << i
			}
		}
		for state := 1<<n - 1; state > 0; state-- {
			if state&mask == mask {
				f[state] = (f[state] + f[state^mask]*cnt[x]) % mod
			}
		}
	}
	for i := 1; i < 1<<n; i++ {
		ans = (ans + f[i]) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

1997. 访问完所有房间的第一天

中等1 种解法

标签：数组、动态规划

题目、示例与约束

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。

最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：

• 假设某一天，你访问 i 号房间。
• 如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
• 如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。

请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。

 

示例 1：

输入：nextVisit = [0,0]
输出：2
解释：
- 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
  下一天你需要访问房间的编号是 nextVisit[0] = 0
- 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
  下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1
- 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。

示例 2：

输入：nextVisit = [0,0,2]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,0,0,1,2,...] 。
第 6 天是你访问完所有房间的第一天。

示例 3：

输入：nextVisit = [0,1,2,0]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,1,2,2,3,...] 。
第 6 天是你访问完所有房间的第一天。

 

提示：

• n == nextVisit.length
• 2 <= n <= 105
• 0 <= nextVisit[i] <= i

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

思考

访问奇偶决定下一步去 $nextVisit[i]$ 还是 $i+1$，模拟天数可达 ${10}^9$ 量级。第一次走到房间 $i$ 的日期 $f[i]$ 只依赖更小下标。

从 $i-1$ 首次到达再折返 $nextVisit[i-1]$，区间 $[nextVisit[i-1],i-1]$ 的奇偶与第一次走过时相同，故这段耗时再次为 $f[i-1]-f[nextVisit[i-1]]$，外加两天。

线性递推并取模。

我们定义 $f[i]$ 表示第一次访问第 $i$ 号房间的日期编号，那么答案就是 $f[n-1]$。

我们考虑第一次到达第 $i-1$ 号房间的日期编号，记为 $f[i-1]$，此时需要花一天的时间回退到第 $nextVisit[i-1]$ 号房间，为什么是回退呢？因为题目限制了 $0\le nextVisit[i]\le i$。

回退之后，此时第 $nextVisit[i-1]$ 号房间的访问为奇数次，而第 $[nextVisit[i-1]+1,..i-1]$ 号房间均被访问偶数次，那么这时候我们从第 $nextVisit[i-1]$ 号房间再次走到第 $i-1$ 号房间，就需要花费 $f[i-1]-f[nextVisit[i-1]]$ 天的时间，然后再花费一天的时间到达第 $i$ 号房间，因此 $f[i]=f[i-1]+1+f[i-1]-f[nextVisit[i-1]]+1$。由于 $f[i]$ 可能很大，因此需要对 ${10}^9+7$ 取余，并且为了防止负数，需要加上 ${10}^9+7$。

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

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

func firstDayBeenInAllRooms(nextVisit []int) int {
	n := len(nextVisit)
	f := make([]int, n)
	const mod = 1e9 + 7
	for i := 1; i < n; i++ {
		f[i] = (f[i-1] + 1 + f[i-1] - f[nextVisit[i-1]] + 1 + mod) % mod
	}
	return f[n-1]
}

力扣原题 · Doocs 题解来源

2002. 两个回文子序列长度的最大乘积

中等1 种解法

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

题目、示例与约束

给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。

请你返回两个回文子序列长度可以达到的 最大乘积 。

子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串 。

 

示例 1：

输入：s = "leetcodecom"
输出：9
解释：最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。
它们的乘积为 3 * 3 = 9 。

示例 2：

输入：s = "bb"
输出：1
解释：最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。
它们的乘积为 1 * 1 = 1 。

示例 3：

输入：s = "accbcaxxcxx"
输出：25
解释：最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。
它们的乘积为 5 * 5 = 25 。

 

提示：

• 2 <= s.length <= 12
• s 只含有小写英文字母。

方法一：二进制枚举 · Go 实现

思考

$n\le 12$，全部子序列仅 $2^n$ 个，枚举可行。两个子序列还须下标不交，直接再套一层会变成 $4^n$ 量级，常数偏大。

对每个掩码用双指针跳过未选位，即可判定对应子序列是否回文，并记入数组 $p$。

若掩码 $i$ 回文，则在其补集上枚举子掩码 $j$，乘积为两边的 $1$ 的个数。子掩码枚举总量为 $3^n$，与预处理 $2^{n}n$ 同属可接受范围。

我们注意到，字符串 $s$ 的长度不超过 $12$，因此我们可以使用二进制枚举的方法来枚举 $s$ 的所有子序列。不妨设 $s$ 的长度为 $n$，我们可以使用 $2^n$ 个长度为 $n$ 的二进制数来表示 $s$ 的所有子序列。对于每个二进制数，第 $i$ 位为 $1$ 表示 $s$ 的第 $i$ 个字符在子序列中，为 $0$ 表示不在子序列中。我们对于每个二进制数，判断其是否为回文子序列，并且记录在数组 $p$ 中。

接下来，我们枚举 $p$ 中的每个数 $i$，如果 $i$ 是回文子序列，那么我们可以从 $i$ 的补集 $mx=(2^n-1)\oplus i$ 中枚举一个数 $j$，如果 $j$ 也是回文子序列，那么 $i$ 和 $j$ 就是我们要找的两个回文子序列，它们的长度分别为 $i$ 和 $j$ 的二进制表示中的 $1$ 的个数，我们记为 $a$ 和 $b$，那么它们的乘积就是 $a\times b$，我们取所有可能的 $a\times b$ 中的最大值即可。

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

func maxProduct(s string) (ans int) {
	n := len(s)
	p := make([]bool, 1<<n)
	for i := range p {
		p[i] = true
	}
	for k := 1; k < 1<<n; k++ {
		for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
			for i < j && (k>>i&1) == 0 {
				i++
			}
			for i < j && (k>>j&1) == 0 {
				j--
			}
			if i < j && s[i] != s[j] {
				p[k] = false
				break
			}
		}
	}
	for i := 1; i < 1<<n; i++ {
		if p[i] {
			a := bits.OnesCount(uint(i))
			mx := (1<<n - 1) ^ i
			for j := mx; j > 0; j = (j - 1) & mx {
				if p[j] {
					b := bits.OnesCount(uint(j))
					ans = max(ans, a*b)
				}
			}
		}
	}
	return

}

力扣原题 · Doocs 题解来源

2008. 出租车的最大盈利

中等3 种解法

标签：数组、哈希表、二分查找、动态规划、排序

题目、示例与约束

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。

乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ，愿意支付 tipi 元的小费。

每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。

给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。

注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。

 

示例 1：

输入：n = 5, rides = [[2,5,4],[1,5,1]]
输出：7
解释：我们可以接乘客 0 的订单，获得 5 - 2 + 4 = 7 元。

示例 2：

输入：n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
输出：20
解释：我们可以接以下乘客的订单：
- 将乘客 1 从地点 3 送往地点 10 ，获得 10 - 3 + 2 = 9 元。
- 将乘客 2 从地点 10 送往地点 12 ，获得 12 - 10 + 3 = 5 元。
- 将乘客 5 从地点 13 送往地点 18 ，获得 18 - 13 + 1 = 6 元。
我们总共获得 9 + 5 + 6 = 20 元。

 

提示：

• 1 <= n <= 105
• 1 <= rides.length <= 3 * 104
• rides[i].length == 3
• 1 <= starti < endi <= n
• 1 <= tipi <= 105

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

思考

乘客按起点排序后，第 $i$ 单只与「起点 $\ge en{d}_i$」的后续乘客相容。 $m\le 3\times {10}^4$，枚举子集不可行；状态只需「从第 $i$ 单开始的最大收益」。

不接则转移到 $i+1$，接则二分找到第一个 $start\ge en{d}_i$ 的下标 $j$，收益为路程加小费再加 $dfs(j)$。

记忆化后每个 $i$ 计算一次，总时间 $O(m\log m)$。

我们先将 $rides$ 按照 $start$ 从小到大排序，然后设计一个函数 $dfs(i)$，表示从第 $i$ 个乘客开始接单，最多能获得的小费。答案即为 $dfs(0)$。

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

对于第 $i$ 个乘客，我们可以选择接单，也可以选择不接单。如果不接单，那么最多能获得的小费为 $dfs(i+1)$；如果接单，那么我们可以通过二分查找，找到在第 $i$ 个乘客下车地点之后遇到的第一个乘客，记为 $j$，那么最多能获得的小费为 $dfs(j)+en{d}_i-star{t}_i+ti{p}_i$。取两者的较大值即可。即：

$$dfs(i)=max(dfs(i+1),dfs(j)+en{d}_i-star{t}_i+ti{p}_i)$$

其中 $j$ 是满足 $star{t}_j\ge en{d}_i$ 的最小的下标，可以通过二分查找得到。

此过程中，我们可以使用记忆化搜索，将每个状态的答案保存下来，避免重复计算。

时间复杂度 $O(m\times \log m)$，空间复杂度 $O(m)$。其中 $m$ 为 $rides$ 的长度。

func maxTaxiEarnings(n int, rides [][]int) int64 {
	sort.Slice(rides, func(i, j int) bool { return rides[i][0] < rides[j][0] })
	m := len(rides)
	f := make([]int64, m)
	var dfs func(int) int64
	dfs = func(i int) int64 {
		if i >= m {
			return 0
		}
		if f[i] == 0 {
			st, ed, tip := rides[i][0], rides[i][1], rides[i][2]
			j := sort.Search(m, func(j int) bool { return rides[j][0] >= ed })
			f[i] = max(dfs(i+1), int64(ed-st+tip)+dfs(j))
		}
		return f[i]
	}
	return dfs(0)
}

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

思考

方法一按起点排序，并从末尾填一张后缀表。这里改按终点排序， $f[i]$ 表示考虑前 $i$ 单的最大收益，转移无后效。

不接为 $f[i-1]$；接则二分最后一个终点 $\le star{t}_i$ 的位置 $j$。

方法一按起点排序并从末尾填表。这里改按终点排序，定义前缀表。

先将 $rides$ 排序，这次我们按照 $end$ 从小到大排序。然后定义 $f[i]$，表示前 $i$ 个乘客中，最多能获得的小费。初始时 $f[0]=0$，答案为 $f[m]$。

对于第 $i$ 个乘客，我们可以选择接单，也可以选择不接单。如果不接单，那么最多能获得的小费为 $f[i-1]$；如果接单，我们可以通过二分查找，找到在第 $i$ 个乘客上车地点之前，最后一个下车地点不大于 $star{t}_i$ 的乘客，记为 $j$，那么最多能获得的小费为 $f[j]+en{d}_i-star{t}_i+ti{p}_i$。取两者的较大值即可。即：

$$f[i]=max(f[i-1],f[j]+en{d}_i-star{t}_i+ti{p}_i)$$

其中 $j$ 是满足 $en{d}_j\le star{t}_i$ 的最大的下标，可以通过二分查找得到。

时间复杂度 $O(m\times \log m)$，空间复杂度 $O(m)$。其中 $m$ 为 $rides$ 的长度。

相似题目：

• 1235. 规划兼职工作
• 1751. 最多可以参加的会议数目 II

func maxTaxiEarnings(n int, rides [][]int) int64 {
	sort.Slice(rides, func(i, j int) bool { return rides[i][1] < rides[j][1] })
	m := len(rides)
	f := make([]int64, m+1)
	for i := 1; i <= m; i++ {
		r := rides[i-1]
		st, ed, tip := r[0], r[1], r[2]
		j := sort.Search(m, func(j int) bool { return rides[j][1] >= st+1 })
		f[i] = max(f[i-1], f[j]+int64(ed-st+tip))
	}
	return f[m]
}

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

思考

乘客按起点排序后，第 $i$ 单只与「起点 $\ge en{d}_i$」的后续乘客相容。 $m\le 3\times {10}^4$，枚举子集不可行；状态只需「从第 $i$ 单开始的最大收益」。

不接依赖 $i+1$，接则依赖第一个起点 $\ge en{d}_i$ 的下标。按这个递推搜索时仍会先调用 $i+1$ 再返回，调用链长度为 $m$，栈会溢出。

从末尾往前走时，更靠后的下标已经就绪。令 $f[i]$ 为该收益， $f[m]=0$，填表时对 $j$ 做二分，从 $i=m-1$ 填到 $0$。

我们先将 $rides$ 按照 $start$ 从小到大排序。令 $f[i]$ 表示从第 $i$ 个乘客开始接单最多能获得的收益，答案为 $f[0]$，且 $f[m]=0$。

我们从 $i=m-1$ 填到 $0$。对于第 $i$ 个乘客，不接单则收益为 $f[i+1]$；接单时通过二分查找找到下车地点之后遇到的第一个乘客 $j$，收益为 $f[j]+en{d}_i-star{t}_i+ti{p}_i$。取两者的较大值：

$$f[i]=max(f[i+1],f[j]+en{d}_i-star{t}_i+ti{p}_i)$$

其中 $j$ 是满足 $star{t}_j\ge en{d}_i$ 的最小下标。因为 $j>i$， $f[j]$ 已经算过。

时间复杂度 $O(m\times \log m)$，空间复杂度 $O(m)$。其中 $m$ 为 $rides$ 的长度。

func maxTaxiEarnings(n int, rides [][]int) int64 {
	sort.Slice(rides, func(i, j int) bool { return rides[i][0] < rides[j][0] })
	m := len(rides)
	f := make([]int64, m+1)
	for i := m - 1; i >= 0; i-- {
		st, ed, tip := rides[i][0], rides[i][1], rides[i][2]
		j := sort.Search(m, func(k int) bool { return rides[k][0] >= ed })
		f[i] = max(f[i+1], int64(ed-st+tip)+f[j])
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

2019. 解出数学表达式的学生分数

困难1 种解法

标签：栈、记忆化、数组、哈希表、数学、字符串、动态规划

题目、示例与约束

给你一个字符串 s ，它 只 包含数字 0-9 ，加法运算符 '+' 和乘法运算符 '*' ，这个字符串表示一个 合法 的只含有 个位数数字 的数学表达式（比方说 3+5*2）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序 ：

1. 按照 从左到右 的顺序计算 乘法 ，然后
2. 按照 从左到右 的顺序计算 加法 。

给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下 规则 打分：

• 如果一位学生的答案 等于 表达式的正确结果，这位学生将得到 5 分。
• 否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到 2 分。
• 否则，这位学生将得到 0 分。

请你返回所有学生的分数和。

 

示例 1：

输入：s = "7+3*1*2", answers = [20,13,42]
输出：7
解释：如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,13,42] 。
一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10*1=10，10*2=20 。所以这位学生得分为 2 分：[20,13,42] 。
所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。

示例 2：

输入：s = "3+5*2", answers = [13,0,10,13,13,16,16]
输出：19
解释：表达式的正确结果为 13 ，所以有 3 位学生得到 5 分：[13,0,10,13,13,16,16] 。
学生可能通过错误的运算顺序得到结果 16 ：3+5=8，8*2=16 。所以两位学生得到 2 分：[13,0,10,13,13,16,16] 。
所有学生得分分别为：[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。

示例 3：

输入：s = "6+0*1", answers = [12,9,6,4,8,6]
输出：10
解释：表达式的正确结果为 6 。
如果一位学生通过错误的运算顺序计算该表达式，结果仍为 6 。
根据打分规则，运算顺序错误的学生也将得到 5 分（因为他们仍然得到了正确的结果），而不是 2 分。
所有学生得分分别为：[0,0,5,0,0,5] 。所有得分之和为 10 分。

 

提示：

• 3 <= s.length <= 31
• s 表示一个只包含 0-9 ，'+' 和 '*' 的合法表达式。
• 表达式中所有整数运算数字都在闭区间 [0, 9] 以内。
• 1 <= 数学表达式中所有运算符数目（'+' 和 '*'） <= 15
• 测试数据保证正确表达式结果在范围 [0, 1000] 以内。
• 测试用例保证乘法中间步骤中的值永远不会超过 109。
• n == answers.length
• 1 <= n <= 104
• 0 <= answers[i] <= 1000

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

思考

运算符至多 $15$ 个，错误答案来自不同加乘结合次序。枚举所有加括号方案是卡特兰数级，但区间 DP 可合并出全部可能值。正确答案按「乘优先于加」单独计算。

$f[i][j]$ 为第 $i$ 到 $j$ 个数字能算出的值集合；枚举分界 $k$ 与运算符做加减乘，并丢掉超过 $1000$ 的中间值（评分只关心 $[0,1000]$）。

对 $answers$ 计数：等于正确值得 $5$，否则若落在 $f[0][m-1]$ 中得 $2$。

我们先设计一个函数 $cal(s)$，用于计算一个合法的只含有个位数数字的数学表达式的结果。那么正确答案就是 $x=cal(s)$。

我们记字符串 $s$ 的长度为 $n$，那么 $s$ 中的数字个数为 $m=\frac{n+1}{2}$。

我们定义 $f[i][j]$ 表示选择 $s$ 中的第 $i$ 个数字到第 $j$ 个数字（下标从 $0$ 开始）这一段数字，计算出的结果可能的取值。初始时 $f[i][i]$ 表示选择第 $i$ 个数字，结果只能是这个数字本身，即 $f[i][i]=\{s[i\times 2]\}$（即第 $i$ 个数字映射到字符串 $s$ 中的下标为 $i\times 2$ 的字符）。

接下来，我们从大到小枚举 $i$，然后从小到大枚举 $j$，我们需要求出区间 $[i,j]$ 所有数字运算的结果可能的取值。我们在区间 $[i,j]$ 中枚举分界点 $k$，那么 $f[i][j]$ 可以由 $f[i][k]$ 和 $f[k+1][j]$ 通过运算符 $s[k\times 2+1]$ 得到。因此我们可以得到如下状态转移方程：

$$f[i][j]=\{\begin{array}{ll}\{s[i\times 2]\},& i=j\\ \bigcup _{k=i}^{j-1}\{f[i][k]\otimes f[k+1][j]\},& i<j\end{array}$$

其中 $\otimes$ 表示运算符，即 $s[k\times 2+1]$。

那么字符串 $s$ 所有数字运算的结果可能的取值就是 $f[0][m-1]$。

最后，我们统计答案。我们用一个数组 $cnt$ 统计答案数组 $answers$ 中每个答案出现的次数。如果答案等于 $x$，那么这个学生得到 $5$ 分，否则如果答案在 $f[0][m-1]$ 中，那么这个学生得到 $2$ 分。遍历 $cnt$，统计答案即可。

时间复杂度 $O(n^3\times M^2)$，空间复杂度 $O(n^2\times M^2)$。其中 $M$ 是答案可能的最大值，而 $n$ 是字符串 $s$ 的长度中数字的个数。

func scoreOfStudents(s string, answers []int) int {
	n := len(s)
	x := cal(s)
	m := (n + 1) >> 1
	f := make([][]map[int]bool, m)
	for i := range f {
		f[i] = make([]map[int]bool, m)
		for j := range f[i] {
			f[i][j] = make(map[int]bool)
		}
		f[i][i][int(s[i<<1]-'0')] = true
	}
	for i := m - 1; i >= 0; i-- {
		for j := i; j < m; j++ {
			for k := i; k < j; k++ {
				for l := range f[i][k] {
					for r := range f[k+1][j] {
						op := s[k<<1|1]
						if op == '+' && l+r <= 1000 {
							f[i][j][l+r] = true
						} else if op == '*' && l*r <= 1000 {
							f[i][j][l*r] = true
						}
					}
				}
			}
		}
	}
	cnt := [1001]int{}
	for _, v := range answers {
		cnt[v]++
	}
	ans := cnt[x] * 5
	for k, v := range cnt {
		if k != x && f[0][m-1][k] {
			ans += v << 1
		}
	}
	return ans
}

func cal(s string) int {
	res, pre := 0, int(s[0]-'0')
	for i := 1; i < len(s); i += 2 {
		cur := int(s[i+1] - '0')
		if s[i] == '+' {
			res += pre
			pre = cur
		} else {
			pre *= cur
		}
	}
	res += pre
	return res
}

力扣原题 · Doocs 题解来源