LeetCode Go · 动态规划（9）

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

来源与许可

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

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

1594. 矩阵的最大非负积

中等1 种解法

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

题目、示例与约束

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。

注意，取余是在得到最大积之后执行的。

 

示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。

示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)

示例 3：

输入：grid = [[1,3],[0,-4]]
输出：0
解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 15
• -4 <= grid[i][j] <= 4

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

思考

只能向右或向下，求路径乘积的最大非负值。网格含负数，最大乘积可能来自「最小（最负）乘积再乘一个负数」。只记最大值会漏掉这条通道。

对每个格子同时记录到达该格的最小积与最大积，由上方、左方的两个极值与当前值相乘更新。终点最大积若为负则返回 $-1$，否则取模。

我们定义一个三维数组 $f$，其中 $f[i][j][0]$ 和 $f[i][j][1]$ 分别表示从左上角 $(0,0)$ 出发到达位置 $(i,j)$ 的路径中积的最小值和最大值。对于每个位置 $(i,j)$，我们可以从上方 $(i-1,j)$ 或左方 $(i,j-1)$ 转移过来，因此我们需要考虑这两条路径的积的最小值和最大值与当前单元格的值相乘后的结果。

最后，我们需要返回 $f[m-1][n-1][1]$ 对 ${10}^9+7$ 取余的结果，如果 $f[m-1][n-1][1]$ 小于 $0$，则返回 $-1$。

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

func maxProductPath(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	f := make([][][2]int64, m)
	for i := range f {
		f[i] = make([][2]int64, n)
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			x := int64(grid[i][j])
			if i == 0 && j == 0 {
				f[i][j] = [2]int64{x, x}
				continue
			}

			mn, mx := int64(1<<63-1), int64(-1<<63)

			if i > 0 {
				a, b := f[i-1][j][0], f[i-1][j][1]
				mn = min(mn, min(a*x, b*x))
				mx = max(mx, max(a*x, b*x))
			}

			if j > 0 {
				a, b := f[i][j-1][0], f[i][j-1][1]
				mn = min(mn, min(a*x, b*x))
				mx = max(mx, max(a*x, b*x))
			}

			f[i][j] = [2]int64{mn, mx}
		}
	}

	ans := f[m-1][n-1][1]
	mod := int64(1e9 + 7)
	if ans < 0 {
		return -1
	}
	return int(ans % mod)
}

力扣原题 · Doocs 题解来源

1595. 连通两组点的最小成本

困难2 种解法

标签：位运算、数组、动态规划、位掩码、矩阵、二分图、图的匹配、最小费用流、SSP 算法、网络流

题目、示例与约束

给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。

任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

 

示例 1：

输入：cost = [[15, 96], [36, 2]]
输出：17
解释：连通两组点的最佳方法是：
1--A
2--B
总成本为 17 。

示例 2：

输入：cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
输出：4
解释：连通两组点的最佳方法是：
1--A
2--B
2--C
3--A
最小成本为 4 。
请注意，虽然有多个点连接到第一组中的点 2 和第二组中的点 A ，但由于题目并不限制连接点的数目，所以只需要关心最低总成本。

示例 3：

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

 

提示：

• size1 == cost.length
• size2 == cost[i].length
• 1 <= size1, size2 <= 12
• size1 >= size2
• 0 <= cost[i][j] <= 100

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

思考

两组点之间连边，要求每点至少连一条，总费用最小。两侧至多 $12$ 个点，边的子集有 $2^{mn}$ 种，不能枚举；第二组可用 $n$ 位掩码表示「哪些点已被连上」。

令 $f[i][j]$ 为处理完第一组前 $i$ 个点、第二组连通状态为 $j$ 的最小费用。枚举与第 $i$ 个点相连的 $k$（ $j$ 含该位），可从「本轮刚连上 $k$」「上一轮已是 $j$」「上一轮尚未含 $k$」三种前驱转移。答案为 $f[m][2^n-1]$。

我们记第一组的点数为 $m$，第二组的点数为 $n$。

由于 $1\le n\le m\le 12$，因此，我们可以用一个整数来表示第二组中点的状态，即二进制表示的一个长度为 $n$ 的整数，其中第 $k$ 位为 $1$ 表示第二组中的第 $k$ 个点与第一组中的点连通，为 $0$ 表示不连通。

接下来，我们定义 $f[i][j]$ 表示第一组中的前 $i$ 个点已经全部连通，且第二组中的点的状态为 $j$ 时的最小成本。初始时 $f[0][0]=0$，其余值均为正无穷大。答案即为 $f[m][2^n-1]$。

考虑 $f[i][j]$，其中 $i\ge 1$。我们可以枚举第二组中的每个点 $k$，如果点 $k$ 与第一组中的第 $i$ 个点连通，那么我们可以分以下两种情况讨论：

• 如果点 $k$ 只与第一组中的第 $i$ 个点连通，那么 $f[i][j]$ 可以从 $f[i][j\oplus 2^k]$ 或者 $f[i-1][j\oplus 2^k]$ 转移而来，其中 $\oplus$ 表示异或运算；
• 如果点 $k$ 与第一组中的第 $i$ 个点以及其他点都连通，那么 $f[i][j]$ 可以从 $f[i-1][j]$ 转移而来。

在上述两种情况中，我们需要选择转移值最小的那个，即有：

$$f[i][j]=\underset{k\in \{0,1,\cdots ,n-1\}}{min}\{f[i][j\oplus 2^k],f[i-1][j\oplus 2^k],f[i-1][j]\}+cost[i-1][k]$$

最后，我们返回 $f[m][2^n-1]$ 即可。

时间复杂度 $O(m\times n\times 2^n)$，空间复杂度 $O(m\times 2^n)$。其中 $m$ 和 $n$ 分别是第一组和第二组中的点数。

func connectTwoGroups(cost [][]int) int {
	m, n := len(cost), len(cost[0])
	const inf = 1 << 30
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, 1<<n)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= m; i++ {
		for j := 0; j < 1<<n; j++ {
			for k := 0; k < n; k++ {
				c := cost[i-1][k]
				if j>>k&1 == 1 {
					f[i][j] = min(f[i][j], f[i][j^(1<<k)]+c)
					f[i][j] = min(f[i][j], f[i-1][j]+c)
					f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+c)
				}
			}
		}
	}
	return f[m][(1<<n)-1]
}

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

思考

第 $i$ 层只依赖第 $i-1$ 层以及本层已算出的状态，两层滚动数组即可把空间从 $O(m\cdot 2^n)$ 降到 $O(2^n)$。转移式不变。

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

func connectTwoGroups(cost [][]int) int {
	m, n := len(cost), len(cost[0])
	const inf = 1 << 30
	f := make([]int, 1<<n)
	for i := range f {
		f[i] = inf
	}
	f[0] = 0
	g := make([]int, 1<<n)
	for i := 1; i <= m; i++ {
		for j := 0; j < 1<<n; j++ {
			g[j] = inf
			for k := 0; k < n; k++ {
				c := cost[i-1][k]
				if j>>k&1 == 1 {
					g[j] = min(g[j], g[j^1<<k]+c)
					g[j] = min(g[j], f[j]+c)
					g[j] = min(g[j], f[j^1<<k]+c)
				}
			}
		}
		copy(f, g)
	}
	return f[1<<n-1]
}

力扣原题 · Doocs 题解来源

1611. 使整数变为 0 的最少操作次数

困难1 种解法

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

题目、示例与约束

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。
• 如果二进制表示中的第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

 

示例 1：

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

示例 2：

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

 

提示：

• 0 <= n <= 109

方法一：格雷码逆变换（格雷码转二进制码） · Go 实现

思考

允许的两种操作分别对应「改最低位」与「改最低的 $1$ 的高一位」， $n$ 可达 ${10}^9$，逐步模拟每种操作不可行。

这两种规则恰为二进制格雷码的生成关系：把 $n$ 看成格雷码，所求最少步数等于其对应的自然二进制值。

格雷码转二进制是各位从高到低的前缀异或，写成循环即为反复 $\mathit{\text{ans}}\oplus =n$ 再右移，直至 $n$ 变为 $0$。

本题实际上求的是格雷码为 $n$ 的逆变换，即通过格雷码构造原数。

我们先来回顾一下二进制码转换成二进制格雷码，其法则是保留二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或，而格雷码其余各位与次高位的求法相类似。

假设某个二进制数表示为 $B_{n-1}{B}_{n-2}...B_2{B}_1{B}_0$，其格雷码表示为 $G_{n-1}{G}_{n-2}...G_2{G}_1{G}_0$。最高位保留，所以 $G_{n-1}=B_{n-1}$；而其它各位 $G_i=B_{i+1}\oplus B_i$，其中 $i=0,1,2..,n-2$。

那么，格雷码转换成二进制码的逆变换是什么呢？

我们可以发现，格雷码的最高位保留，所以 $B_{n-1}=G_{n-1}$；而 $B_{n-2}=G_{n-2}\oplus B_{n-1}=G_{n-2}\oplus G_{n-1}$；而其它各位 $B_i=G_i\oplus G_{i+1}\cdots \oplus G_{n-1}$，其中 $i=0,1,2..,n-2$。因此，我们可以用下面的函数 $rev(x)$ 得到其二进制码：

int rev(int x) {
    int n = 0;
    for (; x != 0; x >>= 1) {
        n ^= x;
    }
    return n;
}

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

func minimumOneBitOperations(n int) (ans int) {
	for ; n > 0; n >>= 1 {
		ans ^= n
	}
	return
}

力扣原题 · Doocs 题解来源

1621. 大小为 K 的不重叠线段的数目

中等1 种解法

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

题目、示例与约束

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：n = 4, k = 2
输出：5
解释：
如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。

示例 2：

输入：n = 3, k = 1
输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

示例 3：

输入：n = 30, k = 7
输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。

示例 4：

输入：n = 5, k = 3
输出：7

示例 5：

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

 

提示：

• 2 <= n <= 1000
• 1 <= k <= n-1

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

思考

题目要求在 $n$ 个点上画出恰好 $k$ 条互不重叠（端点可以重合）的线段。若直接枚举每条线段的两个端点，即使 $n,k\le 1000$，组合量也会迅速膨胀，还要额外保证线段从左到右有序且不相交。

线段只能沿数轴依次排列，因此可以按点从左到右决策，并把状态按「当前点是不是某条线段的右端点」拆开。记 $f[i][j]$ 为前 $i$ 个点已画 $j$ 条且不以 $i$ 为右端， $g[i][j]$ 为以 $i$ 为右端。

这样转移到 $i$ 只依赖 $i-1$ 的两类状态：不以 $i$ 结束时，直接继承前 $i-1$ 个点上的 $j$ 条方案；以 $i$ 结束时，既可以把停在 $i-1$ 的那条线段再延长一格，也可以在 $i-1$ 与 $i$ 之间新开一条长度为 $1$ 的线段。

记 $f[i][j]$ 表示使用前 $i$ 个点构造了 $j$ 条线段，且最后一条线段的右端点不为 $i$ 的方案数；记 $g[i][j]$ 表示使用前 $i$ 个点构造了 $j$ 条线段，且最后一条线段的右端点为 $i$ 的方案数。初始时 $f[1][0]=1$。

考虑 $f[i][j]$，由于第 $j$ 条线段的右端点不为 $i$，因此前 $i-1$ 个点已经构造了 $j$ 条线段，有：

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

考虑 $g[i][j]$，第 $j$ 条线段的右端点为 $i$。此时有两种来源，需要累加：将原先以 $i-1$ 为右端点的第 $j$ 条线段延长到 $i$（长度大于 $1$）；或者在前 $i-1$ 个点上已有 $j-1$ 条线段的基础上，新开一条覆盖 $i-1$ 与 $i$ 的线段（长度为 $1$）。当 $j=0$ 时不存在右端点，故第二项不计入。因此当 $j\ge 1$ 时有：

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

答案为 $f[n][k]+g[n][k]$。

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

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

力扣原题 · Doocs 题解来源

1626. 无矛盾的最佳球队

中等2 种解法

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

题目、示例与约束

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

 

示例 1：

输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出：34
解释：你可以选中所有球员。

示例 2：

输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。

示例 3：

输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最佳的选择是前 3 名球员。

 

提示：

• 1 <= scores.length, ages.length <= 1000
• scores.length == ages.length
• 1 <= scores[i] <= 106
• 1 <= ages[i] <= 1000

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

思考

冲突由「更年长反而得分更低」引起。若先按得分升序、得分相同再按年龄升序，则只需保证所选序列年龄不降，即可无冲突。

$n\le 1000$，以某人收队的最大得分可用 $O(n^2)$ 的 LIS 式转移：枚举更早且年龄不超过自己的队员，取其 $f[j]$ 再加自身得分。

答案为所有 $f[i]$ 的最大值。

我们可以将球员按照分数从小到大排序，如果分数相同，则按照年龄从小到大排序。

接下来，使用动态规划求解。

我们定义 $f[i]$ 表示以排序后的第 $i$ 个球员作为最后一个球员的最大得分，那么答案就是 $\underset{0\le i<n}{max}f[i]$。

对于 $f[i]$，我们可以枚举 $0\le j<i$，如果第 $i$ 个球员的年龄大于等于第 $j$ 个球员的年龄，则 $f[i]$ 可以从 $f[j]$ 转移而来，转移方程为 $f[i]=max(f[i],f[j])$。然后我们将第 $i$ 个球员的分数加到 $f[i]$ 中，即 $f[i]+=scores[i]$。

最后，我们返回 $\underset{0\le i<n}{max}f[i]$ 即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为球员的数量。

func bestTeamScore(scores []int, ages []int) int {
	n := len(ages)
	arr := make([][2]int, n)
	for i := range ages {
		arr[i] = [2]int{scores[i], ages[i]}
	}
	sort.Slice(arr, func(i, j int) bool {
		a, b := arr[i], arr[j]
		return a[0] < b[0] || a[0] == b[0] && a[1] < b[1]
	})
	f := make([]int, n)
	for i := range arr {
		for j := 0; j < i; j++ {
			if arr[i][1] >= arr[j][1] {
				f[i] = max(f[i], f[j])
			}
		}
		f[i] += arr[i][0]
	}
	return slices.Max(f)
}

方法二：排序 + 树状数组 · Go 实现

思考

方法一枚举前驱是 $O(n^2)$。同一排序下，需要的是「年龄不超过当前值的最大得分」，这是前缀最大值查询。

树状数组按下标维护最大值：查询 $[1,\mathit{\text{age}}]$ 的最优，再把 $\mathit{\text{score}}$ 加回去更新该年龄。复杂度降为 $O(n\log m)$。

与方法一类似，我们可以将球员按照分数从小到大排序，如果分数相同，则按照年龄从小到大排序。

接下来，我们使用树状数组维护不超过当前球员年龄的球员的最大得分。每一次，我们只需要在 $O(\log m)$ 的时间内找出不超过当前球员年龄的球员的最大得分，然后将当前球员的分数加到该得分上，即可更新当前球员年龄的最大得分。

最后，我们返回得分的最大值即可。

时间复杂度 $O(n\times (\log n+\log m))$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别为球员的数量和球员的年龄的最大值。

type BinaryIndexedTree struct {
	n int
	c []int
}

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

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

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

func bestTeamScore(scores []int, ages []int) int {
	n := len(ages)
	arr := make([][2]int, n)
	m := 0
	for i, age := range ages {
		m = max(m, age)
		arr[i] = [2]int{scores[i], age}
	}
	sort.Slice(arr, func(i, j int) bool {
		a, b := arr[i], arr[j]
		return a[0] < b[0] || a[0] == b[0] && a[1] < b[1]
	})
	tree := newBinaryIndexedTree(m)
	for _, x := range arr {
		tree.update(x[1], x[0]+tree.query(x[1]))
	}
	return tree.query(m)
}

力扣原题 · Doocs 题解来源

1638. 统计只差一个字符的子串数目

中等2 种解法

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

题目、示例与约束

给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。

比方说， "computer" and "computation" 只有一个字符不同： 'e'/'a' ，所以这一对子字符串会给答案加 1 。

请你返回满足上述条件的不同子字符串对数目。

一个 子字符串 是一个字符串中连续的字符。

 

示例 1：

输入：s = "aba", t = "baba"
输出：6
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。

示例 2：

输入：s = "ab", t = "bb"
输出：3
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。

示例 3：

输入：s = "a", t = "a"
输出：0

示例 4：

输入：s = "abe", t = "bbc"
输出：10

 

提示：

• 1 <= s.length, t.length <= 100
• s 和 t 都只包含小写英文字母。

方法一：枚举 · Go 实现

思考

两串长度不超过 $100$，合法子串对恰好有一个位置不同。以该不同位置为中心向两侧扩展，左右连续相等的长度决定有多少种截取方式。

枚举 $(i,j)$ 且 $s[i]\ne t[j]$，向左、向右统计相同前缀/后缀长度 $l,r$，贡献 $(l+1)(r+1)$。

我们可以枚举字符串 $s$ 和 $t$ 中不同的那个字符位置，然后分别向两边扩展，直到遇到不同的字符为止，这样就可以得到以该位置为中心的满足条件的子串对数目。我们记左边扩展的相同字符个数为 $l$，右边扩展的相同字符个数为 $r$，那么以该位置为中心的满足条件的子串对数目为 $(l+1)\times (r+1)$，累加到答案中即可。

枚举结束后，即可得到答案。

时间复杂度 $O(m\times n\times min(m,n))$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别为字符串 $s$ 和 $t$ 的长度。

func countSubstrings(s string, t string) (ans int) {
	m, n := len(s), len(t)
	for i, a := range s {
		for j, b := range t {
			if a != b {
				l, r := 0, 0
				for i > l && j > l && s[i-l-1] == t[j-l-1] {
					l++
				}
				for i+r+1 < m && j+r+1 < n && s[i+r+1] == t[j+r+1] {
					r++
				}
				ans += (l + 1) * (r + 1)
			}
		}
	}
	return
}

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

思考

方法一在每个差异点现场向两侧延伸，存在重复比较。可预处理以 $(i,j)$ 结尾的最长相等后缀 $f$ 与开头的最长相等前缀 $g$。

再枚举差异点时贡献变为 $(f[i][j]+1)(g[i+1][j+1]+1)$，总时间 $O(mn)$。

方法一中，我们每次需要分别往左右两边扩展，得出 $l$ 和 $r$ 的值。实际上，我们可以预处理出以每个位置 $(i,j)$ 结尾的最长相同后缀的长度，以及以每个位置 $(i,j)$ 开头的最长相同前缀的长度，分别记录在数组 $f$ 和 $g$ 中。

接下来，与方法一类似，我们枚举字符串 $s$ 和 $t$ 中不同的那个字符位置 $(i,j)$，那么以该位置为中心的满足条件的子串对数目为 $(f[i][j]+1)\times (g[i+1][j+1]+1)$，累加到答案中即可。

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

func countSubstrings(s string, t string) (ans int) {
	m, n := len(s), len(t)
	f := make([][]int, m+1)
	g := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
		g[i] = make([]int, n+1)
	}
	for i, a := range s {
		for j, b := range t {
			if a == b {
				f[i+1][j+1] = f[i][j] + 1
			}
		}
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if s[i] == t[j] {
				g[i][j] = g[i+1][j+1] + 1
			} else {
				ans += (f[i][j] + 1) * (g[i+1][j+1] + 1)
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1639. 通过给定词典构造目标字符串的方案数

困难3 种解法

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

题目、示例与约束

给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都 长度相同  。

你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：

• 从左到右依次构造 target 的每一个字符。
• 为了得到 target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你可以使用 words 列表中第 j 个字符串的第 k 个字符。
• 一旦你使用了 words 中第 j 个字符串的第 k 个字符，你不能再使用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于 k 的字符都不能再被使用。
• 请你重复此过程直到得到目标字符串 target 。

请注意， 在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中 同一个字符串 的 多个字符 。

请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 109 + 7 取余 后返回。

（译者注：此题目求的是有多少个不同的 k 序列，详情请见示例。）

 

示例 1：

输入：words = ["acca","bbbb","caca"], target = "aba"
输出：6
解释：总共有 6 种方法构造目标串。
"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("caca")
"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("caca")
"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("caca")

示例 2：

输入：words = ["abba","baab"], target = "bab"
输出：4
解释：总共有 4 种不同形成 target 的方法。
"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 2 ("abba")
"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 3 ("baab")
"bab" -> 下标为 0 ("baab")，下标为 2 ("baab")，下标为 3 ("baab")
"bab" -> 下标为 1 ("abba")，下标为 2 ("baab")，下标为 3 ("baab")

示例 3：

输入：words = ["abcd"], target = "abcd"
输出：1

示例 4：

输入：words = ["abab","baba","abba","baab"], target = "abba"
输出：16

 

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words 中所有单词长度相同。
• 1 <= target.length <= 1000
• words[i] 和 target 都仅包含小写英文字母。

方法一：预处理 + 记忆化搜索 · Go 实现

思考

各单词等长，同一列的字母可以互换使用，列必须从左到右不降地选取。直接对单词做回溯会重复且超时。

先统计第 $j$ 列字母 $c$ 的出现次数 $\mathit{\text{cnt}}[j][c]$，问题化为：匹配 $\mathit{\text{target}}[i:]$ 且当前列号为 $j$。

记忆化 $dfs(i,j)$：可跳过第 $j$ 列，或用该列匹配 $\mathit{\text{target}}[i]$ 并乘上计数；边界为 $i$ 走完返回 $1$、 $j$ 走完返回 $0$。

我们注意到，字符串数组 $words$ 中的每一个字符串长度都相同，不妨记为 $n$，那么我们可以预处理出一个二维数组 $cnt$，其中 $cnt[j][c]$ 表示字符串数组 $words$ 中第 $j$ 个位置的字符 $c$ 的数量。

接下来，我们设计一个函数 $dfs(i,j)$，表示构造 $target[i,..]$ 且当前从 $words$ 中选取的字符位置为 $j$ 的方案数。那么答案就是 $dfs(0,0)$。

函数 $dfs(i,j)$ 的计算逻辑如下：

• 如果 $i\ge m$，说明 $target$ 中的所有字符都已经被选取，那么方案数为 $1$。
• 如果 $j\ge n$，说明 $words$ 中的所有字符都已经被选取，那么方案数为 $0$。
• 否则，我们可以不选择 $words$ 中的第 $j$ 个位置的字符，那么方案数为 $dfs(i,j+1)$；或者我们选择 $words$ 中的第 $j$ 个位置的字符，那么方案数为 $dfs(i+1,j+1)\times cnt[j][target[i]{-}^{\prime }{a}^{\prime }]$。

最后，我们返回 $dfs(0,0)$ 即可。注意答案的取模操作。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 为字符串 $target$ 的长度，而 $n$ 为字符串数组 $words$ 中每个字符串的长度。

func numWays(words []string, target string) int {
	m, n := len(target), len(words[0])
	f := make([][]int, m)
	cnt := make([][26]int, n)
	for _, w := range words {
		for j, c := range w {
			cnt[j][c-'a']++
		}
	}
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	const mod = 1e9 + 7
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= m {
			return 1
		}
		if j >= n {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans := dfs(i, j+1)
		ans = (ans + dfs(i+1, j+1)*cnt[j][target[i]-'a']) % mod
		f[i][j] = ans
		return ans
	}
	return dfs(0, 0)
}

方法二：预处理 + 动态规划 · Go 实现

思考

方法一按后缀填表，每个状态都读取更大的列号。同一选择也可以记成前缀：配完 $\mathit{\text{target}}$ 前 $i$ 个字符、只用前 $j$ 列的方案数。

不选第 $j-1$ 列则等于 $f[i][j-1]$，选用则是 $f[i-1][j-1]$ 乘上该列计数。初值 $f[0][\cdot ]=1$，按 $i$、 $j$ 从小到大填写即可。

与方法一类似，我们可以先预处理出一个二维数组 $cnt$，其中 $cnt[j][c]$ 表示字符串数组 $words$ 中第 $j$ 个位置的字符 $c$ 的数量。

接下来，我们定义 $f[i][j]$ 表示构造 $target$ 的前 $i$ 个字符，且当前是从 $words$ 中每个单词的前 $j$ 个字符中选取字符的方案数。那么答案就是 $f[m][n]$。初始时 $f[0][j]=1$，其中 $0\le j\le n$。

考虑 $f[i][j]$，其中 $i>0$, $j>0$。我们可以不选取 $words$ 中的第 $j$ 个位置的字符，那么方案数为 $f[i][j-1]$；或者我们选择 $words$ 中的第 $j$ 个位置的字符，那么方案数为 $f[i-1][j-1]\times cnt[j-1][target[i-1]{-}^{\prime }{a}^{\prime }]$。最后，我们将这两种情况的方案数相加，即为 $f[i][j]$ 的值。

最后，我们返回 $f[m][n]$ 即可。注意答案的取模操作。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 为字符串 $target$ 的长度，而 $n$ 为字符串数组 $words$ 中每个字符串的长度。

func numWays(words []string, target string) int {
	const mod = 1e9 + 7
	m, n := len(target), len(words[0])
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for j := range f[0] {
		f[0][j] = 1
	}
	cnt := make([][26]int, n)
	for _, w := range words {
		for j, c := range w {
			cnt[j][c-'a']++
		}
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			f[i][j] = f[i][j-1] + f[i-1][j-1]*cnt[j-1][target[i-1]-'a']
			f[i][j] %= mod
		}
	}
	return f[m][n]
}

方法三：预处理 + 动态规划 · Go 实现

思考

各单词等长，同一列的字母可以互换。直接对单词回溯，在 $m$ 与 $n$ 都不超过 $1000$ 时会重复搜索并超时。

先统计第 $j$ 列字母 $c$ 的次数 $\mathit{\text{cnt}}[j][c]$。构造 $\mathit{\text{target}}[i:]$ 时，可以跳过第 $j$ 列，也可以用它匹配当前字符并乘上计数。

两种选择读到的都是更大的列号。从第 $0$ 列一直走到第 $n$ 列，调用链长度就是 $n$。 $n=1000$ 时 Python 会抛出 RecursionError。

因此改成填表。 $f[i][j]$ 仍是从第 $j$ 列起构造 $\mathit{\text{target}}[i:]$ 的方案数。目标配完为 $1$，列用尽为 $0$，所以先令 $f[m][j]=1$。 $i$ 与 $j$ 都从大到小填写， $f[i][j+1]$ 和 $f[i+1][j+1]$ 已经算完。

我们注意到，字符串数组 $words$ 中的每一个字符串长度都相同，不妨记为 $n$，那么我们可以预处理出一个二维数组 $cnt$，其中 $cnt[j][c]$ 表示字符串数组 $words$ 中第 $j$ 个位置的字符 $c$ 的数量。

接下来，定义 $f[i][j]$ 表示构造 $target[i,..]$ 且当前从 $words$ 的第 $j$ 列开始选取字符的方案数。答案就是 $f[0][0]$。

若 $i=m$，说明 $target$ 已经全部选取，方案数为 $1$；若 $j=n$ 且 $i<m$，说明列已经用尽而目标尚未完成，方案数为 $0$。因此先把 $f[m][j]$ 置为 $1$（ $0\le j\le n$），其余格子置为 $0$。

对于其余状态，按 $i$ 从 $m-1$ 降到 $0$、 $j$ 从 $n-1$ 降到 $0$ 计算。不选择第 $j$ 列时，方案数为 $f[i][j+1]$；选择第 $j$ 列时，方案数为 $f[i+1][j+1]\times cnt[j][target[i]{-}^{\prime }{a}^{\prime }]$。两者相加后对 ${10}^9+7$ 取模，得到 $f[i][j]$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 为字符串 $target$ 的长度，而 $n$ 为字符串数组 $words$ 中每个字符串的长度。

func numWays(words []string, target string) int {
	m, n := len(target), len(words[0])
	cnt := make([][26]int, n)
	for _, w := range words {
		for j, c := range w {
			cnt[j][c-'a']++
		}
	}
	const mod = 1e9 + 7
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for j := range f[m] {
		f[m][j] = 1
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			ans := f[i][j+1] + f[i+1][j+1]*cnt[j][target[i]-'a']
			f[i][j] = ans % mod
		}
	}
	return f[0][0]
}

力扣原题 · Doocs 题解来源

1641. 统计字典序元音字符串的数目

中等2 种解法

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

题目、示例与约束

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

 

示例 1：

输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：

输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：

输入：n = 33
输出：66045

 

提示：

• 1 <= n <= 50 

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

思考

长度为 $n$ 的非降元音串等价于从 $5$ 种字母中可重复地按序选取。 $n$ 通常不超过 $50$，按「已放 $i$ 个、最后字母编号为 $j$」搜索即可。

$dfs(i,j)$ 在 $i=n$ 时计 $1$，否则枚举 $k\ge j$ 继续； $\mathtt{\text{cache}}$ 避免重复状态。

我们设计一个函数 $dfs(i,j)$，表示当前已经选了 $i$ 个元音字母，且最后一个元音字母是 $j$ 的方案数。那么答案就是 $dfs(0,0)$。

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

• 如果 $i\ge n$，说明已经选了 $n$ 个元音字母，返回 $1$。
• 否则，枚举 $j$ 后面的元音字母，即 $k\in [j,4]$，并将 $dfs(i+1,k)$ 的结果累加，即 $dfs(i,j)=\sum _{k=j}^{4}dfs(i+1,k)$。

过程中，我们可以使用记忆化搜索，将已经计算过的 $dfs(i,j)$ 的结果保存起来，避免重复计算。

时间复杂度 $O(n\times C^2)$，空间复杂度 $O(n\times C)$。其中 $n$ 为题目给定的整数，而 $C$ 是元音字母的数量，本题中 $C=5$。

func countVowelStrings(n int) int {
	f := make([][5]int, n)
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= n {
			return 1
		}
		if f[i][j] != 0 {
			return f[i][j]
		}
		ans := 0
		for k := j; k < 5; k++ {
			ans += dfs(i+1, k)
		}
		f[i][j] = ans
		return ans
	}
	return dfs(0, 0)
}

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

思考

方法一的二维状态可压成「长度为 $i$ 时以各元音结尾的个数」。后一长度是前一长度的后缀和。

用长为 $5$ 的数组滚动，每次把前缀和写回，最后求和。空间降为常数。

定义 $f[i][j]$ 表示当前已经选了 $i$ 个元音字母，且最后一个元音字母是 $j$ 的方案数。初始时 $f[1][j]=1$。答案是 $\sum _{j=0}^{4}f[n][j]$。

我们可以发现 $f[i][j]$ 只与 $f[i-1][j]$ 有关，因此可以将二维数组压缩为一维数组，从而优化空间复杂度。

时间复杂度 $O(n\times C)$，空间复杂度 $O(C)$。其中 $n$ 为题目给定的整数，而 $C$ 是元音字母的数量，本题中 $C=5$。

func countVowelStrings(n int) (ans int) {
	f := [5]int{1, 1, 1, 1, 1}
	for i := 0; i < n-1; i++ {
		s := 0
		for j := 0; j < 5; j++ {
			s += f[j]
			f[j] = s
		}
	}
	for _, v := range f {
		ans += v
	}
	return
}

力扣原题 · Doocs 题解来源

1643. 第 K 条最小指令

困难1 种解法

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

题目、示例与约束

Bob 站在单元格 (0, 0) ，想要前往目的地 destination ：(row, column) 。他只能向 右 或向 下 走。你可以为 Bob 提供导航 指令 来帮助他到达目的地 destination 。

指令 用字符串表示，其中每个字符：

• 'H' ，意味着水平向右移动
• 'V' ，意味着竖直向下移动

能够为 Bob 导航到目的地 destination 的指令可以有多种，例如，如果目的地 destination 是 (2, 3)，"HHHVV" 和 "HVHVH" 都是有效 指令 。

然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循 按字典序排列后的第 k 条最小指令 的导航前往目的地 destination 。k  的编号 从 1 开始 。

给你一个整数数组 destination 和一个整数 k ，请你返回可以为 Bob 提供前往目的地 destination 导航的 按字典序排列后的第 k 条最小指令 。

 

示例 1：

输入：destination = [2,3], k = 1
输出："HHHVV"
解释：能前往 (2, 3) 的所有导航指令 按字典序排列后 如下所示：
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].

示例 2：

输入：destination = [2,3], k = 2
输出："HHVHV"

示例 3：

输入：destination = [2,3], k = 3
输出："HHVVH"

 

提示：

• destination.length == 2
• 1 <= row, column <= 15
• 1 <= k <= nCr(row + column, row)，其中 nCr(a, b) 表示组合数，即从 a 个物品中选 b 个物品的不同方案数。

方法一：组合计数 · Go 实现

思考

路径由 $v$ 个 $\mathtt{\text{V}}$ 与 $h$ 个 $\mathtt{\text{H}}$ 组成，字典序第 $k$ 条不能把全部 $(\genfrac{}{}{0ex}{}{h+v}{h})$ 条路径列出来。

最高位若取 $\mathtt{\text{H}}$，以 $\mathtt{\text{H}}$ 开头的条数是 $C_{h+v-1}^{h-1}$。 $k$ 大于该数则最高位只能是 $\mathtt{\text{V}}$ 并扣掉这些方案，否则取 $\mathtt{\text{H}}$。

从左到右逐位用组合数决策，直到 $h$ 用尽则其余全为 $\mathtt{\text{V}}$。

根据题目描述我们可以知道，最终的路径是由 $destination[0]$ 个 'V' 和 $destination[1]$ 个 'H' 组成的，且按字典序排列后的第 $k$ 条最小指令。

我们首先考虑字典序的最高位，即最左边的字符。如果高位字符是 'V'，那么所有以 'H' 开头的路径的字典序都比它小，而以 'H' 开头的路径总数为 $x=C_{v+h-1}^{h-1}$。

如果 $k<x$，那么高位字符一定是 'V'，我们将 $k$ 减去 $x$，并将 $v$ 减 $1$，然后继续考虑下一位字符；否则，高位字符一定是 'H'，我们将 $h$ 减 $1$，然后继续考虑下一位字符。

注意，如果 $h=0$，那么高位字符一定是 'V'，因为剩下的字符都是 'V'。

问题可以转换为求解 $C_n^k$，我们可以通过公式 $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$ 递推求解。

时间复杂度 $O((h+v)\times h)$，空间复杂度 $O((h+v)\times h)$。其中 $h$ 和 $v$ 分别为 $destination[1]$ 和 $destination[0]$。

func kthSmallestPath(destination []int, k int) string {
	v, h := destination[0], destination[1]
	n := v + h
	c := make([][]int, n+1)
	for i := range c {
		c[i] = make([]int, h+1)
		c[i][0] = 1
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= h; j++ {
			c[i][j] = c[i-1][j] + c[i-1][j-1]
		}
	}
	ans := []byte{}
	for i := 0; i < n; i++ {
		if h == 0 {
			ans = append(ans, 'V')
		} else {
			x := c[v+h-1][h-1]
			if k > x {
				ans = append(ans, 'V')
				k -= x
				v--
			} else {
				ans = append(ans, 'H')
				h--
			}
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1653. 使字符串平衡的最少删除次数

中等2 种解法

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

题目、示例与约束

给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

 

示例 1：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

 

提示：

• 1 <= s.length <= 105
• s[i] 要么是 'a' 要么是 'b'​ 。​

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

思考

平衡串是若干 a 后接若干 b。 $n$ 达 ${10}^5$，不能枚举所有删除方案。从前到后决策时，已出现的 b 个数决定「删当前 a」还是「删掉这些 b」。

$f[i]$ 为前 $i$ 个字符变平衡的最少删除：遇 b 则 $f[i]=f[i-1]$ 并累加 $b$；遇 a 则 $f[i]=min(f[i-1]+1,b)$。

我们定义 $f[i]$ 表示前 $i$ 个字符中，删除最少的字符数，使得字符串平衡。初始时 $f[0]=0$。答案为 $f[n]$。

我们遍历字符串 $s$，维护变量 $b$，表示当前遍历到的位置之前的字符中，字符 $b$ 的个数。

• 如果当前字符为 'b'，此时不影响前 $i$ 个字符的平衡性，因此 $f[i]=f[i-1]$，然后我们更新 $b\leftarrow b+1$。
• 如果当前字符为 'a'，此时我们可以选择删除当前字符，那么有 $f[i]=f[i-1]+1$；也可以选择删除之前的字符 $b$，那么有 $f[i]=b$。因此我们取两者的最小值，即 $f[i]=min(f[i-1]+1,b)$。

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

$$f[i]=\{\begin{array}{ll}f[i-1],& s[i-1]{=}^{\prime }{b}^{\prime }\\ min(f[i-1]+1,b),& s[i-1]{=}^{\prime }{a}^{\prime }\end{array}$$

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

我们注意到，状态转移方程中只与前一个状态以及变量 $b$ 有关，因此我们可以仅用一个答案变量 $ans$ 维护当前的 $f[i]$，并不需要开辟数组 $f$。

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

func minimumDeletions(s string) int {
	n := len(s)
	f := make([]int, n+1)
	b := 0
	for i, c := range s {
		i++
		if c == 'b' {
			f[i] = f[i-1]
			b++
		} else {
			f[i] = min(f[i-1]+1, b)
		}
	}
	return f[n]
}

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

思考

方法一按前缀递推。也可枚举分界：左边只留 a（删光 b），右边只留 b（删光 a），两边计数之和即删除数。

维护左侧 b 个数与右侧 a 个数，扫一遍取最小和，空间同样 $O(1)$。

我们可以枚举字符串 $s$ 中的每一个位置 $i$，将字符串 $s$ 分成两部分，分别为 $s[0,..,i-1]$ 和 $s[i+1,..n-1]$，要使得字符串平衡，我们在当前位置 $i$ 需要删除的字符数为 $s[0,..,i-1]$ 中字符 $b$ 的个数加上 $s[i+1,..n-1]$ 中字符 $a$ 的个数。

因此，我们维护两个变量 $lb$ 和 $ra$ 分别表示 $s[0,..,i-1]$ 中字符 $b$ 的个数以及 $s[i+1,..n-1]$ 中字符 $a$ 的个数，那么我们需要删除的字符数为 $lb+ra$。枚举过程中，更新变量 $lb$ 和 $ra$。

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

func minimumDeletions(s string) int {
	lb, ra := 0, strings.Count(s, "a")
	ans := ra
	for _, c := range s {
		if c == 'a' {
			ra--
		}
		if t := lb + ra; ans > t {
			ans = t
		}
		if c == 'b' {
			lb++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1655. 分配重复整数

困难1 种解法

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

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity ，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足：

• 第 i 位顾客 恰好 有 quantity[i] 个整数。
• 第 i 位顾客拿到的整数都是 相同的 。
• 每位顾客都满足上述两个要求。

如果你可以分配 nums 中的整数满足上面的要求，那么请返回 true ，否则返回 false 。

 

示例 1：

输入：nums = [1,2,3,4], quantity = [2]
输出：false
解释：第 0 位顾客没办法得到两个相同的整数。

示例 2：

输入：nums = [1,2,3,3], quantity = [2]
输出：true
解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。

示例 3：

输入：nums = [1,1,2,2], quantity = [2,2]
输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。

 

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= 1000
• m == quantity.length
• 1 <= m <= 10
• 1 <= quantity[i] <= 105
• nums 中至多有 50 个不同的数字。

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

思考

顾客至多 $10$ 人，每种数的存量要完整分给若干顾客。子集分配可用 $2^m$ 表示谁已被满足。

先把频次收成 $arr$，并预处理顾客子集的需求之和 $s[j]$。 $f[i][j]$ 表示前 $i$ 种数字能否满足顾客集合 $j$。

枚举 $j$ 的子集 $k$ 分给第 $i$ 种数，当 $s[k]\le arr[i]$ 且剩余集合已被前 $i-1$ 种满足时转移。答案是 $f[n-1][2^m-1]$。

我们先统计数组 $nums$ 中每个数字出现的次数，记录在哈希表 $cnt$ 中，然后将哈希表中的值存入数组 $arr$ 中，我们记数组 $arr$ 的长度为 $n$。

注意到数组 $quantity$ 的长度不超过 $10$，因此，我们可以用一个二进制数表示 $quantity$ 中的一个子集，即数字 $j$ 表示 $quantity$ 中的一个子集，其中 $j$ 的二进制表示中的第 $i$ 位为 $1$ 表示 $quantity$ 中的第 $i$ 个数字被选中，为 $0$ 表示第 $i$ 个数字未被选中。

我们可以预处理出数组 $s$，其中 $s[j]$ 表示 $quantity$ 中子集 $j$ 中所有数字的和。

接下来，我们定义 $f[i][j]$ 表示数组 $arr[0,..i-1]$ 中的数字能否成功分配给 $quantity$ 中的子集 $j$，其中 $i$ 的取值范围为 $[0,..n-1]$，而 $j$ 的取值范围为 $[0,2^m-1]$，其中 $m$ 为 $quantity$ 的长度。

考虑 $f[i][j]$，如果子集 $j$ 中存在一个子集 $k$，使得 $s[k]\le arr[i]$，并且 $f[i-1][j\oplus k]$ 为真，那么 $f[i][j]$ 为真，否则 $f[i][j]$ 为假。

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

时间复杂度 $O(n\times 3^m)$，空间复杂度 $O(n\times 2^m)$。其中 $n$ 是数组 $nums$ 中不同整数的个数；而 $m$ 是数组 $quantity$ 的长度。

func canDistribute(nums []int, quantity []int) bool {
	m := len(quantity)
	s := make([]int, 1<<m)
	for i := 1; i < 1<<m; i++ {
		for j := 0; j < m; j++ {
			if i>>j&1 == 1 {
				s[i] = s[i^(1<<j)] + quantity[j]
				break
			}
		}
	}
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	n := len(cnt)
	arr := make([]int, 0, n)
	for _, x := range cnt {
		arr = append(arr, x)
	}
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, 1<<m)
		f[i][0] = true
	}
	for i := 0; i < n; i++ {
		for j := 0; j < 1<<m; j++ {
			if i > 0 && f[i-1][j] {
				f[i][j] = true
				continue
			}
			for k := j; k > 0; k = (k - 1) & j {
				ok1 := (i == 0 && j == k) || (i > 0 && f[i-1][j-k])
				ok2 := s[k] <= arr[i]
				if ok1 && ok2 {
					f[i][j] = true
					break
				}
			}
		}
	}
	return f[n-1][(1<<m)-1]
}

力扣原题 · Doocs 题解来源

1659. 最大化网格幸福感

困难2 种解法

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

题目、示例与约束

给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格，和两种类型的人：内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。

请你决定网格中应当居住多少人，并为每个人分配一个网格单元。 注意，不必 让所有人都生活在网格中。

每个人的 幸福感 计算如下：

• 内向的人 开始 时有 120 个幸福感，但每存在一个邻居（内向的或外向的）他都会 失去  30 个幸福感。
• 外向的人 开始 时有 40 个幸福感，每存在一个邻居（内向的或外向的）他都会 得到  20 个幸福感。

邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。

网格幸福感 是每个人幸福感的 总和 。 返回 最大可能的网格幸福感 。

 

示例 1：

输入：m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
输出：240
解释：假设网格坐标 (row, column) 从 1 开始编号。
将内向的人放置在单元 (1,1) ，将外向的人放置在单元 (1,3) 和 (2,3) 。
- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (0 * 30)（0 位邻居）= 120
- 位于 (1,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
- 位于 (2,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
网格幸福感为：120 + 60 + 60 = 240
上图展示该示例对应网格中每个人的幸福感。内向的人在浅绿色单元中，而外向的人在浅紫色单元中。

示例 2：

输入：m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
输出：260
解释：将内向的人放置在单元 (1,1) 和 (3,1) ，将外向的人放置在单元 (2,1) 。
- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
- 位于 (2,1) 的外向的人的幸福感：40（初始幸福感）+ (2 * 20)（2 位邻居）= 80
- 位于 (3,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
网格幸福感为 90 + 80 + 90 = 260

示例 3：

输入：m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
输出：240

 

提示：

• 1 <= m, n <= 5
• 0 <= introvertsCount, extrovertsCount <= min(m * n, 6)

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

思考

网格至多 $5\times 5$，每格空置、内向或外向，相邻会对幸福感产生固定修正。整表搜索 $3^{mn}$ 过大，但一行只有 $3^n\le 243$ 种填法。

预处理每行自身幸福感 $f$、相邻两行之间的贡献 $g$，以及该行消耗的内向、外向人数。

按行记忆化 $dfs(i,pre,ic,ec)$：枚举当前行状态，扣人数并累加 $f+g$，取最大。

我们注意到，题目中 $1\le m,n\le 5$，并且每个网格单元只有三种状态，即：不分配人员、分配内向的人、分配外向的人。因此，我们可以用 $0$, $1$, $2$ 表示这三种状态，网格中的每一行可以用一个长度为 $n$ 的三进制数表示。

我们定义一个函数 $dfs(i,pre,ic,ec)$，表示当前从第 $i$ 行开始，且上一行的状态为 $pre$，内向的人还剩 $ic$ 个，外向的人还剩 $ec$ 个时，网格的最大幸福感。那么答案就是 $dfs(0,0,introvertsCount,extrovertsCount)$。

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

如果 $i=m$，表示已经处理完了所有的行，那么返回 $0$；

如果 $ic=0$ 且 $ec=0$，表示所有的人都已经分配完了，那么返回 $0$；

否则，枚举当前行的状态 $cur$，其中 $cur\in [0,3^n)$，然后计算当前行的幸福感 $f[cur]$，以及与上一行的状态 $pre$ 之间对幸福感的贡献 $g[pre][cur]$，并递归计算 $dfs(i+1,cur,ic-ix[cur],ec-ex[cur])$，最后返回 $f[cur]+g[pre][cur]+dfs(i+1,cur,ic-ix[cur],ec-ex[cur])$ 的最大值，即：

$$dfs(i,pre,ic,ec)=\underset{cur}{max}\{f[cur]+g[pre][cur]+dfs(i+1,cur,ic-ix[cur],ec-ex[cur])\}$$

其中：

• $ix[cur]$ 表示状态 $cur$ 中内向的人的个数；
• $ex[cur]$ 表示状态 $cur$ 中外向的人的个数；
• $f[cur]$ 表示状态 $cur$ 中的人的初始幸福感；
• $g[pre][cur]$ 表示两个相邻状态行对幸福感的贡献。

这些值都可以通过预处理得到。并且，我们可以使用记忆化搜索的方法，避免重复计算。

时间复杂度 $O(3^{2n}\times (m\times ic\times ec+n))$，空间复杂度 $O(3^{2n}+3^n\times m\times ic\times ec)$。其中 $ic$ 和 $ec$ 分别表示内向的人和外向的人的个数。

func getMaxGridHappiness(m int, n int, introvertsCount int, extrovertsCount int) int {
	mx := int(math.Pow(3, float64(n)))
	f := make([]int, mx)
	g := make([][]int, mx)
	h := [3][3]int{{0, 0, 0}, {0, -60, -10}, {0, -10, 40}}
	bits := make([][]int, mx)
	ix := make([]int, mx)
	ex := make([]int, mx)
	memo := make([][][][]int, m)
	for i := range g {
		g[i] = make([]int, mx)
		bits[i] = make([]int, n)
	}
	for i := range memo {
		memo[i] = make([][][]int, mx)
		for j := range memo[i] {
			memo[i][j] = make([][]int, introvertsCount+1)
			for k := range memo[i][j] {
				memo[i][j][k] = make([]int, extrovertsCount+1)
				for l := range memo[i][j][k] {
					memo[i][j][k][l] = -1
				}
			}
		}
	}
	for i := 0; i < mx; i++ {
		mask := i
		for j := 0; j < n; j++ {
			x := mask % 3
			mask /= 3
			bits[i][j] = x
			if x == 1 {
				ix[i]++
				f[i] += 120
			} else if x == 2 {
				ex[i]++
				f[i] += 40
			}
			if j > 0 {
				f[i] += h[x][bits[i][j-1]]
			}
		}
	}
	for i := 0; i < mx; i++ {
		for j := 0; j < mx; j++ {
			for k := 0; k < n; k++ {
				g[i][j] += h[bits[i][k]][bits[j][k]]
			}
		}
	}
	var dfs func(int, int, int, int) int
	dfs = func(i, pre, ic, ec int) int {
		if i == m || (ic == 0 && ec == 0) {
			return 0
		}
		if memo[i][pre][ic][ec] != -1 {
			return memo[i][pre][ic][ec]
		}
		ans := 0
		for cur := 0; cur < mx; cur++ {
			if ix[cur] <= ic && ex[cur] <= ec {
				ans = max(ans, f[cur]+g[pre][cur]+dfs(i+1, cur, ic-ix[cur], ec-ex[cur]))
			}
		}
		memo[i][pre][ic][ec] = ans
		return ans
	}
	return dfs(0, 0, introvertsCount, extrovertsCount)
}

方法二：轮廓线记忆化搜索 · Go 实现

思考

方法一按整行转移，行宽变大时 $3^n$ 仍偏厚。改成逐格填，轮廓线只保留最近 $n$ 格的三进制状态，即可与左、上邻居结算。

$dfs(pos,pre,ic,ec)$ 枚举当前格 $0/1/2$，滚动轮廓并加上 $h[up][i]+h[left][i]$ 与格子本身的 $120$ 或 $40$。

我们可以考虑搜索每个网格单元，每次搜索一个位置 $(i,j)$，我们记 $pos=i\times n+j$。那么它左边以及上边的相邻网格会影响到它们之间的幸福感贡献。

我们定义一个函数 $dfs(pos,pre,ic,ec)$，表示当前搜索到位置 $pos$，且此前的 $n$ 个网格单元的状态为 $pre$，内向的人还剩 $ic$ 个，外向的人还剩 $ec$ 个时，网格的最大幸福感。那么答案就是 $dfs(0,0,introvertsCount,extrovertsCount)$。

函数 $dfs(pos,pre,ic,ec)$ 的计算过程如下：

如果 $pos=m\times n$，表示已经处理完了所有的网格单元，那么返回 $0$；

如果 $ic=0$ 且 $ec=0$，表示所有的人都已经分配完了，那么返回 $0$；

否则，我们根据 $pre$ 算出当前网格单元的上边相邻网格单元的状态 $up=\frac{pre}{3^{n-1}}$，以及左边相邻网格单元的状态 $left=premod3$（注意，如果 $pos$ 在第 $0$ 列，那么 $left=0$）。

接下来，我们枚举当前网格单元的状态 $i$，其中 $i\in [0,3)$。那么当前的 $n$ 个网格单元的状态为 $cur=premod{3}^{n-1}\times 3+i$，当前网格单元以及左边和上边的相邻网格单元的幸福感贡献为 $h[up][i]+h[left][i]$；而当前网格单元本身的幸福感取决于该位置是否分配人员，以及分配的人员是内向的还是外向的，如果是内向的，那么幸福感为 $120$，如果是外向的，那么幸福感为 $40$，否则幸福感为 $0$；然后，如果当前网格单元分配了人员，那么我们递归调用时需要更新 $ic$ 或 $ec$。累计这些幸福感，取最大值作为函数的返回值。

与方法一类似，我们也可以使用记忆化搜索的方法，避免重复计算。

时间复杂度 $O(3^{n+1}\times m\times n\times ic\times ec)$，空间复杂度 $O(3^n\times m\times n\times ic\times ec)$。其中 $ic$ 和 $ec$ 分别表示内向的人和外向的人的个数。

func getMaxGridHappiness(m int, n int, introvertsCount int, extrovertsCount int) int {
	p := int(math.Pow(3, float64(n-1)))
	h := [3][3]int{{0, 0, 0}, {0, -60, -10}, {0, -10, 40}}
	memo := make([][][][]int, m*n)
	for i := range memo {
		memo[i] = make([][][]int, p*3)
		for j := range memo[i] {
			memo[i][j] = make([][]int, introvertsCount+1)
			for k := range memo[i][j] {
				memo[i][j][k] = make([]int, extrovertsCount+1)
				for l := range memo[i][j][k] {
					memo[i][j][k][l] = -1
				}
			}
		}
	}
	var dfs func(int, int, int, int) int
	dfs = func(pos, pre, ic, ec int) int {
		if pos == m*n || (ic == 0 && ec == 0) {
			return 0
		}
		if memo[pos][pre][ic][ec] != -1 {
			return memo[pos][pre][ic][ec]
		}
		ans := 0
		up := pre / p
		left := pre % 3
		if pos%n == 0 {
			left = 0
		}
		for i := 0; i < 3; i++ {
			if (i == 1 && ic == 0) || (i == 2 && ec == 0) {
				continue
			}
			cur := pre%p*3 + i
			nic, nec := ic, ec
			c := 0
			if i == 1 {
				nic--
				c = 120
			} else if i == 2 {
				nec--
				c = 40
			}
			a := h[up][i] + h[left][i]
			b := dfs(pos+1, cur, nic, nec)
			ans = max(ans, a+b+c)
		}
		memo[pos][pre][ic][ec] = ans
		return ans
	}
	return dfs(0, 0, introvertsCount, extrovertsCount)
}

力扣原题 · Doocs 题解来源

1668. 最大重复子字符串

简单1 种解法

标签：字符串、动态规划、字符串匹配

题目、示例与约束

给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。

给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。

 

示例 1：

输入：sequence = "ababc", word = "ab"
输出：2
解释："abab" 是 "ababc" 的子字符串。

示例 2：

输入：sequence = "ababc", word = "ba"
输出：1
解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。

示例 3：

输入：sequence = "ababc", word = "ac"
输出：0
解释："ac" 不是 "ababc" 的子字符串。

 

提示：

• 1 <= sequence.length <= 100
• 1 <= word.length <= 100
• sequence 和 word 都只包含小写英文字母。

方法一：直接枚举 · Go 实现

思考

求 $word$ 连续重复能作为 $sequence$ 子串的最大次数。两串长度不超过 $100$，从 $n/|word|$ 向下枚举 $k$，第一次 $word\ast k$ 出现即为答案。

注意到字符串长度不超过 $100$，我们直接从大到小枚举 word 的重复次数 $k$，判断 word 重复该次数后是否是 sequence 的子串，是则直接返回当前的重复次数 $k$。

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

func maxRepeating(sequence string, word string) int {
	for k := len(sequence) / len(word); k > 0; k-- {
		if strings.Contains(sequence, strings.Repeat(word, k)) {
			return k
		}
	}
	return 0
}

力扣原题 · Doocs 题解来源

1671. 得到山形数组的最少删除次数

困难1 种解法

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

题目、示例与约束

我们定义 arr 是 山形数组 当且仅当它满足：

• arr.length >= 3
• 存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums​ ，请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。

 

示例 1：

输入：nums = [1,3,1]
输出：0
解释：数组本身就是山形数组，所以我们不需要删除任何元素。

示例 2：

输入：nums = [2,1,1,5,6,2,3,1]
输出：3
解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。

 

提示：

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 题目保证 nums 删除一些元素后一定能得到山形数组。

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

思考

山形数组在峰两侧严格升降。删最少元素等于留下最长山形子序列。 $n\le 1000$，可对每个峰算左侧 LIS 与右侧 LDS。

$\mathit{\text{left}}[i]$、 $\mathit{\text{right}}[i]$ 分别为以 $i$ 结尾的最长上升、以 $i$ 开头的最长下降；峰须满足两者都大于 $1$。

最少删除为 $n-max(\mathit{\text{left}}[i]+\mathit{\text{right}}[i]-1)$。

本题可以转化为求最长上升子序列和最长下降子序列。

我们定义 $left[i]$ 表示以 $nums[i]$ 结尾的最长上升子序列的长度，定义 $right[i]$ 表示以 $nums[i]$ 开头的最长下降子序列的长度。

那么最终答案就是 $n-max(left[i]+right[i]-1)$，其中 $1\le i\le n$，并且 $left[i]>1$ 且 $right[i]>1$。

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

func minimumMountainRemovals(nums []int) int {
	n := len(nums)
	left, right := make([]int, n), make([]int, n)
	for i := range left {
		left[i], right[i] = 1, 1
	}
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				left[i] = max(left[i], left[j]+1)
			}
		}
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if nums[i] > nums[j] {
				right[i] = max(right[i], right[j]+1)
			}
		}
	}
	ans := 0
	for i := range left {
		if left[i] > 1 && right[i] > 1 {
			ans = max(ans, left[i]+right[i]-1)
		}
	}
	return n - ans
}

力扣原题 · Doocs 题解来源

1681. 最小不兼容性

困难1 种解法

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

题目、示例与约束

给你一个整数数组 nums​​​ 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。

一个子集的 不兼容性 是该子集里面最大值和最小值的差。

请你返回将数组分成 k 个子集后，各子集 不兼容性 的 和 的 最小值 ，如果无法分成分成 k 个子集，返回 -1 。

子集的定义是数组中一些数字的集合，对数字顺序没有要求。

 

示例 1：

输入：nums = [1,2,1,4], k = 2
输出：4
解释：最优的分配是 [1,2] 和 [1,4] 。
不兼容性和为 (2-1) + (4-1) = 4 。
注意到 [1,1] 和 [2,4] 可以得到更小的和，但是第一个集合有 2 个相同的元素，所以不可行。

示例 2：

输入：nums = [6,3,8,1,3,1,2,2], k = 4
输出：6
解释：最优的子集分配为 [1,2]，[2,3]，[6,8] 和 [1,3] 。
不兼容性和为 (2-1) + (3-2) + (8-6) + (3-1) = 6 。

示例 3：

输入：nums = [5,3,3,6,3,3], k = 3
输出：-1
解释：没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。

 

提示：

• 1 <= k <= nums.length <= 16
• nums.length 能被 k 整除。
• 1 <= nums[i] <= nums.length

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

思考

把数组均分成 $k$ 组，组内元素互异，最小化各组 $(max-min)$ 之和。 $n\le 16$，子集 DP 可行。

预处理所有大小为 $m=n/k$ 且无重复的子集的不兼容性 $g[i]$。 $f[S]$ 为已选下标集合 $S$ 的最小代价，枚举 $S$ 的补集中无重复的 $m$ 元子集转移。

无法划分则 $f[2^n-1]$ 仍为无穷，返回 $-1$。

不妨设划分后每个子集的大小为 $m$，那么 $m=\frac{n}{k}$，其中 $n$ 是数组的长度。

我们可以枚举所有的子集 $i$，其中 $i\in [0,2^n)$，如果子集 $i$ 的二进制表示中有 $m$ 个 $1$，并且子集 $i$ 中的元素没有重复，那么我们就可以计算出子集 $i$ 的不兼容性，记为 $g[i]$，即 $g[i]=\underset{j\in i}{max}\{nums[j]\}-\underset{j\in i}{min}\{nums[j]\}$。

接下来，我们可以使用动态规划来求解。

我们定义 $f[i]$ 表示当前已经划分的子集状态为 $i$ 时，子集的不兼容性和的最小值。初始时 $f[0]=0$，表示没有任何元素被划分到子集中，其余 $f[i]=+\mathrm{\infty }$。

对于状态 $i$，我们找出所有未被划分且不重复的元素，用一个状态 $mask$ 表示，如果状态 $mask$ 中的元素个数大于等于 $m$，那么我们就枚举 $mask$ 的所有子集 $j$，并且满足 $j\subset mask$，那么 $f[i\cup j]=min\{f[i\cup j],f[i]+g[j]\}$。

最后，如果 $f[2^n-1]=+\mathrm{\infty }$，那么说明无法划分成 $k$ 个子集，返回 $-1$，否则返回 $f[2^n-1]$。

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

func minimumIncompatibility(nums []int, k int) int {
	n := len(nums)
	m := n / k
	const inf = 1 << 30
	f := make([]int, 1<<n)
	g := make([]int, 1<<n)
	for i := range g {
		f[i] = inf
		g[i] = -1
	}
	for i := 1; i < 1<<n; i++ {
		if bits.OnesCount(uint(i)) != m {
			continue
		}
		s := map[int]struct{}{}
		mi, mx := 20, 0
		for j, x := range nums {
			if i>>j&1 == 1 {
				if _, ok := s[x]; ok {
					break
				}
				s[x] = struct{}{}
				mi = min(mi, x)
				mx = max(mx, x)
			}
		}
		if len(s) == m {
			g[i] = mx - mi
		}
	}
	f[0] = 0
	for i := 0; i < 1<<n; i++ {
		if f[i] == inf {
			continue
		}
		s := map[int]struct{}{}
		mask := 0
		for j, x := range nums {
			if _, ok := s[x]; !ok && i>>j&1 == 0 {
				s[x] = struct{}{}
				mask |= 1 << j
			}
		}
		if len(s) < m {
			continue
		}
		for j := mask; j > 0; j = (j - 1) & mask {
			if g[j] != -1 {
				f[i|j] = min(f[i|j], f[i]+g[j])
			}
		}
	}
	if f[1<<n-1] == inf {
		return -1
	}
	return f[1<<n-1]
}

力扣原题 · Doocs 题解来源

1682. 最长回文子序列 II 🔒

中等1 种解法

标签：字符串、动态规划

题目、示例与约束

字符串 s 的某个子序列符合下列条件时，称为“好的回文子序列”：

• 它是 s 的子序列。
• 它是回文序列（反转后与原序列相等）。
• 长度为偶数。
• 除中间的两个字符外，其余任意两个连续字符不相等。

例如，若 s = "abcabcabb"，则 "abba" 可称为“好的回文子序列”，而 "bcb" （长度不是偶数）和 "bbbb" （含有相等的连续字符）不能称为“好的回文子序列”。

给定一个字符串 s， 返回 s 的最长“好的回文子序列”的长度。

 

示例 1:

输入: s = "bbabab"
输出: 4
解释: s 的最长“好的回文子序列”是 "baab"。

示例 2:

输入: s = "dcbccacdb"
输出: 4
解释: s 的最长“好的回文子序列”是 "dccd"。

 

提示:

• 1 <= s.length <= 250
• s 包含小写英文字母。

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

思考

好的回文子序列长度至少为 $2$，且相邻的「成对字符」不能相同。普通 LPS 只需区间两端，这里还要记住上一对用过的字符。

$dfs(i,j,x)$：区间 $[i,j]$、上一对字符为 $x$。两端相等且不等于 $x$ 则配对并更新 $x$，否则收缩一端。记忆化后复杂度 $O(n^2|\mathrm{\Sigma }|)$。

我们设计一个函数 $dfs(i,j,x)$ 表示字符串 $s$ 中下标范围 $[i,j]$ 内，且以字符 $x$ 结尾的最长“好的回文子序列”的长度。答案为 $dfs(0,n-1,26)$。

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

• 如果 $i>=j$，则 $dfs(i,j,x)=0$；
• 如果 $s[i]=s[j]$，且 $s[i]\ne x$，那么 $dfs(i,j,x)=dfs(i+1,j-1,s[i])+2$；
• 如果 $s[i]\ne s[j]$，那么 $dfs(i,j,x)=max(dfs(i+1,j,x),dfs(i,j-1,x))$。

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

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

func longestPalindromeSubseq(s string) int {
	n := len(s)
	f := make([][][]int, n)
	for i := range f {
		f[i] = make([][]int, n)
		for j := range f[i] {
			f[i][j] = make([]int, 27)
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	var dfs func(i, j, x int) int
	dfs = func(i, j, x int) int {
		if i >= j {
			return 0
		}
		if f[i][j][x] != -1 {
			return f[i][j][x]
		}
		ans := 0
		if s[i] == s[j] && int(s[i]-'a') != x {
			ans = dfs(i+1, j-1, int(s[i]-'a')) + 2
		} else {
			ans = max(dfs(i+1, j, x), dfs(i, j-1, x))
		}
		f[i][j][x] = ans
		return ans
	}
	return dfs(0, n-1, 26)
}

力扣原题 · Doocs 题解来源

1690. 石子游戏 VII

中等3 种解法

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

题目、示例与约束

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

 

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。

示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

 

提示：

• n == stones.length
• 2 <= n <= 1000
• 1 <= stones[i] <= 1000

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

思考

每次取走两端之一，得分为剩余石子和，求先手减后手的最大差值。区间博弈可用记忆化： $dfs(i,j)$ 表示当前先手相对优势。

前缀和 $s$ 给出去掉左端或右端后的得分，转移取 $s[j+1]-s[i+1]-dfs(i+1,j)$ 与 $s[j]-s[i]-dfs(i,j-1)$ 的较大者。

我们先预处理出前缀和数组 $s$，其中 $s[i]$ 表示前 $i$ 个石头的总和。

接下来，设计一个函数 $dfs(i,j)$，表示当剩下的石子为 $stones[i],stones[i+1],\dots ,stones[j]$ 时，先手与后手的得分差值。那么答案即为 $dfs(0,n-1)$。

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

• 如果 $i>j$，说明当前没有石子，返回 $0$；
• 否则，先手有两种选择，分别是移除 $stones[i]$ 或 $stones[j]$，然后计算得分差值，即 $a=s[j+1]-s[i+1]-dfs(i+1,j)$ 和 $b=s[j]-s[i]-dfs(i,j-1)$，我们取两者中的较大值作为 $dfs(i,j)$ 的返回值。

过程中，我们使用记忆化搜索，即使用数组 $f$ 记录函数 $dfs(i,j)$ 的返回值，避免重复计算。

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

func stoneGameVII(stones []int) int {
	n := len(stones)
	s := make([]int, n+1)
	f := make([][]int, n)
	for i, x := range stones {
		s[i+1] = s[i] + x
		f[i] = make([]int, n)
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i > j {
			return 0
		}
		if f[i][j] != 0 {
			return f[i][j]
		}
		a := s[j+1] - s[i+1] - dfs(i+1, j)
		b := s[j] - s[i] - dfs(i, j-1)
		f[i][j] = max(a, b)
		return f[i][j]
	}
	return dfs(0, n-1)
}

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

思考

方法一已经按 $i$ 递减、 $j$ 递增填好同一组区间转移。下面的 $f[i][j]$ 与那张表是同一定义。

方法一已经按 $i$ 递减、 $j$ 递增填好同一组转移。定义 $f[i][j]$ 表示当剩下的石子为 $stones[i],stones[i+1],\dots ,stones[j]$ 时，先手与后手的得分差值。那么答案即为 $f[0][n-1]$。

状态转移方程如下：

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

在计算 $f[i][j]$ 时，我们需要保证 $f[i+1][j]$ 和 $f[i][j-1]$ 已经被计算出来，因此我们需要按照从大到小的顺序枚举 $i$，从小到大的顺序枚举 $j$。

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

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

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

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

思考

双方每一步都枚举左右两端，方案数是指数级的。石子个数可以到 $1000$，而先计算去掉左端的分支时，区间左端点每次加一，递归深度就是 $n$。先手在区间 $[i,j]$ 上的相对优势只依赖更短的区间。于是用 $f[i][j]$ 记下这个差值，单颗石子的差值为 $0$，按 $i$ 从大到小、 $j$ 从小到大填写：去掉左端得 $s[j+1]-s[i+1]-f[i+1][j]$，去掉右端得 $s[j]-s[i]-f[i][j-1]$，取较大者。

先预处理前缀和 $s$，其中 $s[i]$ 表示前 $i$ 个石头的总和。令 $f[i][j]$ 表示剩下的石子为 $stones[i],stones[i+1],\dots ,stones[j]$ 时，当前先手与后手的得分差值。只剩一颗石子时差值为 $0$。从 $i=n-2$ 递减到 $0$，对每个 $i$ 让 $j$ 从 $i+1$ 增到 $n-1$。此时更短的区间 $f[i+1][j]$ 与 $f[i][j-1]$ 都已算过。去掉左端的得分为 $s[j+1]-s[i+1]-f[i+1][j]$，去掉右端的得分为 $s[j]-s[i]-f[i][j-1]$， $f[i][j]$ 取两者较大值。答案为 $f[0][n-1]$。

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

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

力扣原题 · Doocs 题解来源

1691. 堆叠长方体的最大高度

困难1 种解法

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

题目、示例与约束

给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。

如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。

返回 堆叠长方体 cuboids 可以得到的 最大高度 。

 

示例 1：

输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]
输出：190
解释：
第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
总高度是 95 + 50 + 45 = 190 。

示例 2：

输入：cuboids = [[38,25,45],[76,35,3]]
输出：76
解释：
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。

示例 3：

输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出：102
解释：
重新排列长方体后，可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下，这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。

 

提示：

• n == cuboids.length
• 1 <= n <= 100
• 1 <= widthi, lengthi, heighti <= 100

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

思考

可旋转长方体，堆叠要求三维都不超过下方。把每条棱排序成「长 $\le$ 宽 $\le$ 高」后，合法堆叠高度最大，再对长方体整体排序。

$n$ 很小，用 $f[i]$ 表示以 $i$ 为底的最大高度，枚举可放在其上的 $j$（宽、高也不超过），转移 $f[i]=maxf[j]+h_i$。

根据题目描述，长方体 $j$ 能够放在长方体 $i$ 上，当且仅当长方体 $j$ 的“长、宽、高”分别小于等于长方体 $i$ 的“长、宽、高”。

本题允许我们旋转长方体，意味着我们可以选择长方体的任意一边作为长方体的“高”。对于任意一种合法的堆叠，如果我们把里面每个长方体都旋转至“长 <= 宽 <= 高”，堆叠仍然是合法的，并且能够保证堆叠的高度最大化。

因此，我们可以把所有长方体的边长进行排序，使得每个长方体满足“长 <= 宽 <= 高”。然后将每个长方体升序排列。

接下来，我们可以使用动态规划的方法求解本题。

我们定义 $f[i]$ 表示以长方体 $i$ 为最底部长方体时的最大高度。我们可以枚举每个长方体 $i$ 的上方的长方体 $j$，其中 $0\le j<i$。如果 $j$ 可以放在 $i$ 的上方，那么我们可以得到状态转移方程：

$$f[i]=\underset{0\le j<i}{max}\{f[j]+h[i]\}$$

其中 $h[i]$ 表示长方体 $i$ 的高度。

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

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

func maxHeight(cuboids [][]int) int {
	for _, c := range cuboids {
		sort.Ints(c)
	}
	sort.Slice(cuboids, func(i, j int) bool {
		a, b := cuboids[i], cuboids[j]
		return a[0] < b[0] || a[0] == b[0] && (a[1] < b[1] || a[1] == b[1] && a[2] < b[2])
	})
	n := len(cuboids)
	f := make([]int, n)
	for i := range f {
		for j := 0; j < i; j++ {
			if cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2] {
				f[i] = max(f[i], f[j])
			}
		}
		f[i] += cuboids[i][2]
	}
	return slices.Max(f)
}

力扣原题 · Doocs 题解来源

1692. 计算分配糖果的不同方式 🔒

困难1 种解法

标签：动态规划

题目、示例与约束

现有 n 颗 不同 糖果（分别标记为 1 到 n ）和 k 个相同的手袋。请把糖果分配到各个手袋中并保证每个手袋里至少有一颗糖果。

不考虑手袋和糖果的摆放顺序，会有多种不同的分配方式。如果某种分配方式中其中一个手袋里的糖果与另一种分配方式中所有手袋里的糖果都不相同，则认为这两种分配方式不同。

例如，(1), (2,3) 与(2), (1,3)的分配方式是不同的，因为第一种分配方式中手袋(2,3)里的糖果2和3，在第二种分配方式中被分配到了手袋(2)和(1,3) 中。

已知整数 n 和 k, 请返回分配糖果的不同方式。返回的答案如果数值太大，请取109 + 7的模，并返回。

 

示例 1：

输入：n = 3, k = 2
输出：3
解释：把糖果 3 分配到 2 个手袋中的一个，共有 3 种方式:
(1), (2,3)
(1,2), (3)
(1,3), (2)

示例 2：

输入：n = 4, k = 2
输出：7
解释：把糖果 4 分配到 2 个手袋中的一个，共有 7 种方式:
(1), (2,3,4)
(1,2), (3,4)
(1,3), (2,4)
(1,4), (2,3)
(1,2,3), (4)
(1,2,4), (3)
(1,3,4), (2)

示例 3：

输入：n = 20, k = 5
输出：206085257
解释：把 20 颗糖果分配到 5 个手袋种，共有 1881780996 种方式。1881780996 取 109 + 7的模，等于 206085257。

 

提示：

• 1 <= k <= n <= 1000

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

思考

把 $n$ 颗糖果放入 $k$ 个非空无标号手袋，手袋之间只按所装数量区分，即第二类 Stirling 相关计数。 $n,k\le 1000$，二维 DP 即可。

$f[i][j]$：前 $i$ 颗放入 $j$ 个手袋。新糖或开新袋 $f[i-1][j-1]$，或放入已有 $j$ 袋之一 $f[i-1][j]\times j$。

我们定义 $f[i][j]$ 表示将 $i$ 个糖果分配给 $j$ 个手袋的不同分配方式的数量。初始时 $f[0][0]=1$，答案为 $f[n][k]$。

我们考虑第 $i$ 个糖果如何分配，如果第 $i$ 个糖果分配给一个新的手袋，那么 $f[i][j]=f[i-1][j-1]$；如果第 $i$ 个糖果分配给一个已有的手袋，那么 $f[i][j]=f[i-1][j]\times j$。因此，状态转移方程为：

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

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

时间复杂度 $O(n\times k)$，空间复杂度 $O(n\times k)$。其中 $n$ 和 $k$ 分别为糖果的数量和手袋的数量。

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

力扣原题 · Doocs 题解来源

1696. 跳跃游戏 VI

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。

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

 

示例 1：

输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。

示例 2：

输入：nums = [10,-5,-2,4,0,3], k = 3
输出：17
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。

示例 3：

输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出：0

 

提示：

•  1 <= nums.length, k <= 105
• -104 <= nums[i] <= 104

方法一：动态规划 + 单调队列优化 · Go 实现

思考

从 $i$ 可跳到 $(i,i+k]$，得分累加落地值，求到终点的最大得分。朴素 $f[i]=nums[i]+\underset{i-k\le j<i}{max}f[j]$ 是 $O(nk)$， $n$ 达 ${10}^5$。

窗口最大值用单调递减队列存下标： $f[q[0]]$ 即最优前驱，队尾弹出不优的 $f$，队首丢掉滑出窗口的下标。

我们定义 $f[i]$ 表示到达下标 $i$ 的最大得分，那么 $f[i]$ 的值可以从 $f[j]$ 转移而来，其中 $j$ 满足 $i-k\le j\le i-1$。因此我们可以使用动态规划求解。

状态转移方程为：

$$f[i]=\underset{j\in [i-k,i-1]}{max}f[j]+nums[i]$$

我们可以使用单调队列优化状态转移方程，具体做法是维护一个单调递减的队列，队列中存储的是下标 $j$，并且队列中的下标对应的 $f[j]$ 值是单调递减的。在进行状态转移时，我们只需要取出队首的下标 $j$，即可得到 $f[j]$ 的最大值，然后将 $f[i]$ 的值更新为 $f[j]+nums[i]$ 即可。

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

func maxResult(nums []int, k int) int {
	n := len(nums)
	f := make([]int, n)
	q := Deque{}
	q.PushBack(0)
	for i := 0; i < n; i++ {
		if i-q.Front() > k {
			q.PopFront()
		}
		f[i] = nums[i] + f[q.Front()]
		for !q.Empty() && f[i] >= f[q.Back()] {
			q.PopBack()
		}
		q.PushBack(i)
	}
	return f[n-1]
}

type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
	return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
	return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
	q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
	q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
	if len(q.l) > 0 {
		q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
	} else {
		v, q.r = q.r[0], q.r[1:]
	}
	return
}

func (q *Deque) PopBack() (v int) {
	if len(q.r) > 0 {
		q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
	} else {
		v, q.l = q.l[0], q.l[1:]
	}
	return
}

func (q Deque) Front() int {
	if len(q.l) > 0 {
		return q.l[len(q.l)-1]
	}
	return q.r[0]
}

func (q Deque) Back() int {
	if len(q.r) > 0 {
		return q.r[len(q.r)-1]
	}
	return q.l[0]
}

func (q Deque) Get(i int) int {
	if i < len(q.l) {
		return q.l[len(q.l)-1-i]
	}
	return q.r[i-len(q.l)]
}

力扣原题 · Doocs 题解来源

1714. 数组中特殊等间距元素的和 🔒

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给定一个索引从 0 开始的整数类型数组 nums ，包含 n 个非负整数。

另外给定一个（包含查询指令的）数组 queries ，其中 queries[i] = [xi, yi]。 第 i 个查询指令的答案是 nums[j] 中满足该条件的所有元素的和： xi <= j < n 且 (j - xi) 能被 yi 整除。

返回一个数组 answer，其中  answer.length == queries.length 且 answer[i] 是第 i 个查询指令的答案对 109 + 7 取模。

 

示例 1:

输入: nums = [0,1,2,3,4,5,6,7], queries = [[0,3],[5,1],[4,2]]
输出: [9,18,10]
解释: 每次查询的答案如下：
1) 符合查询条件的索引 j 有 0、 3 和 6。 nums[0] + nums[3] + nums[6] = 9
2) 符合查询条件的索引 j 有 5、 6 和 7。 nums[5] + nums[6] + nums[7] = 18
3) 符合查询条件的索引 j 有 4 和 6。 nums[4] + nums[6] = 10

示例 2:

输入: nums = [100,200,101,201,102,202,103,203], queries = [[0,7]]
输出: [303]

 

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• 0 <= nums[i] <= 109
• 1 <= queries.length <= 1.5 * 105
• 0 <= xi < n
• 1 <= yi <= 5 * 104

方法一：分块 · Go 实现

思考

询问形如从 $x$ 起每隔 $y$ 求和。若每次暴力沿步长累加， $q\le 1.5\times {10}^5$、 $n\le 5\times {10}^4$ 在步长很小时会退化到接近 $O(nq)$。

步长大时路径短，直接求和即可；步长小时路径长，应预处理后缀和。以 $\sqrt{n}$ 为界把两种情形分开。

$\mathit{\text{suf}}[i][j]$ 表示从 $j$ 起步长为 $i$ 的后缀和。 $y\le \sqrt{n}$ 时查表，否则按步长扫描。整体 $O((n+q)\sqrt{n})$。

这道题是一道比较典型的分块题目，对于步长较大的查询，我们可以直接暴力求解；对于步长较小的查询，我们可以预处理出每个位置的后缀和，然后直接查询。

本题中，我们将步长较大的查询的步长限制为 $\sqrt{n}$，这样就可以保证每个查询的时间复杂度为 $O(\sqrt{n})$。

我们定义一个二维数组 $suf$，其中 $suf[i][j]$ be 表示从位置 $j$ 开始，步长为 $i$ 的后缀和。那么对于每个查询 $[x,y]$，我们可以分为两种情况：

• 如果 $y\le \sqrt{n}$，那么我们可以直接查询 $suf[y][x]$；
• 如果 $y>\sqrt{n}$，那么我们可以直接暴力求解。

时间复杂度 $O((n+m)\times \sqrt{n})$，空间复杂度 $O(n\times \sqrt{n})$。其中 $n$ 是数组的长度，而 $m$ 是查询的个数。

func solve(nums []int, queries [][]int) (ans []int) {
	n := len(nums)
	m := int(math.Sqrt(float64(n)))
	const mod int = 1e9 + 7
	suf := make([][]int, m+1)
	for i := range suf {
		suf[i] = make([]int, n+1)
		for j := n - 1; j >= 0; j-- {
			suf[i][j] = (suf[i][min(n, j+i)] + nums[j]) % mod
		}
	}
	for _, q := range queries {
		x, y := q[0], q[1]
		if y <= m {
			ans = append(ans, suf[y][x])
		} else {
			s := 0
			for i := x; i < n; i += y {
				s = (s + nums[i]) % mod
			}
			ans = append(ans, s)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1723. 完成所有工作的最短时间

困难1 种解法

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

题目、示例与约束

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能 最小 的 最大工作时间 。

 

示例 1：

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。

示例 2：

输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。

 

提示：

• 1 <= k <= jobs.length <= 12
• 1 <= jobs[i] <= 107

方法一：DFS + 剪枝 · Go 实现

思考

把工作分给 $k$ 个工人，最小化最大工作量。工作数很小，可搜索分配，但朴素 $k^n$ 过大。

当前最大工作量一旦不小于已知答案即可剪枝。先分配耗时更长的工作，能更早触发该剪枝。

将 $jobs$ 降序排列后 DFS：尝试放入每个工人，回溯；若某工人当前为空则不必再试后续空工人，避免对称重复。

本题与 2305. 公平分发饼干 基本一致，不同的地方仅在于 $k$ 值的大小。

剪枝优化：优化分配花费时间较大的工作，因此可以先对 $jobs$ 按照降序排列。

func minimumTimeRequired(jobs []int, k int) int {
	cnt := make([]int, k)
	ans := 0x3f3f3f3f
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i] > jobs[j]
	})
	var dfs func(int)
	dfs = func(i int) {
		if i == len(jobs) {
			mx := slices.Max(cnt)
			ans = min(ans, mx)
			return
		}
		for j := 0; j < k; j++ {
			if cnt[j]+jobs[i] >= ans {
				continue
			}
			cnt[j] += jobs[i]
			dfs(i + 1)
			cnt[j] -= jobs[i]
			if cnt[j] == 0 {
				break
			}
		}
	}
	dfs(0)
	return ans
}

力扣原题 · Doocs 题解来源

1735. 生成乘积数组的方案数

困难1 种解法

标签：数组、数学、动态规划、组合数学、数论、质因数分解、费马小定理

题目、示例与约束

给你一个二维整数数组 queries ，其中 queries[i] = [ni, ki] 。第 i 个查询 queries[i] 要求构造长度为 ni 、每个元素都是正整数的数组，且满足所有元素的乘积为 ki ，请你找出有多少种可行的方案。由于答案可能会很大，方案数需要对 109 + 7 取余 。

请你返回一个整数数组 answer，满足 answer.length == queries.length ，其中 answer[i]是第 i 个查询的结果。

 

示例 1：

输入：queries = [[2,6],[5,1],[73,660]]
输出：[4,1,50734910]
解释：每个查询之间彼此独立。
[2,6]：总共有 4 种方案得到长度为 2 且乘积为 6 的数组：[1,6]，[2,3]，[3,2]，[6,1]。
[5,1]：总共有 1 种方案得到长度为 5 且乘积为 1 的数组：[1,1,1,1,1]。
[73,660]：总共有 1050734917 种方案得到长度为 73 且乘积为 660 的数组。1050734917 对 109 + 7 取余得到 50734910 。

示例 2 ：

输入：queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：[1,2,3,10,5]

 

提示：

• 1 <= queries.length <= 104
• 1 <= ni, ki <= 104

方法一：质因数分解 + 组合数学 · Go 实现

思考

每个询问要把乘积 $k$ 拆成 $n$ 个正整数。枚举因子分配在 $k\le {10}^4$ 且询问多时过慢。

将 $k$ 质因数分解后，各质数指数独立：把 $x$ 个相同质因子放入 $n$ 个可空位置，方案为 $C_{x+n-1}^{n-1}$。

预处理阶乘、逆元与每个 $k$ 的指数表，询问时把各指数的组合数相乘取模。

我们可以对 $k$ 进行质因数分解，即 $k=p_1^{x_1}\times p_2^{x_2}\times \cdots \times p_m^{x_m}$，其中 $p_i$ 为质数，而 $x_i$ 为 $p_i$ 的指数。那么题目实际上等价于：把 $x_1$ 个 $p_1$, $x_2$ 个 $p_2$, $\cdots$, $x_m$ 个 $p_m$ 分别放到 $n$ 个位置上，单个位置可以为空，问有多少种方案。

根据组合数学的知识，我们把 $x$ 个球放入 $n$ 个盒子中，有两种情况：

如果盒子不能为空，那么方案数为 $C_{x-1}^{n-1}$，这里是利用隔板法，即一共 $x$ 个球，我们在其中 $x-1$ 个位置插入 $n-1$ 个隔板，从而将 $x$ 个球分成 $n$ 组。

如果盒子可以为空，那么我们可以再增加 $n$ 个虚拟球，然后再利用隔板法，即一共 $x+n$ 个球，我们在其中 $x+n-1$ 个位置插入 $n-1$ 个隔板，从而将实际的 $x$ 个球分成 $n$ 组，并且允许盒子为空，因此方案数为 $C_{x+n-1}^{n-1}$。

因此，对于每个查询 $queries[i]$，我们可以先对 $k$ 进行质因数分解，得到指数 $x_1,x_2,\cdots ,x_m$，然后计算 $C_{x_1+n-1}^{n-1},C_{x_2+n-1}^{n-1},\cdots ,C_{x_m+n-1}^{n-1}$，最后将所有的方案数相乘即可。

所以，问题转化为如何快速计算 $C_m^n$，根据公式 $C_m^n=\frac{m!}{n!(m-n)!}$，我们可以先预处理出 $m!$，然后利用逆元快速计算 $C_m^n$。

时间复杂度 $O(K\times \log \log K+N+m\times \log K)$，空间复杂度 $O(N)$。

const n = 1e4 + 20
const mod = 1e9 + 7

var f = make([]int, n)
var g = make([]int, n)
var p = make([][]int, n)

func qmi(a, k, p int) int {
	res := 1
	for k != 0 {
		if k&1 == 1 {
			res = res * a % p
		}
		k >>= 1
		a = a * a % p
	}
	return res
}

func init() {
	f[0], g[0] = 1, 1
	for i := 1; i < n; i++ {
		f[i] = f[i-1] * i % mod
		g[i] = qmi(f[i], mod-2, mod)
		x := i
		for j := 2; j <= x/j; j++ {
			if x%j == 0 {
				cnt := 0
				for x%j == 0 {
					cnt++
					x /= j
				}
				p[i] = append(p[i], cnt)
			}
		}
		if x > 1 {
			p[i] = append(p[i], 1)
		}
	}
}

func comb(n, k int) int {
	return (f[n] * g[k] % mod) * g[n-k] % mod
}

func waysToFillArray(queries [][]int) (ans []int) {
	for _, q := range queries {
		n, k := q[0], q[1]
		t := 1
		for _, x := range p[k] {
			t = t * comb(x+n-1, n-1) % mod
		}
		ans = append(ans, t)
	}
	return
}

力扣原题 · Doocs 题解来源

1745. 分割回文串 IV

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

 

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

 

提示：

• 3 <= s.length <= 2000
• s​​​​​​ 只包含小写英文字母。

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

思考

要把串切成三段回文。若对每段现判回文，三段枚举达 $O(n^3)$ 次检测。 $n$ 可达数百，宜先预处理回文。

$f[i][j]$ 表示 $s[i..j]$ 是否回文，按区间长度转移后，枚举两道切口验证三段即可，总时间 $O(n^2)$。

我们定义 $f[i][j]$ 表示字符串 $s$ 的第 $i$ 个字符到第 $j$ 个字符是否为回文串，初始时 $f[i][j]=\mathit{\text{true}}$。

然后我们可以通过以下的状态转移方程来计算 $f[i][j]$：

$$f[i][j]=\{\begin{array}{ll}\mathit{\text{true}},& \text{if }s[i]=s[j]\text{ and }(i+1=j\text{ or }f[i+1][j-1])\\ \mathit{\text{false}},& \text{otherwise}\end{array}$$

由于 $f[i][j]$ 依赖于 $f[i+1][j-1]$，因此，我们需要从大到小的顺序枚举 $i$，从小到大的顺序枚举 $j$，这样才能保证当计算 $f[i][j]$ 时 $f[i+1][j-1]$ 已经被计算过。

接下来，我们枚举第一个子串的右端点 $i$，第二个子串的右端点 $j$，那么第三个子串的左端点可以枚举的范围为 $[j+1,n-1]$，其中 $n$ 是字符串 $s$ 的长度。如果第一个子串 $s[0..i]$、第二个子串 $s[i+1..j]$ 和第三个子串 $s[j+1..n-1]$ 都是回文串，那么我们就找到了一种可行的分割方案，返回 $\mathit{\text{true}}$。

枚举完所有的分割方案后，如果没有找到符合要求的分割方案，那么返回 $\mathit{\text{false}}$。

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

func checkPartitioning(s string) bool {
	n := len(s)
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, n)
		for j := range f[i] {
			f[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = s[i] == s[j] && (i+1 == j || f[i+1][j-1])
		}
	}
	for i := 0; i < n-2; i++ {
		for j := i + 1; j < n-1; j++ {
			if f[0][i] && f[i+1][j] && f[j+1][n-1] {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

1746. 经过一次操作后的最大子数组和 🔒

中等1 种解法

标签：数组、动态规划

题目、示例与约束

你有一个整数数组 nums。你只能将一个元素 nums[i] 替换为 nums[i] * nums[i]。

返回替换后的最大子数组和。

 

示例 1：

输入：nums = [2,-1,-4,-3]
输出：17
解释：你可以把-4替换为16(-4*(-4))，使nums = [2,-1,16,-3]. 现在，最大子数组和为 2 + -1 + 16 = 17.

示例 2：

输入：nums = [1,-1,1,1,-1,-1,1]
输出：4
解释：你可以把第一个-1替换为1，使 nums = [1,1,1,1,-1,-1,1]. 现在，最大子数组和为 1 + 1 + 1 + 1 = 4.

 

提示：

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

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

思考

必须将恰好一个元素改成平方，再求最大子段和。枚举替换位置后做 Kadane 是 $O(n^2)$， $n\le {10}^5$ 不可行。

以当前位置结尾时，替换可以尚未发生或已经发生。前者即普通 Kadane；后者来自「此前未替换并在此平方」或「此前已替换并加上当前值」。

两个滚动变量 $f,g$ 分别维护这两种结尾状态，取全程最大。

我们定义 $f[i]$ 表示以 $nums[i]$ 结尾，且没有进行替换的最大子数组和，另外定义 $g[i]$ 表示以 $nums[i]$ 结尾，且进行了替换的最大子数组和。那么有如下状态转移方程：

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

最终答案即为所有 $max(f[i],g[i])$ 的最大值。

由于 $f[i]$ 只与 $f[i-1]$ 有关，因此我们可以只用两个变量来维护 $f[i]$ 和 $g[i]$ 的值，从而将空间复杂度降低到 $O(1)$。

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

func maxSumAfterOperation(nums []int) int {
	var f, g int
	ans := -(1 << 30)
	for _, x := range nums {
		ff := max(f, 0) + x
		gg := max(max(f, 0)+x*x, g+x)
		f, g = ff, gg
		ans = max(ans, max(f, g))
	}
	return ans
}

力扣原题 · Doocs 题解来源

1749. 任意子数组和的绝对值的最大值

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

abs(x) 定义如下：

• 如果 x 是负整数，那么 abs(x) = -x 。
• 如果 x 是非负整数，那么 abs(x) = x 。

 

示例 1：

输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。

示例 2：

输入：nums = [2,-5,1,-4,3,-2]
输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。

 

提示：

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

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

思考

子数组和的绝对值最大，等于最大子段和与最小子段和绝对值之中的较大者。

Kadane 同时维护以当前位置结尾的最大和 $f$ 与最小和 $g$，答案取 $f$ 与 $|g|$ 的全程最大。

我们定义 $f[i]$ 表示以 $nums[i]$ 结尾的子数组的和的最大值，定义 $g[i]$ 表示以 $nums[i]$ 结尾的子数组的和的最小值。那么 $f[i]$ 和 $g[i]$ 的状态转移方程如下：

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

最后答案为 $max(f[i],|g[i]|)$ 的最大值。

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

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

func maxAbsoluteSum(nums []int) (ans int) {
	var f, g int
	for _, x := range nums {
		f = max(f, 0) + x
		g = min(g, 0) + x
		ans = max(ans, max(f, abs(g)))
	}
	return
}

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

力扣原题 · Doocs 题解来源

1751. 最多可以参加的会议数目 II

困难3 种解法

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

题目、示例与约束

给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和 。

 

示例 1：

输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。

示例 2：

输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。

示例 3：

输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。

 

提示：

• 1 <= k <= events.length
• 1 <= k * events.length <= 106
• 1 <= startDayi <= endDayi <= 109
• 1 <= valuei <= 106

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

思考

最多参加 $k$ 个不重叠会议，价值和最大。按开始时间排序后，选或不选当前会议，下一场可用二分定位。

$\mathit{\text{dfs}}(i,k)$ 表示从第 $i$ 场起还剩 $k$ 次机会。不选走 $i+1$；选则在结束日后二分第一个可参加的 $j$，并加上价值。记忆化避免重复状态。

我们先将会议按照开始时间从小到大排序，然后设计一个函数 $\text{dfs}(i,k)$ 表示从第 $i$ 个会议开始，最多参加 $k$ 个会议的最大价值和。答案即为 $\text{dfs}(0,k)$。

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

如果不参加第 $i$ 个会议，那么最大价值和就是 $\text{dfs}(i+1,k)$；如果参加第 $i$ 个会议，我们可以通过二分查找，找到第一个开始时间大于第 $i$ 个会议结束时间的会议，记为 $j$，那么最大价值和就是 $\text{dfs}(j,k-1)+\text{value}[i]$。取二者的较大值即可。即：

$$\text{dfs}(i,k)=max(\text{dfs}(i+1,k),\text{dfs}(j,k-1)+\text{value}[i])$$

其中 $j$ 为第一个开始时间大于第 $i$ 个会议结束时间的会议，可以通过二分查找得到。

由于函数 $\text{dfs}(i,k)$ 的计算过程中，会调用 $\text{dfs}(i+1,k)$ 和 $\text{dfs}(j,k-1)$，因此我们可以使用记忆化搜索，将计算过的值保存下来，避免重复计算。

时间复杂度 $O(n\times \log n+n\times k)$，空间复杂度 $O(n\times k)$，其中 $n$ 为会议数量。

func maxValue(events [][]int, k int) int {
	sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] })
	n := len(events)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	var dfs func(i, k int) int
	dfs = func(i, k int) int {
		if i >= n || k <= 0 {
			return 0
		}
		if f[i][k] > 0 {
			return f[i][k]
		}
		j := sort.Search(n, func(h int) bool { return events[h][0] > events[i][1] })
		ans := max(dfs(i+1, k), dfs(j, k-1)+events[i][2])
		f[i][k] = ans
		return ans
	}
	return dfs(0, k)
}

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

思考

方法一按开始时间排序，并从末尾填一张后缀表。这里改按结束时间排序， $f[i][j]$ 为前 $i$ 个会议选 $j$ 个的最大价值，转移时二分最后一个不冲突的会议。

方法一按开始时间排序并从末尾填表。这里改按结束时间排序，定义前缀表。

先将会议排序，这次我们按照结束时间从小到大排序。然后定义 $f[i][j]$ 表示前 $i$ 个会议中，最多参加 $j$ 个会议的最大价值和。答案即为 $f[n][k]$。

对于第 $i$ 个会议，我们可以选择参加或者不参加。如果不参加，那么最大价值和就是 $f[i][j]$，如果参加，我们可以通过二分查找，找到最后一个结束时间小于第 $i$ 个会议开始时间的会议，记为 $h$，那么最大价值和就是 $f[h+1][j-1]+\text{value}[i]$。取二者的较大值即可。即：

$$f[i+1][j]=max(f[i][j],f[h+1][j-1]+\text{value}[i])$$

其中 $h$ 为最后一个结束时间小于第 $i$ 个会议开始时间的会议，可以通过二分查找得到。

时间复杂度 $O(n\times \log n+n\times k)$，空间复杂度 $O(n\times k)$，其中 $n$ 为会议数量。

相似题目：

• 1235. 规划兼职工作
• 2008. 出租车的最大盈利

func maxValue(events [][]int, k int) int {
	sort.Slice(events, func(i, j int) bool { return events[i][1] < events[j][1] })
	n := len(events)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		st, val := events[i-1][0], events[i-1][2]
		p := sort.Search(i, func(j int) bool { return events[j][1] >= st })
		for j := 1; j <= k; j++ {
			f[i][j] = max(f[i-1][j], f[p][j-1]+val)
		}
	}
	return f[n][k]
}

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

思考

最多参加 $k$ 个不重叠会议，价值和最大。 $k\times n\le {10}^6$，因此 $n$ 本身可以到 ${10}^6$，枚举子集不可行。

按开始时间排序后，不参加当前会议会先以同样的剩余次数调用 $i+1$，调用链长度为 $n$，栈会溢出。

更靠后的会议和更少的参加次数，在从末尾往前走时已经就绪。令 $f[i][c]$ 为从第 $i$ 场起最多参加 $c$ 场的最大价值和，从 $i=n-1$ 填到 $0$。

我们先将会议按照开始时间从小到大排序。令 $f[i][c]$ 表示从第 $i$ 个会议开始，最多参加 $c$ 个会议的最大价值和。答案为 $f[0][k]$，且 $f[n][c]=0$。

我们从 $i=n-1$ 填到 $0$。不参加第 $i$ 个会议，价值和为 $f[i+1][c]$。当 $c>0$ 且参加第 $i$ 个会议时，通过二分查找找到第一个开始时间大于其结束时间的会议 $j$，价值和为 $f[j][c-1]+\text{value}[i]$。取二者的较大值：

$$f[i][c]=max(f[i+1][c],f[j][c-1]+\text{value}[i])$$

其中 $j$ 为第一个开始时间大于第 $i$ 个会议结束时间的会议。因为 $j>i$， $f[j]$ 已经算过。

时间复杂度 $O(n\times \log n+n\times k)$，空间复杂度 $O(n\times k)$，其中 $n$ 为会议数量。

func maxValue(events [][]int, k int) int {
	sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] })
	n := len(events)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	for i := n - 1; i >= 0; i-- {
		ed, val := events[i][1], events[i][2]
		j := sort.Search(n, func(h int) bool { return events[h][0] > ed })
		for c := 0; c <= k; c++ {
			f[i][c] = f[i+1][c]
			if c > 0 {
				f[i][c] = max(f[i][c], f[j][c-1]+val)
			}
		}
	}
	return f[0][k]
}

力扣原题 · Doocs 题解来源

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

困难2 种解法

标签：位运算、数组、双指针、动态规划、位掩码、排序、中途相遇

题目、示例与约束

给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。

返回 abs(sum - goal) 可能的 最小值 。

注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

 

示例 1：

输入：nums = [5,-7,3,5], goal = 6
输出：0
解释：选择整个数组作为选出的子序列，元素和为 6 。
子序列和与目标值相等，所以绝对差为 0 。

示例 2：

输入：nums = [7,-9,15,-2], goal = -5
输出：1
解释：选出子序列 [7,-9,-2] ，元素和为 -4 。
绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。

示例 3：

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

 

提示：

• 1 <= nums.length <= 40
• -107 <= nums[i] <= 107
• -109 <= goal <= 109

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

思考

子序列和最接近 $\mathit{\text{goal}}$。 $n\le 40$，全集枚举 $2^n$ 不可行，但 $2^{n/2}$ 可以。

将数组对半，DFS 得到左右所有子序列和。对每个左和在有序的右和中二分 $\mathit{\text{goal}}-l$，取最接近的两个候选。

每个数选或不选两种可能，所以 $n$ 个数就有 $2^n$ 种组合，由于 $n$ 最大为 $40$，枚举 $2^{40}$ 种组合显然会超时。

我们可以把数组分成左右两部分，分别求出两部分所有子序列和，记为 $left$ 和 $right$。最后，只需找到最接近 $goal$ 的 $left[i]+right[j]$。

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

相似题目：

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

func minAbsDifference(nums []int, goal int) int {
	n := len(nums)
	lsum := make([]int, 0)
	rsum := make([]int, 0)

	dfs(nums[:n/2], &lsum, 0, 0)
	dfs(nums[n/2:], &rsum, 0, 0)

	sort.Ints(rsum)
	res := math.MaxInt32

	for _, x := range lsum {
		t := goal - x
		l, r := 0, len(rsum)
		for l < r {
			m := int(uint(l+r) >> 1)
			if rsum[m] < t {
				l = m + 1
			} else {
				r = m
			}
		}
		if l < len(rsum) {
			res = min(res, abs(t-rsum[l]))
		}
		if l > 0 {
			res = min(res, abs(t-rsum[l-1]))
		}
	}

	return res
}

func dfs(nums []int, sum *[]int, i, cur int) {
	if i == len(nums) {
		*sum = append(*sum, cur)
		return
	}

	dfs(nums, sum, i+1, cur)
	dfs(nums, sum, i+1, cur+nums[i])
}

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

方法二 · Go 实现

思考

方法二仍是折半枚举与二分，只是 DFS 写成先不选再选的递归形态，逻辑与方法一相同，实现更紧凑。

func minAbsDifference(nums []int, goal int) int {
	n := len(nums)
	left := []int{}
	right := []int{}
	dfs(nums[:n>>1], &left, 0, 0)
	dfs(nums[n>>1:], &right, 0, 0)
	sort.Ints(right)
	ans := math.MaxInt32
	for _, x := range left {
		y := goal - x
		l, r := 0, len(right)
		for l < r {
			mid := (l + r) >> 1
			if right[mid] >= y {
				r = mid
			} else {
				l = mid + 1
			}
		}
		if l < len(right) {
			ans = min(ans, abs(y-right[l]))
		}
		if l > 0 {
			ans = min(ans, abs(y-right[l-1]))
		}
	}
	return ans
}

func dfs(arr []int, res *[]int, i, s int) {
	if i == len(arr) {
		*res = append(*res, s)
		return
	}
	dfs(arr, res, i+1, s)
	dfs(arr, res, i+1, s+arr[i])
}

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

力扣原题 · Doocs 题解来源

1770. 执行乘法运算的最大分数

困难2 种解法

标签：数组、动态规划

题目、示例与约束

给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。

初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：

• 选择数组 nums 开头处或者末尾处 的整数 x 。
• 你获得 multipliers[i] * x 分，并累加到你的分数中。
• 将 x 从数组 nums 中移除。

在执行 m 步操作后，返回 最大 分数。

 

示例 1：

输入：nums = [1,2,3], multipliers = [3,2,1]
输出：14
解释：一种最优解决方案如下：
- 选择末尾处的整数 3 ，[1,2,3] ，得 3 * 3 = 9 分，累加到分数中。
- 选择末尾处的整数 2 ，[1,2] ，得 2 * 2 = 4 分，累加到分数中。
- 选择末尾处的整数 1 ，[1] ，得 1 * 1 = 1 分，累加到分数中。
总分数为 9 + 4 + 1 = 14 。

示例 2：

输入：nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
输出：102
解释：一种最优解决方案如下：
- 选择开头处的整数 -5 ，[-5,-3,-3,-2,7,1] ，得 -5 * -10 = 50 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-3,-2,7,1] ，得 -3 * -5 = 15 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-2,7,1] ，得 -3 * 3 = -9 分，累加到分数中。
- 选择末尾处的整数 1 ，[-2,7,1] ，得 1 * 4 = 4 分，累加到分数中。
- 选择末尾处的整数 7 ，[-2,7] ，得 7 * 6 = 42 分，累加到分数中。
总分数为 50 + 15 - 9 + 4 + 42 = 102 。

 

提示：

• n == nums.length
• m == multipliers.length
• 1 <= m <= 103
• m <= n <= 105
• -1000 <= nums[i], multipliers[i] <= 1000

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

思考

每次只能取 $nums$ 两端之一与 $\mathit{\text{multipliers}}[k]$ 相乘。 $m$ 次操作后 $nums$ 只动两端，状态可用「左取了几个、右取了几个」描述。

记忆化 $f(i,j,k)$：左指针 $i$、右指针 $j$、第 $k$ 个乘数。转移为取左或取右，边界是 $k=m$。状态数 $O(m^2)$。

我们设计一个函数 $dfs(i,j)$，表示从 nums 数组头部第 $i$ 个元素开始，从 nums 数组尾部第 $j$ 个元素开始，能够获得的最大分数。那么答案就是 $dfs(0,0)$。

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

• 如果 $i\ge m$ 或者 $j\ge m$，或者 $i+j\ge m$，说明已经没有元素可以选择了，返回 $0$。
• 否则，我们可以选择 nums 数组头部第 $i$ 个元素，那么能够获取的最大分数为 $nums[i]\times multipliers[i+j]+dfs(i+1,j)$；或者我们可以选择 nums 数组尾部第 $j$ 个元素，那么能够获取的最大分数为 $nums[n-j-1]\times multipliers[i+j]+dfs(i,j+1)$。我们取两者的最大值作为 $dfs(i,j)$ 的返回值。

我们可以使用记忆化搜索来实现上述递归过程，其中 f 数组用于存储函数 $dfs(i,j)$ 的返回值，防止重复计算。

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

func maximumScore(nums []int, multipliers []int) int {
	n, m := len(nums), len(multipliers)
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, m)
		for j := range f[i] {
			f[i][j] = 1 << 30
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= m || j >= m || i+j >= m {
			return 0
		}
		if f[i][j] != 1<<30 {
			return f[i][j]
		}
		k := i + j
		a := dfs(i+1, j) + nums[i]*multipliers[k]
		b := dfs(i, j+1) + nums[n-j-1]*multipliers[k]
		f[i][j] = max(a, b)
		return f[i][j]
	}
	return dfs(0, 0)
}

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

思考

将记忆化改成递推： $f[i][j]$ 表示取了前 $i$ 个与后 $j$ 个的最大得分，按 $i+j$ 递增填表，在 $i+j=m$ 处更新答案。避免递归，复杂度同为 $O(m^2)$。

我们可以将方法一中的记忆化搜索改写为动态规划的形式。

我们用 $f[i][j]$ 表示取数组 $nums$ 的前 $i$ 个元素，以及取数组 $nums$ 的后 $j$ 个元素，能够获得的最大分数。初始时 $f[0][0]=0$，其余元素均为 $-\mathrm{\infty }$。答案为 $\underset{0\le i\le m}{max}f[i][m-i]$。

考虑 $f[i][j]$，那么当前我们可以选择 nums 数组头部的第 $i$ 个元素，或者选择 nums 数组尾部的第 $j$ 个元素。如果选择了 nums 数组头部的第 $i$ 个元素，那么能够获得的最大分数为 $f[i-1][j]+nums[i-1]\times multipliers[i+j-1]$；如果选择了 nums 数组尾部的第 $j$ 个元素，那么能够获得的最大分数为 $f[i][j-1]+nums[n-j]\times multipliers[i+j-1]$。我们取两者的最大值作为 $f[i][j]$ 的值。如果 $i+j=m$，我们我们更新答案 $ans=max(ans,f[i][j])$。

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

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

func maximumScore(nums []int, multipliers []int) int {
	const inf int = 1 << 30
	n, m := len(nums), len(multipliers)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, m+1)
		for j := range f {
			f[i][j] = -inf
		}
	}
	f[0][0] = 0
	ans := -inf
	for i := 0; i <= m; i++ {
		for j := 0; j <= m-i; j++ {
			k := i + j - 1
			if i > 0 {
				f[i][j] = max(f[i][j], f[i-1][j]+multipliers[k]*nums[i-1])
			}
			if j > 0 {
				f[i][j] = max(f[i][j], f[i][j-1]+multipliers[k]*nums[n-j])
			}
			if i+j == m {
				ans = max(ans, f[i][j])
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1771. 由子序列构造的最长回文串的长度

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：

• 从 word1 中选出某个 非空 子序列 subsequence1 。
• 从 word2 中选出某个 非空 子序列 subsequence2 。
• 连接两个子序列 subsequence1 + subsequence2 ，得到字符串。

返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 0 。

字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

 

示例 1：

输入：word1 = "cacb", word2 = "cbba"
输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。

示例 2：

输入：word1 = "ab", word2 = "ab"
输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。

示例 3：

输入：word1 = "aa", word2 = "bb"
输出：0
解释：无法按题面所述方法构造回文串，所以返回 0 。

 

提示：

• 1 <= word1.length, word2.length <= 1000
• word1 和 word2 由小写英文字母组成

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

思考

从两串各取非空子序列拼接成回文，求最长长度。拼接后即在 $s=\mathit{\text{word1}}+\mathit{\text{word2}}$ 上求最长回文子序列，但两端必须分属两串。

$f[i][j]$ 为 $s[i..j]$ 的 LPS。 $s[i]=s[j]$ 时长度为内部加 $2$，且若 $i$ 在第一串、 $j$ 在第二串则更新答案；否则取少一端的较大者。

我们首先将字符串 word1 和 word2 连接起来，得到字符串 $s$，然后我们可以将问题转化为求字符串 $s$ 的最长回文子序列的长度。只不过这里在算最后的答案时，需要保证回文字符串中，至少有一个字符来自 word1，另一个字符来自 word2。

我们定义 $f[i][j]$ 表示字符串 $s$ 中下标范围在 $[i,j]$ 内的子串的最长回文子序列的长度。

如果 $s[i]=s[j]$，那么 $s[i]$ 和 $s[j]$ 一定在最长回文子序列中，此时 $f[i][j]=f[i+1][j-1]+2$，这时候我们还需要判断 $s[i]$ 和 $s[j]$ 是否来自 word1 和 word2，如果是，我们将答案的最大值更新为 $ans=max(ans,f[i][j])$。

如果 $s[i]\ne s[j]$，那么 $s[i]$ 和 $s[j]$ 一定不会同时出现在最长回文子序列中，此时 $f[i][j]=max(f[i+1][j],f[i][j-1])$。

最后我们返回答案即可。

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

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

力扣原题 · Doocs 题解来源