LeetCode Go · 动态规划（12）

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

来源与许可

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

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

2305. 公平分发饼干

中等1 种解法

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

题目、示例与约束

给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量，所有 零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。

分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。

返回所有分发的最小不公平程度。

 

示例 1：

输入：cookies = [8,15,10,20,8], k = 2
输出：31
解释：一种最优方案是 [8,15,8] 和 [10,20] 。
- 第 1 个孩子分到 [8,15,8] ，总计 8 + 15 + 8 = 31 块饼干。
- 第 2 个孩子分到 [10,20] ，总计 10 + 20 = 30 块饼干。
分发的不公平程度为 max(31,30) = 31 。
可以证明不存在不公平程度小于 31 的分发方案。

示例 2：

输入：cookies = [6,1,3,2,2,4,1,2], k = 3
输出：7
解释：一种最优方案是 [6,1]、[3,2,2] 和 [4,1,2] 。
- 第 1 个孩子分到 [6,1] ，总计 6 + 1 = 7 块饼干。 
- 第 2 个孩子分到 [3,2,2] ，总计 3 + 2 + 2 = 7 块饼干。
- 第 3 个孩子分到 [4,1,2] ，总计 4 + 1 + 2 = 7 块饼干。
分发的不公平程度为 max(7,7,7) = 7 。
可以证明不存在不公平程度小于 7 的分发方案。

 

提示：

• 2 <= cookies.length <= 8
• 1 <= cookies[i] <= 105
• 2 <= k <= cookies.length

方法一：回溯 + 剪枝 · Go 实现

思考

要把 $n\le 8$ 包饼干分给 $k\le 8$ 个孩子并最小化最大份量。若无约束地枚举分配，状态数为 $k^n$，在上限附近过于庞大。

同一分配的不公平度与包的先后无关，但大包先放更容易触发剪枝。将包降序排列后回溯：若某孩子加上当前包已不小于已知答案则跳过；相邻孩子份量相同则视为对称，只尝试一种。全部包分完后用当前最大值更新答案。

我们先对数组 $cookies$ 进行降序排序（减少搜索次数），然后创建一个长度为 $k$ 的数组 $cnt$，用于存储每个孩子分到的饼干数量。另外，用变量 $ans$ 维护当前的最小不公平程度，初始化一个很大的值。

接下来，我们从第一个零食包开始，对于当前零食包 $i$，我们枚举每个孩子 $j$，如果当前零食包中的饼干 $cookies[i]$ 分给孩子 $j$ 后，使得不公平程度大于等于 $ans$，或者当前孩子已有的饼干数量与前一个孩子相同，那么我们不需要考虑将当前零食包中的饼干分给孩子 $j$，直接跳过（剪枝）。否则，我们将当前零食包中的饼干 $cookies[i]$ 分给孩子 $j$，然后继续考虑下一个零食包。当我们考虑完所有的零食包后，更新 $ans$ 的值，然后回溯到上一个零食包，继续枚举当前零食包中的饼干分给哪个孩子。

最后，我们返回 $ans$ 即可。

func distributeCookies(cookies []int, k int) int {
	sort.Sort(sort.Reverse(sort.IntSlice(cookies)))
	cnt := make([]int, k)
	ans := 1 << 30
	var dfs func(int)
	dfs = func(i int) {
		if i >= len(cookies) {
			ans = slices.Max(cnt)
			return
		}
		for j := 0; j < k; j++ {
			if cnt[j]+cookies[i] >= ans || (j > 0 && cnt[j] == cnt[j-1]) {
				continue
			}
			cnt[j] += cookies[i]
			dfs(i + 1)
			cnt[j] -= cookies[i]
		}
	}
	dfs(0)
	return ans
}

力扣原题 · Doocs 题解来源

2310. 个位数字为 K 的整数之和

中等2 种解法

标签：贪心、数学、动态规划、枚举

题目、示例与约束

给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集：

• 每个整数个位数字都是 k 。
• 所有整数之和是 num 。

返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。

注意：

• 多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。
• 个位数字 是数字最右边的数位。

 

示例 1：

输入：num = 58, k = 9
输出：2
解释：
多重集 [9,49] 满足题目条件，和为 58 且每个整数的个位数字是 9 。
另一个满足条件的多重集是 [19,39] 。
可以证明 2 是满足题目条件的多重集的最小长度。

示例 2：

输入：num = 37, k = 2
输出：-1
解释：个位数字为 2 的整数无法相加得到 37 。

示例 3：

输入：num = 0, k = 7
输出：0
解释：空多重集的和为 0 。

 

提示：

• 0 <= num <= 3000
• 0 <= k <= 9

方法一：数学 + 枚举 · Go 实现

思考

每个加数形如 $10x+k$，故 $n$ 个数之和的个位由 $n\times k$ 决定。 $num\le 3000$，枚举个数 $n$ 并检验 $num-n\times k$ 是否为 $10$ 的非负倍数即可。

从小到大尝试 $n$，第一个满足条件者即为最少个数；若直至 $num$ 仍不成立则无解。

符合拆分条件的每个数都可以表示成 $10x_i+k$，若总共有 $n$ 个数，那么 $\mathit{\text{num}}-n\times k$ 必然是 $10$ 的倍数。

我们从小到达枚举 $n$，找到第一个满足 $\mathit{\text{num}}-n\times k$ 是 $10$ 的倍数的 $n$。由于 $n$ 不会超过 $\mathit{\text{num}}$，因此 $n$ 最大枚举至 $\mathit{\text{num}}$。

也可以只考虑个位，个位满足，高位随意。

时间复杂度 $O(n)$，其中 $n$ 为 $\mathit{\text{num}}$ 的大小。空间复杂度 $O(1)$。

func minimumNumbers(num int, k int) int {
	if num == 0 {
		return 0
	}
	for i := 1; i <= num; i++ {
		t := num - k*i
		if t >= 0 && t%10 == 0 {
			return i
		}
	}
	return -1
}

方法二：数学 + 枚举（个位） · Go 实现

思考

方法一最多枚举 $num$ 次。个位以 $10$ 为周期，因此只需检查 $n\le 10$ 是否使 $n\times k$ 与 $num$ 同余且不超过 $num$，常数更小。

只需枚举个数 $n\le 10$，使 $n\times k$ 与 $\mathit{\text{num}}$ 个位相同且不超过 $\mathit{\text{num}}$。

func minimumNumbers(num int, k int) int {
	if num == 0 {
		return 0
	}
	for i := 1; i <= 10; i++ {
		if (k*i)%10 == num%10 && k*i <= num {
			return i
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

2311. 小于等于 K 的最长二进制子序列

中等1 种解法

标签：贪心、记忆化、字符串、动态规划

题目、示例与约束

给你一个二进制字符串 s 和一个正整数 k 。

请你返回 s 的 最长 子序列的长度，且该子序列对应的 二进制 数字小于等于 k 。

注意：

• 子序列可以有 前导 0 。
• 空字符串视为 0 。
• 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

 

示例 1：

输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。

示例 2：

输入：s = "00101001", k = 1
输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。

 

提示：

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

方法一：贪心 · Go 实现

思考

子序列对应的数值须 $\le k$。 $s$ 长至多 $1000$，枚举子集不可行。所有 $0$ 不增加数值，理应全部保留。

高位的 $1$ 代价更大，因此从右向左考虑能否再收一个 $1$。用当前已选长度作为该 $1$ 的权值下标，若并入后仍 $\le k$ 则收下。超过约 $30$ 位必然大于 $k$，可直接跳过。

最长二进制子序列必然包含原字符串中所有的 $0$，在此基础上，我们从右到左遍历 $s$，若遇到 $1$，判断子序列能否添加 $1$，使得子序列对应的二进制数字 $v\le k$。

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

func longestSubsequence(s string, k int) (ans int) {
	for i, v := len(s)-1, 0; i >= 0; i-- {
		if s[i] == '0' {
			ans++
		} else if ans < 30 && (v|1<<ans) <= k {
			v |= 1 << ans
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2312. 卖木头块

困难2 种解法

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

题目、示例与约束

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

• 沿垂直方向按高度 完全 切割木块，或
• 沿水平方向按宽度 完全 切割木块

在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块来交换它的高度值和宽度值。

请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。

注意你可以切割木块任意次。

 

示例 1：

输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出：19
解释：上图展示了一个可行的方案。包括：
- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。

示例 2：

输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出：32
解释：上图展示了一个可行的方案。包括：
- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。

 

提示：

• 1 <= m, n <= 200
• 1 <= prices.length <= 2 * 104
• prices[i].length == 3
• 1 <= hi <= m
• 1 <= wi <= n
• 1 <= pricei <= 106
• 所有 (hi, wi) 互不相同 。

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

思考

木块可反复横切或竖切，每块也可整块出售。搜索所有切割序列会大量重复同一尺寸。 $m,n\le 200$，不同矩形只有 $O(mn)$ 种。

子问题只由高、宽决定：整卖价格与一次切开后两块最优值之和取最大。用哈希表记下给定价格，记忆化搜索 $dfs(h,w)$，横切只枚举到一半以免对称重复。

我们先定义一个二维数组 $d$，其中 $d[i][j]$ 表示高为 $i$，宽为 $j$ 的木块的价格。初始时，我们遍历价格数组 $prices$，将每一块木块 $(h,w,p)$ 的价格 $p$ 存入 $d[h][w]$ 中，其余价格为 $0$。

然后我们设计一个函数 $dfs(h,w)$，表示对一块高为 $h$，宽为 $w$ 的木块切割后能得到的最多钱数。答案就是 $dfs(m,n)$。

函数 $dfs(h,w)$ 的执行过程如下：

• 如果 $(h,w)$ 已经被计算过了，直接返回答案。
• 否则，我们先初始化答案为 $d[h][w]$，然后枚举切割的位置，分别计算切割后的两块木块能得到的最多钱数，取最大值即可。

时间复杂度 $O(m\times n\times (m+n)+p)$，空间复杂度 $O(m\times n)$。其中 $p$ 表示价格数组的长度，而 $m$ 和 $n$ 分别表示木块的高和宽。

func sellingWood(m int, n int, prices [][]int) int64 {
	f := make([][]int64, m+1)
	d := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int64, n+1)
		for j := range f[i] {
			f[i][j] = -1
		}
		d[i] = make([]int, n+1)
	}
	for _, p := range prices {
		d[p[0]][p[1]] = p[2]
	}
	var dfs func(int, int) int64
	dfs = func(h, w int) int64 {
		if f[h][w] != -1 {
			return f[h][w]
		}
		ans := int64(d[h][w])
		for i := 1; i < h/2+1; i++ {
			ans = max(ans, dfs(i, w)+dfs(h-i, w))
		}
		for i := 1; i < w/2+1; i++ {
			ans = max(ans, dfs(h, i)+dfs(h, w-i))
		}
		f[h][w] = ans
		return ans
	}
	return dfs(m, n)
}

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

思考

方法一依赖递归与缓存，常数与调用开销较大。按面积从小到大填表，同一转移写成两重循环，语义不变而避免递归栈，并便于滚动或并行扩展。

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

与方法一类似，我们定义一个二维数组 $d$，其中 $d[i][j]$ 表示高为 $i$，宽为 $j$ 的木块的价格。初始时，我们遍历价格数组 $prices$，将每一块木块 $(h,w,p)$ 的价格 $p$ 存入 $d[h][w]$ 中，其余价格为 $0$。

然后，我们定义另一个二维数组 $f$，其中 $f[i][j]$ 表示对一块高为 $i$，宽为 $j$ 的木块切割后能得到的最多钱数。答案就是 $f[m][n]$。

考虑 $f[i][j]$ 如何转移，初始时 $f[i][j]=d[i][j]$。我们枚举切割的位置，分别计算切割后的两块木块能得到的最多钱数，取最大值即可。

时间复杂度 $O(m\times n\times (m+n)+p)$，空间复杂度 $O(m\times n)$。其中 $p$ 表示价格数组的长度，而 $m$ 和 $n$ 分别表示木块的高和宽。

相似题目：

• 1444. 切披萨的方案数

func sellingWood(m int, n int, prices [][]int) int64 {
	d := make([][]int, m+1)
	f := make([][]int64, m+1)
	for i := range d {
		d[i] = make([]int, n+1)
		f[i] = make([]int64, n+1)
	}
	for _, p := range prices {
		d[p[0]][p[1]] = p[2]
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			f[i][j] = int64(d[i][j])
			for k := 1; k < i; k++ {
				f[i][j] = max(f[i][j], f[k][j]+f[i-k][j])
			}
			for k := 1; k < j; k++ {
				f[i][j] = max(f[i][j], f[i][k]+f[i][j-k])
			}
		}
	}
	return f[m][n]
}

力扣原题 · Doocs 题解来源

2318. 不同骰子序列的数目

困难1 种解法

标签：记忆化、动态规划

题目、示例与约束

给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出 不同 骰子序列的数目：

1. 序列中任意 相邻 数字的 最大公约数 为 1 。
2. 序列中 相等 的值之间，至少有 2 个其他值的数字。正式地，如果第 i 次掷骰子的值 等于 第 j 次的值，那么 abs(i - j) > 2 。

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

如果两个序列中至少有一个元素不同，那么它们被视为不同的序列。

 

示例 1：

输入：n = 4
输出：184
解释：一些可行的序列为 (1, 2, 3, 4) ，(6, 1, 2, 3) ，(1, 2, 3, 1) 等等。
一些不可行的序列为 (1, 2, 1, 3) ，(1, 2, 3, 6) 。
(1, 2, 1, 3) 是不可行的，因为第一个和第三个骰子值相等且 abs(1 - 3) = 2 （下标从 1 开始表示）。
(1, 2, 3, 6) i是不可行的，因为 3 和 6 的最大公约数是 3 。
总共有 184 个不同的可行序列，所以我们返回 184 。

示例 2：

输入：n = 2
输出：22
解释：一些可行的序列为 (1, 2) ，(2, 1) ，(3, 2) 。
一些不可行的序列为 (3, 6) ，(2, 4) ，因为最大公约数不为 1 。
总共有 22 个不同的可行序列，所以我们返回 22 。

 

提示：

• 1 <= n <= 104

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

思考

长度为 $n\le {10}^4$ 的骰子序列，相邻两数须互素且不同，且不能与再前一个相同。直接递归会重复大量后缀。

合法性只依赖最近两个点数。令 $dp[k][i][j]$ 为长 $k$、末两位为 $i,j$ 的方案数，由满足 $gcd$ 与互异约束的前一位转移。骰面只有 $6$ 种，三维表可以接受。

三维 DP。

设 $dp[k][i][j]$ 表示序列长度为 $k$，且序列的最后两个数字分别为 $i$, $j$ 的所有满足要求的不同序列的数量。

func distinctSequences(n int) int {
	if n == 1 {
		return 6
	}
	dp := make([][][]int, n+1)
	for k := range dp {
		dp[k] = make([][]int, 6)
		for i := range dp[k] {
			dp[k][i] = make([]int, 6)
		}
	}
	for i := 0; i < 6; i++ {
		for j := 0; j < 6; j++ {
			if gcd(i+1, j+1) == 1 && i != j {
				dp[2][i][j] = 1
			}
		}
	}
	mod := int(1e9) + 7
	for k := 3; k <= n; k++ {
		for i := 0; i < 6; i++ {
			for j := 0; j < 6; j++ {
				if gcd(i+1, j+1) == 1 && i != j {
					for h := 0; h < 6; h++ {
						if gcd(h+1, i+1) == 1 && h != i && h != j {
							dp[k][i][j] = (dp[k][i][j] + dp[k-1][h][i]) % mod
						}
					}
				}
			}
		}
	}
	ans := 0
	for i := 0; i < 6; i++ {
		for j := 0; j < 6; j++ {
			ans = (ans + dp[n][i][j]) % mod
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

2320. 统计放置房子的方式数

中等1 种解法

标签：动态规划

题目、示例与约束

一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

 

示例 1：

输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。

示例 2：

输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。

 

提示：

• 1 <= n <= 104

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

思考

街道两侧独立，每侧相邻地块不能同时盖房。 $n\le {10}^4$，一侧方案数平方即答案。一侧若按位置搜索，状态可压缩为「上一块是否已建」。

令 $f[i]$、 $g[i]$ 分别表示前 $i+1$ 块中最后一块建或不建的方案。建则上一块必须空，不建则上一块任意。两侧相乘取模。

由于街道两侧房子的摆放互不影响，因此，我们可以只考虑一侧的摆放情况，最后将一侧的方案数平方取模得到最终结果。

我们定义 $f[i]$ 表示放置前 $i+1$ 个地块，且最后一个地块放置房子的方案数，定义 $g[i]$ 表示放置前 $i+1$ 个地块，且最后一个地块不放置房子的方案数。初始时 $f[0]=g[0]=1$。

当我们放置第 $i+1$ 个地块时，有两种情况：

• 如果第 $i+1$ 个地块放置房子，那么第 $i$ 个地块必须不放置房子，因此方案数 $f[i]=g[i-1]$；
• 如果第 $i+1$ 个地块不放置房子，那么第 $i$ 个地块可以放置房子，也可以不放置房子，因此方案数 $g[i]=f[i-1]+g[i-1]$。

最终，我们将 $f[n-1]+g[n-1]$ 的平方取模即为答案。

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

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

力扣原题 · Doocs 题解来源

2321. 拼接数组的最大分数

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。

你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right] 。

• 例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。

你可以选择执行上述操作 一次 或不执行任何操作。

数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。

返回 可能的最大分数 。

子数组 是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。

 

示例 1：

输入：nums1 = [60,60,60], nums2 = [10,90,10]
输出：210
解释：选择 left = 1 和 right = 1 ，得到 nums1 = [60,90,60] 和 nums2 = [10,60,10] 。
分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210 。

示例 2：

输入：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
输出：220
解释：选择 left = 3 和 right = 4 ，得到 nums1 = [20,40,20,40,20] 和 nums2 = [50,20,50,70,30] 。
分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220 。

示例 3：

输入：nums1 = [7,11,13], nums2 = [1,1,1]
输出：31
解释：选择不交换任何子数组。
分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31 。

 

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 104

方法一 · Go 实现

思考

只能交换一段对应子数组，目标是使某一个数组的元素和最大。 $n\le {10}^5$，不能枚举区间。交换 $[l,r]$ 后， $nums2$ 的和增加 $\sum (nums{1}_i-nums{2}_i)$ 在该区间上的值。

问题化为最大子段和：对差分数组做 Kadane，得到给 $nums2$ 的最大增益；对称地再算给 $nums1$ 的增益。与原数组和相加后取较大者。

func maximumsSplicedArray(nums1 []int, nums2 []int) int {
	s1, s2 := 0, 0
	n := len(nums1)
	for i, v := range nums1 {
		s1 += v
		s2 += nums2[i]
	}
	f := func(nums1, nums2 []int) int {
		t := nums1[0] - nums2[0]
		mx := t
		for i := 1; i < n; i++ {
			v := nums1[i] - nums2[i]
			if t > 0 {
				t += v
			} else {
				t = v
			}
			mx = max(mx, t)
		}
		return mx
	}
	return max(s2+f(nums1, nums2), s1+f(nums2, nums1))
}

力扣原题 · Doocs 题解来源

2327. 知道秘密的人数

中等1 种解法

标签：队列、动态规划、模拟

题目、示例与约束

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

 

提示：

• 2 <= n <= 1000
• 1 <= delay < forget <= n

方法一：差分数组 · Go 实现

思考

每人在得知后的 $[delay,forget)$ 天内每天各传给一人，第 $forget$ 天遗忘。 $n\le 1000$，按天模拟可行。

用 $cnt[i]$ 记第 $i$ 天新知情的人数，他们会在后续区间内每天复制自身份数。差分数组 $d$ 记录「仍记得」的人数增减，前 $n$ 天的前缀和即答案。

我们用一个差分数组 $d[i]$ 来记录第 $i$ 天知道秘密的人数变化情况，用一个数组 $cnt[i]$ 来记录第 $i$ 天新得知秘密的人数。

那么，对于第 $i$ 天新得知秘密的 $cnt[i]$ 个人来说，他们会在 $[i+\text{delay},i+\text{forget})$ 这段时间内每天都能分享给另外 $cnt[i]$ 个人。

答案为 $\sum _{i=1}^{n}d[i]$。

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

func peopleAwareOfSecret(n int, delay int, forget int) int {
	m := (n << 1) + 10
	d := make([]int, m)
	cnt := make([]int, m)
	mod := int(1e9) + 7
	cnt[1] = 1
	for i := 1; i <= n; i++ {
		if cnt[i] == 0 {
			continue
		}
		d[i] = (d[i] + cnt[i]) % mod
		d[i+forget] = (d[i+forget] - cnt[i] + mod) % mod
		nxt := i + delay
		for nxt < i+forget {
			cnt[nxt] = (cnt[nxt] + cnt[i]) % mod
			nxt++
		}
	}
	ans := 0
	for i := 1; i <= n; i++ {
		ans = (ans + d[i]) % mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

2338. 统计理想数组的数目

困难1 种解法

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

题目、示例与约束

给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。

对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：

• 每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。
• 每个 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。

返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 109 + 7 取余的结果。

 

示例 1：

输入：n = 2, maxValue = 5
输出：10
解释：存在以下理想数组：
- 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5]
- 以 2 开头的数组（2 个）：[2,2]、[2,4]
- 以 3 开头的数组（1 个）：[3,3]
- 以 4 开头的数组（1 个）：[4,4]
- 以 5 开头的数组（1 个）：[5,5]
共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。

示例 2：

输入：n = 5, maxValue = 3
输出：11
解释：存在以下理想数组：
- 以 1 开头的数组（9 个）：
   - 不含其他不同值（1 个）：[1,1,1,1,1] 
   - 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
   - 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- 以 2 开头的数组（1 个）：[2,2,2,2,2]
- 以 3 开头的数组（1 个）：[3,3,3,3,3]
共计 9 + 1 + 1 = 11 个不同理想数组。

 

提示：

• 2 <= n <= 104
• 1 <= maxValue <= 104

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

思考

理想数组要求后项能整除前项。 $n$ 与 $\mathit{\text{maxValue}}$ 均可达 ${10}^4$，不能枚举数组。一条严格倍增链的长度不超过 $\log \mathit{\text{maxValue}}$。

先统计以 $i$ 结尾、含 $j$ 个不同值的链数 $f[i][j]$，再把长度为 $j$ 的链用隔板法扩成 $n$ 位，乘组合数 $c_{n-1}^{j-1}$。组合数按行递推，链长上限取 $16$。

设 $f[i][j]$ 表示以 $i$ 结尾，且由 $j$ 个不同元素构成的序列的方案数。初始值 $f[i][1]=1$。

考虑 $n$ 个小球，最终划分为 $j$ 份，那么可以用“隔板法”，即在 $n-1$ 个位置上插入 $j-1$ 个隔板，那么组合数为 $c_{n-1}^{j-1}$。

我们可以预处理组合数 $c[i][j]$，根据递推公式 $c[i][j]=c[i-1][j]+c[i-1][j-1]$ 求得，特别地，当 $j=0$ 时， $c[i][j]=1$。

最终的答案为

$$\sum _{i=1}^k\sum _{j=1}^{{\log }_{2}k+1}f[i][j]\times c_{n-1}^{j-1}$$

其中 $k$ 表示数组的最大值，即 $\mathit{\text{maxValue}}$。

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

func idealArrays(n int, maxValue int) (ans int) {
	const mod = int(1e9 + 7)
	c := make([][]int, n)
	for i := 0; i < n; i++ {
		c[i] = make([]int, 16)
		for j := 0; j <= i && j < 16; j++ {
			if j == 0 {
				c[i][j] = 1
			} else {
				c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
			}
		}
	}

	f := make([][16]int, maxValue+1)
	for i := 1; i <= maxValue; i++ {
		f[i][1] = 1
	}
	for j := 1; j < 15; j++ {
		for i := 1; i <= maxValue; i++ {
			for k := 2; k*i <= maxValue; k++ {
				f[k*i][j+1] = (f[k*i][j+1] + f[i][j]) % mod
			}
		}
	}

	for i := 1; i <= maxValue; i++ {
		for j := 1; j < 16; j++ {
			ans = (ans + f[i][j]*c[n-1][j-1]) % mod
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2355. 你能拿走的最大图书数量 🔒

困难1 种解法

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

题目、示例与约束

给定一个长度为 n 的 下标从 0 开始 的整数数组 books，其中 books[i] 表示书架的第 i 个书架上的书的数量。

你要从书架 l 到 r 的一个 连续 的部分中取书，其中 0 <= l <= r < n。对于 l <= i < r 范围内的每个索引 i，你从书架 i 取书的数量必须 严格小于 你从书架 i + 1 取书的数量。

返回你能从书架上拿走的书的 最大 数量。

 

示例 1:

输入: books = [8,5,2,7,9]
输出: 19
解释:
- 从书架 1 上取 1 本书。
- 从书架 2 上取 2 本书。
- 从书架 3 上取 7 本书
- 从书架 4 上取 9 本书
你已经拿了19本书，所以返回 19。
可以证明 19 本是你所能拿走的书的最大数量。

示例 2:

输入: books = [7,0,3,4,5]
输出: 12
解释:
- 从书架 2 上取 3 本书。
- 从书架 3 上取 4 本书。
- 从书架 4 上取 5 本书。
你已经拿了 12 本书，所以返回 12。
可以证明 12 本是你所能拿走的书的最大数量。

示例 3:

输入: books = [8,2,3,7,3,4,0,1,4,3]
输出: 13
解释:
- 从书架 0 上取 1 本书。
- 从书架 1 上取 2 本书。
- 从书架 2 上取 3 本书。
- 从书架 3 上取 7 本书。
你已经拿了 13 本书，所以返回 13。
可以证明 13 本是你所能拿走的书的最大数量。

 

提示:

• 1 <= books.length <= 105
• 0 <= books[i] <= 105

方法一：单调栈 + 动态规划 · Go 实现

思考

从连续书架取书，且往左每层至少少一本。枚举右端后若再暴力找断裂点，总复杂度过高。

令 $nums[i]=books[i]-i$，断裂发生在左侧第一个更小的 $nums[j]$。单调栈预处理 $left[i]$，再以 $dp[i]$ 表示以 $i$ 为右端的最大取书量：中间一段是等差数列，左侧接上 $dp[j]$。

我们定义 $dp[i]$ 表示以书架 $i$ 为右端点时能取走的书的最大数量。令 $nums[i]=books[i]-i$。若往左的严格递减在某个 $j$ 处断开（ $0\le j<i$），则 $books[j]<books[i]-(i-j)$，也就是 $nums[j]<nums[i]$。用单调栈为每个位置求出左侧第一个严格更小的 $nums$，记为 $j$；不存在时 $j=-1$。

从 $j+1$ 到 $i$ 实际取走的本数是公差为 $1$ 的等差数列。其长度为 $cnt=min(books[i],i-j)$，末项为 $books[i]$，首项为 $u=books[i]-cnt+1$，和为 $s=(u+books[i])\times cnt/2$。于是 $dp[i]=s$，若 $j\ne -1$ 再加 $dp[j]$。

答案为 $\underset{i}{max}dp[i]$。

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

func maximumBooks(books []int) int64 {
	n := len(books)
	nums := make([]int, n)
	left := make([]int, n)
	for i, v := range books {
		nums[i] = v - i
		left[i] = -1
	}
	stk := []int{}
	for i, v := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	dp := make([]int, n)
	dp[0] = books[0]
	ans := 0
	for i, v := range books {
		j := left[i]
		cnt := min(v, i-j)
		u := v - cnt + 1
		s := (u + v) * cnt / 2
		dp[i] = s
		if j != -1 {
			dp[i] += dp[j]
		}
		ans = max(ans, dp[i])
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2361. 乘坐火车路线的最少费用 🔒

困难2 种解法

标签：数组、动态规划

题目、示例与约束

城市中的火车有两条路线，分别是常规路线和特快路线。两条路线经过 相同 的 n + 1 个车站，车站编号从 0 到 n。初始时，你位于车站 0 的常规路线。

给你两个 下标从 1 开始 、长度均为 n 的两个整数数组 regular 和 express ，其中 regular[i] 表示乘坐常规路线从车站 i - 1 到车站 i 的费用，express[i] 表示乘坐特快路线从车站 i - 1 到车站 i 的费用。

另外给你一个整数 expressCost，表示从常规路线转换到特快路线的费用。

注意：

• 从特快路线转换回常规路线没有费用。
• 每次 从常规路线转换到特快路线，你都需要支付 expressCost 的费用。
• 留在特快路线上没有额外费用。

返回 下标从 1 开始 、长度为 n 的数组 costs，其中 costs[i] 是从车站 0 到车站 i 的最少费用。

注意：每个车站都可以从任意一条路线 到达 。

 

示例 1：

输入：regular = [1,6,9,5], express = [5,2,3,10], expressCost = 8
输出：[1,7,14,19]
解释：上图展示了从车站 0 到车站 4 的最少费用方法。
- 乘坐常规路线从车站 0 到车站 1，费用是 1。
- 乘坐特快路线从车站 1 到车站 2，费用是 8 + 2 = 10。
- 乘坐特快路线从车站 2 到车站 3，费用是 3。
- 乘坐常规路线从车站 3 到车站 4，费用是 5。
总费用是 1 + 10 + 3 + 5 + 19。
注意到达其他车站的最少费用方法可以选择不同的路线。

示例 2：

输入：regular = [11,5,13], express = [7,10,6], expressCost = 3
输出：[10,15,24]
解释：上图展示了从车站 0 到车站 3 的最少费用方法。
- 乘坐特快路线从车站 0 到车站 1，费用是 3 + 7 = 10。
- 乘坐常规路线从车站 1 到车站 2，费用是 5。
- 乘坐特快路线从车站 2 到车站 3，费用是 3 + 6 = 9。
总费用是 10 + 5 + 9 = 24。
注意转换回特快路线时需要再次支付 expressCost 的费用。

 

提示：

• n == regular.length == express.length
• 1 <= n <= 105
• 1 <= regular[i], express[i], expressCost <= 105

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

思考

两线并行，特快首次上车另付 $expressCost$。 $n\le {10}^5$，须线性递推。到达第 $i$ 站的最小花费只与上一站所在线路有关。

令 $f[i]$、 $g[i]$ 分别为坐常规、特快到达 $i$ 的最小费用。常规可由任一线路加 $a_i$；特快可由常规加首乘费再加 $b_i$，或继续特快只加 $b_i$。第 $i$ 站答案为二者较小值。

我们定义 $f[i]$ 表示从车站 $0$ 到车站 $i$ 且到达车站 $i$ 时乘坐常规路线的最少费用，定义 $g[i]$ 表示从车站 $0$ 到车站 $i$ 且到达车站 $i$ 时乘坐特快路线的最少费用。初始时 $f[0]=0,g[0]=\mathrm{\infty }$。

接下来，我们考虑 $f[i]$ 和 $g[i]$ 如何进行状态转移。

如果我们到达车站 $i$ 乘坐的是常规路线，那么我们可以从车站 $i-1$ 乘坐常规路线或者从车站 $i-1$ 乘坐特快路线转换到常规路线。因此我们可以得到状态转移方程：

$$f[i]=min\{f[i-1]+a_i,g[i-1]+a_i\}$$

其中 $a_i$ 表示从车站 $i-1$ 到车站 $i$ 乘坐常规路线的费用。

如果我们到达车站 $i$ 乘坐的是特快路线，那么我们可以从车站 $i-1$ 乘坐常规路线转换到特快路线或者从车站 $i-1$ 乘坐特快路线。因此我们可以得到状态转移方程：

$$g[i]=min\{f[i-1]+expressCost+b_i,g[i-1]+b_i\}$$

其中 $b_i$ 表示从车站 $i-1$ 到车站 $i$ 乘坐特快路线的费用。

我们记答案数组为 $cost$，其中 $cost[i]$ 表示从车站 $0$ 到车站 $i$ 的最少费用。由于我们可以从任意一条路线到达车站 $i$，因此我们有 $cost[i]=min\{f[i],g[i]\}$。

最后返回 $cost$ 即可。

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

func minimumCosts(regular []int, express []int, expressCost int) []int64 {
	n := len(regular)
	f := make([]int, n+1)
	g := make([]int, n+1)
	g[0] = 1 << 30
	cost := make([]int64, n)
	for i := 1; i <= n; i++ {
		a, b := regular[i-1], express[i-1]
		f[i] = min(f[i-1]+a, g[i-1]+a)
		g[i] = min(f[i-1]+expressCost+b, g[i-1]+b)
		cost[i-1] = int64(min(f[i], g[i]))
	}
	return cost
}

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

思考

方法一保留整表。转移只用上一站的两个数，滚动为变量 $f,g$ 即可，额外空间降到常数，输出数组仍要 $O(n)$。

我们注意到 $f[i]$ 和 $g[i]$ 只依赖 $f[i-1]$ 和 $g[i-1]$，因此可以用两个变量滚动更新，将额外空间优化到 $O(1)$。

func minimumCosts(regular []int, express []int, expressCost int) []int64 {
	f, g := 0, 1<<30
	cost := make([]int64, len(regular))
	for i, a := range regular {
		b := express[i]
		ff := min(f+a, g+a)
		gg := min(f+expressCost+b, g+b)
		f, g = ff, gg
		cost[i] = int64(min(f, g))
	}
	return cost
}

力扣原题 · Doocs 题解来源

2369. 检查数组是否存在有效划分

中等3 种解法

标签：数组、动态规划

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：

1. 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
2. 子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
3. 子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。

如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

 

示例 1：

输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这是一种有效划分，所以返回 true 。

示例 2：

输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。

 

提示：

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

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

思考

划分由「两相等」「三相等」或「三连续递增」组成。 $n\le {10}^5$，递归划分会重叠。从下标 $i$ 出发是否合法只取决于 $i$ 之后的后缀。

记忆化 $dfs(i)$：尝试长度 $2$ 或 $3$ 的合法块并跳到块末。越界视为成功。

我们设计一个函数 $dfs(i)$，表示从下标 $i$ 开始是否存在一种有效划分。那么答案就是 $dfs(0)$。

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

• 如果 $i\ge n$，返回 $true$。
• 如果 $i$ 和 $i+1$ 下标的元素相等，那么可以选择将 $i$ 和 $i+1$ 作为一个子数组，递归调用 $dfs(i+2)$。
• 如果 $i$, $i+1$ 和 $i+2$ 下标的元素相等，那么可以选择将 $i$, $i+1$ 和 $i+2$ 作为一个子数组，递归调用 $dfs(i+3)$。
• 如果 $i$, $i+1$ 和 $i+2$ 下标的元素依次递增 $1$，那么可以选择将 $i$, $i+1$ 和 $i+2$ 作为一个子数组，递归调用 $dfs(i+3)$。
• 如果上述情况都不满足，返回 $false$，否则返回 $true$。

即：

$$dfs(i)=\mathit{\text{OR}}\{\begin{array}{ll}true,& i\ge n\\ dfs(i+2),& i+1<n\mathit{\text{and}}\mathit{\text{nums}}[i]=\mathit{\text{nums}}[i+1]\\ dfs(i+3),& i+2<n\mathit{\text{and}}\mathit{\text{nums}}[i]=\mathit{\text{nums}}[i+1]=\mathit{\text{nums}}[i+2]\\ dfs(i+3),& i+2<n\mathit{\text{and}}\mathit{\text{nums}}[i+1]-\mathit{\text{nums}}[i]=1\mathit{\text{and}}\mathit{\text{nums}}[i+2]-\mathit{\text{nums}}[i+1]=1\end{array}$$

为了避免重复计算，我们使用记忆化搜索的方法。

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

func validPartition(nums []int) bool {
	n := len(nums)
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) bool
	dfs = func(i int) bool {
		if i == n {
			return true
		}
		if f[i] != -1 {
			return f[i] == 1
		}
		a := i+1 < n && nums[i] == nums[i+1]
		b := i+2 < n && nums[i] == nums[i+1] && nums[i+1] == nums[i+2]
		c := i+2 < n && nums[i+1]-nums[i] == 1 && nums[i+2]-nums[i+1] == 1
		f[i] = 0
		if a && dfs(i+2) || b && dfs(i+3) || c && dfs(i+3) {
			f[i] = 1
		}
		return f[i] == 1
	}
	return dfs(0)
}

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

思考

方法一从末尾填后缀， $f[i]$ 表示从下标 $i$ 起能否划分。同样三种块也可以按前缀来写： $f[i]$ 表示前 $i$ 个元素能否划分，由 $f[i-2]$ 与 $f[i-3]$ 转入。

自左向右填表，答案为 $f[n]$。时间仍为 $O(n)$。

方法一从末尾判断后缀能否划分。下面改为判断前缀，转移仍是同样的三种块。

设 $f[i]$ 表示数组的前 $i$ 个元素是否存在一种有效划分，初始时 $f[0]=true$，答案就是 $f[n]$。

状态转移方程如下：

$$f[i]=\mathit{\text{OR}}\{\begin{array}{ll}true,& i=0\\ f[i-2],& i-2\ge 0\mathit{\text{and}}\mathit{\text{nums}}[i-1]=\mathit{\text{nums}}[i-2]\\ f[i-3],& i-3\ge 0\mathit{\text{and}}\mathit{\text{nums}}[i-1]=\mathit{\text{nums}}[i-2]=\mathit{\text{nums}}[i-3]\\ f[i-3],& i-3\ge 0\mathit{\text{and}}\mathit{\text{nums}}[i-1]-\mathit{\text{nums}}[i-2]=1\mathit{\text{and}}\mathit{\text{nums}}[i-2]-\mathit{\text{nums}}[i-3]=1\end{array}$$

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

func validPartition(nums []int) bool {
	n := len(nums)
	f := make([]bool, n+1)
	f[0] = true
	for i := 1; i <= n; i++ {
		x := nums[i-1]
		a := i-2 >= 0 && nums[i-2] == x
		b := i-3 >= 0 && nums[i-3] == nums[i-2] && nums[i-2] == x
		c := i-3 >= 0 && x-nums[i-2] == 1 && nums[i-2]-nums[i-3] == 1
		f[i] = (a && f[i-2]) || ((b || c) && f[i-3])
	}
	return f[n]
}

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

思考

划分只能是两相等、三相等或三连续递增。 $n\le {10}^5$，按块枚举会重叠，而且两相等的块总会先尝试。

全相等时这次尝试连成一条长度为 $n/2$ 的调用链，栈会溢出。

更靠后的下标在从末尾往前走时已经就绪。令 $f[i]$ 表示从下标 $i$ 起能否划分， $f[n]$ 为真，从 $i=n-1$ 填到 $0$。合法块仍是跳到 $i+2$ 或 $i+3$。

令 $f[i]$ 表示从下标 $i$ 开始是否存在一种有效划分。答案为 $f[0]$， $f[n]=true$。

从 $i=n-1$ 填到 $0$。两相邻元素相等时，可以接上 $f[i+2]$；三个元素相等，或依次递增 $1$ 时，可以接上 $f[i+3]$。三种情况取或，都不成立则为 $false$：

$$f[i]=\mathit{\text{OR}}\{\begin{array}{ll}f[i+2],& i+1<n\mathit{\text{and}}\mathit{\text{nums}}[i]=\mathit{\text{nums}}[i+1]\\ f[i+3],& i+2<n\mathit{\text{and}}\mathit{\text{nums}}[i]=\mathit{\text{nums}}[i+1]=\mathit{\text{nums}}[i+2]\\ f[i+3],& i+2<n\mathit{\text{and}}\mathit{\text{nums}}[i+1]-\mathit{\text{nums}}[i]=1\mathit{\text{and}}\mathit{\text{nums}}[i+2]-\mathit{\text{nums}}[i+1]=1\end{array}$$

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

func validPartition(nums []int) bool {
	n := len(nums)
	f := make([]bool, n+1)
	f[n] = true
	for i := n - 1; i >= 0; i-- {
		a := i+1 < n && nums[i] == nums[i+1]
		b := i+2 < n && nums[i] == nums[i+1] && nums[i+1] == nums[i+2]
		c := i+2 < n && nums[i+1]-nums[i] == 1 && nums[i+2]-nums[i+1] == 1
		f[i] = (a && f[i+2]) || ((b || c) && f[i+3])
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

2370. 最长理想子序列

中等1 种解法

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

题目、示例与约束

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：

• t 是字符串 s 的一个子序列。
• t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。

返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

注意：字母表顺序不会循环。例如，'a' 和 'z' 在字母表中位次的绝对差值是 25 ，而不是 1 。

 

示例 1：

输入：s = "acfgbd", k = 2
输出：4
解释：最长理想字符串是 "acbd" 。该字符串长度为 4 ，所以返回 4 。
注意 "acfgbd" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。

示例 2：

输入：s = "abcd", k = 3
输出：4
解释：最长理想字符串是 "abcd" ，该字符串长度为 4 ，所以返回 4 。

 

提示：

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

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

思考

子序列相邻字母距离不超过 $k$。 $n\le {10}^5$，枚举子序列不可行。以某位置结尾的最长长度，只依赖此前字母在 $[s[i]-k,s[i]+k]$ 内的最优。

令 $dp[i]$ 为以 $i$ 结尾的答案，哈希表记下每个字母最近一次出现。对字母表中合法前驱取 $dp$ 最大值加一。字母仅 $26$ 个。

设 $dp[i]$ 表示以字符 $s[i]$ 结尾的最长理想子序列的长度，利用哈希表 $d$ 记录每个字符最新出现的位置。初始时 $dp[0]=1$, $d[s[0]]=0$。

在 $[1,..n-1]$ 范围内的每个字符 $s[i]$，获取它所有前一个合法字符的位置 $j$，那么 $dp[i]=max(dp[i],dp[j]+1)$。

答案为 $dp$ 中的最大值。

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

func longestIdealString(s string, k int) int {
	n := len(s)
	ans := 1
	dp := make([]int, n)
	for i := range dp {
		dp[i] = 1
	}
	d := map[byte]int{s[0]: 0}
	for i := 1; i < n; i++ {
		a := s[i]
		for b := byte('a'); b <= byte('z'); b++ {
			if int(a)-int(b) > k || int(b)-int(a) > k {
				continue
			}
			if v, ok := d[b]; ok {
				dp[i] = max(dp[i], dp[v]+1)
			}
		}
		d[a] = i
		ans = max(ans, dp[i])
	}
	return ans
}

力扣原题 · Doocs 题解来源

2376. 统计特殊整数

困难1 种解法

标签：数学、动态规划

题目、示例与约束

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

 

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。

示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

 

提示：

• 1 <= n <= 2 * 109

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

思考

统计 $[1,n]$ 中各位数字互不相同的个数。 $n\le 2\times {10}^9$，枚举每个整数不可行。条件只与数位集合有关，适合数位 DP。

从高位记忆化 $dfs(i,mask,lead,limit)$： $mask$ 记录已用数字，前导零不占位，上限约束保证不超过 $n$。走到末位且已非前导零则计 $1$。

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

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

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

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

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

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

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

函数的执行过程如下：

如果 $i$ 超过了数字 $n$ 的长度，说明搜索结束，如果此时 $\mathit{\text{lead}}$ 为真，说明当前数字只包含前导 $0$，直接返回 $0$，否则返回 $1$。

如果 $\mathit{\text{limit}}$ 为假且 $\mathit{\text{lead}}$ 为假且 $\mathit{\text{mask}}$ 的状态已经被记忆化，直接返回记忆化的结果。

否则，我们计算当前数字的上界 $up$，如果 $\mathit{\text{limit}}$ 为真， $up$ 为当前数字的第 $i$ 位，否则 $up=9$。

然后我们遍历 $[0,up]$，对于每个数字 $j$，如果 $\mathit{\text{mask}}$ 的第 $j$ 位为 $1$，说明数字 $j$ 已经被使用过，直接跳过。否则，如果 $\mathit{\text{lead}}$ 为真且 $j=0$，说明当前数字只包含前导 $0$，递归搜索下一位，否则递归搜索下一位并更新 $\mathit{\text{mask}}$ 的状态。

最后，如果 $\mathit{\text{limit}}$ 为假且 $\mathit{\text{lead}}$ 为假，将当前状态记忆化。

最终返回答案。

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

相似题目：

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

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

力扣原题 · Doocs 题解来源

2380. 二进制字符串重新安排顺序需要的时间

中等2 种解法

标签：字符串、动态规划、模拟

题目、示例与约束

给你一个二进制字符串 s 。

在一秒之中，所有 子字符串 "01" 同时 被替换成 "10" 。这个过程持续进行到没有 "01" 存在。

请你返回完成这个过程所需要的秒数。

 

示例 1：

输入：s = "0110101"
输出：4
解释：
一秒后，s 变成 "1011010" 。
再过 1 秒后，s 变成 "1101100" 。
第三秒过后，s 变成 "1110100" 。
第四秒后，s 变成 "1111000" 。
此时没有 "01" 存在，整个过程花费 4 秒。
所以我们返回 4 。

示例 2：

输入：s = "11100"
输出：0
解释：
s 中没有 "01" 存在，整个过程花费 0 秒。
所以我们返回 0 。

 

提示：

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

 

进阶：

你能以 O(n) 的时间复杂度解决这个问题吗？

方法一：暴力模拟 · Go 实现

思考

每秒把所有 $01$ 同时变成 $10$。 $n\le 1000$，最多 $n$ 轮，直接替换模拟可以通过。

循环执行 $replace(01,10)$ 直至不再出现，轮数即答案。

由于本题数据范围不大，所以可以暴力模拟，每一轮将字符串中所有 “01” 替换为 “10”，统计轮次作为答案。

时间复杂度 $O(n^2)$。每一轮时间复杂度 $O(n)$，最多进行 $n$ 轮操作。

func secondsToRemoveOccurrences(s string) int {
	cs := []byte(s)
	ans := 0
	find := true
	for find {
		find = false
		for i := 0; i < len(cs)-1; i++ {
			if cs[i] == '0' && cs[i+1] == '1' {
				cs[i], cs[i+1] = cs[i+1], cs[i]
				i++
				find = true
			}
		}
		if find {
			ans++
		}
	}
	return ans
}

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

思考

方法一最坏平方。实质上每个 $1$ 在向左穿过其左侧的 $0$。扫一遍统计已遇零的个数：遇到 $1$ 时，它的完成时刻是「比上一个 $1$ 多一秒」与「左侧零的个数」的较大者。

题目要把所有“01”串替换为“10”，实际上是将所有的“1”往左移动。操作过后，左侧均为“1”，而右侧均为“0”。

假如我们要把“0100010”重排为“1100000”，会出现两种情况：

1. 如果一个“1”左边有 $cnt$ 个“0”，那么将这个“1”移动到最左边的位置需要 $cnt$ 秒；
2. 如果有连续的“1”，则将这两个“1”移动到最左边的位置需要额外的 $1$ 秒。

看下面的示例：

时刻（秒）	示例 1	示例 2
0	0001	00011
1	0010	00101
2	0100	01010
3	1000	10100
4	-	11000

我们可以看到，如果在 $cnt$ 个“0”之后只有一个“1”，那么只需要 $cnt$ 秒，如果有连续的“1”，则需要额外的 $1$ 秒。

因此，对于字符串中的每一个“1”，我们计算 $ans=max(ans+1,cnt)$。

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

func secondsToRemoveOccurrences(s string) int {
	ans, cnt := 0, 0
	for _, c := range s {
		if c == '0' {
			cnt++
		} else if cnt > 0 {
			ans = max(ans+1, cnt)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2393. 严格递增的子数组个数 🔒

中等1 种解法

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

题目、示例与约束

给定一个由 正整数 组成的数组 nums 。

返回 严格递增 顺序的 nums 子数组 的数目。

子数组 是数组的一部分，且是 连续 的。

 

示例 1:

输入: nums = [1,3,5,4,4,6]
输出: 10
解释: 严格递增的子数组如下:
- 长度为 1 的子数组: [1], [3], [5], [4], [4], [6]。
- 长度为 2 的子数组: [1,3], [3,5], [4,6]。
- 长度为 3 的子数组: [1,3,5]。
子数组的总数是 6 + 3 + 1 = 10。

示例 2:

输入: nums = [1,2,3,4,5]
输出: 15
解释: 每个子数组都严格递增。我们可以取 15 个子数组。

 

提示:

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

方法一：枚举 · Go 实现

思考

统计严格递增的连续子数组。以右端点分类后，长度由当前递增段决定，不必枚举左端。

维护以当前元素结尾的递增长度 $cnt$：比前一个大则加一，否则重置为 $1$，并累加 $cnt$。

我们可以枚举以每个元素结尾的严格递增子数组的个数，然后将它们累加起来即可。

我们用一个变量 $\mathit{\text{cnt}}$ 来记录以当前元素结尾的严格递增子数组的个数，初始时 $\mathit{\text{cnt}}=1$。然后我们从第二个元素开始遍历数组，如果当前元素大于前一个元素，那么 $\mathit{\text{cnt}}$ 就可以加 $1$，否则 $\mathit{\text{cnt}}$ 重置为 $1$。此时，以当前元素结尾的严格递增子数组的个数就是 $\mathit{\text{cnt}}$，我们将其累加到答案中即可。

遍历结束后，返回答案即可。

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

func countSubarrays(nums []int) int64 {
	ans, cnt := 1, 1
	for i, x := range nums[1:] {
		if nums[i] < x {
			cnt++
		} else {
			cnt = 1
		}
		ans += cnt
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2400. 恰好移动 k 步到达某一位置的方法数目

中等1 种解法

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

题目、示例与约束

给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。

给你一个正整数 k ，返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法数目。由于答案可能会很大，返回对 109 + 7 取余 的结果。

如果所执行移动的顺序不完全相同，则认为两种方法不同。

注意：数轴包含负整数。

 

示例 1：

输入：startPos = 1, endPos = 2, k = 3
输出：3
解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法：
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
可以证明不存在其他方法，所以返回 3 。

示例 2：

输入：startPos = 2, endPos = 5, k = 10
输出：0
解释：不存在从 2 到 5 且恰好移动 10 步的方法。

 

提示：

• 1 <= startPos, endPos, k <= 1000

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

思考

每一步仅能左移或右移一格，若枚举全部长度为 $k$ 的路径，方案数为 $2^k$， $k\le 1000$ 无法接受。按绝对坐标与剩余步数记忆化，坐标落在长度为 $O(k)$ 的区间内，状态量已与 $k^2$ 同阶，但数轴可任意平移，不必保存真实位置。

注意到方案数只由「当前点到终点的距离」与剩余步数决定：朝终点走一步距离变为 $|i-1|$，反向则变为 $i+1$。因此令 $dfs(i,j)$ 表示距离为 $i$、还剩 $j$ 步的方案数并记忆化。若 $i>j$，剩余步数不足以走完这段距离，可直接返回 $0$。

我们设计一个函数 $dfs(i,j)$，表示当前位置距离目标位置的距离为 $i$，还剩 $j$ 步，有多少种方法到达目标位置。那么答案就是 $dfs(abs(startPos-endPos),k)$。

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

• 如果 $i>j$ 或者 $j<0$，说明当前位置距离目标位置的距离大于剩余步数，或者剩余步数为负数，此时无法到达目标位置，返回 $0$；
• 如果 $j=0$，说明剩余步数为 $0$，此时只有当前位置距离目标位置的距离为 $0$ 时才能到达目标位置，否则无法到达目标位置，返回 $1$ 或者 $0$；
• 否则，当前位置距离目标位置的距离为 $i$，还剩 $j$ 步，那么有两种方法到达目标位置：
  • 向左移动一步，此时当前位置距离目标位置的距离为 $i+1$，还剩 $j-1$ 步，方法数为 $dfs(i+1,j-1)$；
  • 向右移动一步，此时当前位置距离目标位置的距离为 $abs(i-1)$，还剩 $j-1$ 步，方法数为 $dfs(abs(i-1),j-1)$；
• 最后，返回两种方法的和对 ${10}^9+7$ 取余的结果。

为了避免重复计算，我们使用记忆化搜索，即使用一个二维数组 $f$ 记录函数 $dfs(i,j)$ 的结果，当函数 $dfs(i,j)$ 被调用时，如果 $f[i][j]$ 不为 $-1$，则直接返回 $f[i][j]$，否则计算 $f[i][j]$ 的值，并返回 $f[i][j]$。

时间复杂度 $O(k^2)$，空间复杂度 $O(k^2)$。其中 $k$ 为题目给定的步数。

func numberOfWays(startPos int, endPos int, k int) int {
	const mod = 1e9 + 7
	f := make([][]int, k+1)
	for i := range f {
		f[i] = make([]int, k+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i > j || j < 0 {
			return 0
		}
		if j == 0 {
			if i == 0 {
				return 1
			}
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		f[i][j] = (dfs(i+1, j-1) + dfs(abs(i-1), j-1)) % mod
		return f[i][j]
	}
	return dfs(abs(startPos-endPos), k)
}

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

力扣原题 · Doocs 题解来源

2403. 杀死所有怪物的最短时间 🔒

困难2 种解法

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

题目、示例与约束

你有一个整数数组 power，其中  power[i] 是第 i 个怪物的力量。

你从 0 点法力值开始，每天获取 gain 点法力值，最初 gain 等于 1。

每天，在获得 gain 点法力值后，如果你的法力值大于或等于怪物的力量，你就可以打败怪物。当你打败怪物时:

• 你的法力值会被重置为 0，并且

• gain 的值增加 1。

返回打败所有怪物所需的 最少 天数。

 

示例 1:

输入: power = [3,1,4]
输出: 4
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。
- 第 3 天: 获得 2 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。
- 第 4 天: 获得 3 点法力值，现在总共拥有 3 点法力值。 用尽所有法力值击杀第 1 个怪物。
可以证明，4 天是最少需要的天数。

示例 2:

输入: power = [1,1,4]
输出: 4
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物。
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。
- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。用尽所有法力值击杀第 3 个怪物。
可以证明，4 天是最少需要的天数。

示例 3:

输入: power = [1,2,4,9]
输出: 6
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。
- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。
- 第 5 天: 获得 3 点法力值，现在总共拥有 9 点法力值。用尽所有法力值击杀第 4 个怪物。
- 第 6 天: 获得 4 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。
可以证明，6 天是最少需要的天数。

 

提示:

• 1 <= power.length <= 17
• 1 <= power[i] <= 109

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

思考

击败顺序有 $n!$ 种， $n\le 17$ 无法直接枚举。每天伤害等于「已击败数 $+1$」，同一存活集合上的最优天数可由该集合完全描述。

用二进制 $\mathit{\text{mask}}$ 表示仍存活的怪物，令 $dfs(\mathit{\text{mask}})$ 为清空该集合的最少天数。当前法力由已击败数量决定，对 $\mathit{\text{mask}}$ 中每位枚举下一个击败目标并记忆化，状态数 $2^n$，每次转移 $O(n)$。

我们注意带，怪物的数量最多为 $17$，这意味着我们可以使用一个 $17$ 位的二进制数来表示怪物的状态，其中第 $i$ 位为 $1$ 表示第 $i$ 个怪物还活着，为 $0$ 表示第 $i$ 个怪物已经被击败。

我们设计一个函数 $\mathit{\text{dfs}}(\mathit{\text{mask}})$，表示当前怪物的状态为 $\mathit{\text{mask}}$ 时，打败所有怪物所需的最少天数。那么答案就是 $\mathit{\text{dfs}}(2^n-1)$，其中 $n$ 为怪物的数量。

函数 $\mathit{\text{dfs}}(\mathit{\text{mask}})$ 的计算方式如下：

• 如果 $\mathit{\text{mask}}=0$，表示所有怪物都已经被击败，返回 $0$；
• 否则，我们枚举每个怪物 $i$，如果第 $i$ 个怪物还活着，那么我们可以选择击败第 $i$ 个怪物，然后递归计算 $\mathit{\text{dfs}}(\mathit{\text{mask}}\oplus 2^i)$，并更新答案为 $\mathit{\text{ans}}=min(\mathit{\text{ans}},\mathit{\text{dfs}}(\mathit{\text{mask}}\oplus 2^i)+\lceil \frac{x}{\mathit{\text{gain}}}\rceil )$，其中 $x$ 为第 $i$ 个怪物的力量，而 $\mathit{\text{gain}}=1+(n-\mathit{\text{mask}}.\mathit{\text{bitCount}}())$，表示当前每天可以获得的法力值。

最后，我们返回 $\mathit{\text{dfs}}(2^n-1)$。

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

func minimumTime(power []int) int64 {
	n := len(power)
	f := make([]int64, 1<<n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(mask int) int64
	dfs = func(mask int) int64 {
		if mask == 0 {
			return 0
		}
		if f[mask] != -1 {
			return f[mask]
		}
		f[mask] = 1e18
		gain := 1 + (n - bits.OnesCount(uint(mask)))
		for i, x := range power {
			if mask>>i&1 == 1 {
				f[mask] = min(f[mask], dfs(mask^(1<<i))+int64(x+gain-1)/int64(gain))
			}
		}
		return f[mask]
	}
	return dfs(1<<n - 1)
}

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

思考

方法一的转移已经是 $O(2^{n}n)$，但仍依赖递归与缓存。同一转移可按 $\mathit{\text{mask}}$ 从小到大填表：令 $f[\mathit{\text{mask}}]$ 表示已击败集合为 $\mathit{\text{mask}}$ 的最少天数，由去掉其中一只怪物的前驱转移而来。渐近复杂度不变，实现改为自底向上；此处位为 $1$ 表示已击败，与方法一相反。

我们可以将方法一中的记忆化搜索改为动态规划，定义 $f[\mathit{\text{mask}}]$ 表示当前怪物的状态为 $\mathit{\text{mask}}$ 时，打败所有怪物所需的最少天数。其中 $\mathit{\text{mask}}$ 是一个 $n$ 位的二进制数，其中第 $i$ 位为 $1$ 表示第 $i$ 个怪物已被击败，为 $0$ 表示第 $i$ 个怪物还活着。初始时 $f[0]=0$，其余 $f[\mathit{\text{mask}}]=+\mathrm{\infty }$。答案即为 $f[2^n-1]$。

我们在 $[1,2^n-1]$ 的范围内枚举 $\mathit{\text{mask}}$，对于每个 $\mathit{\text{mask}}$，我们枚举每个怪物 $i$，如果第 $i$ 个怪物被击败，那么它可以从上一个状态 $\mathit{\text{mask}}\oplus 2^i$ 转移过来，转移的代价为 $(\mathit{\text{power}}[i]+\mathit{\text{gain}}-1)/\mathit{\text{gain}}$，其中 $\mathit{\text{gain}}=\mathit{\text{mask}}.\mathit{\text{bitCount}}()$。

最后，返回 $f[2^n-1]$。

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

func minimumTime(power []int) int64 {
	n := len(power)
	f := make([]int64, 1<<n)
	for i := range f {
		f[i] = 1e18
	}
	f[0] = 0
	for mask := 1; mask < 1<<n; mask++ {
		gain := bits.OnesCount(uint(mask))
		for i, x := range power {
			if mask>>i&1 == 1 {
				f[mask] = min(f[mask], f[mask^(1<<i)]+int64(x+gain-1)/int64(gain))
			}
		}
	}
	return f[1<<n-1]
}

力扣原题 · Doocs 题解来源

2420. 找到所有好下标

中等1 种解法

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

题目、示例与约束

给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。

对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：

• 下标 i 之前 的 k 个元素是 非递增的 。
• 下标 i 之后 的 k 个元素是 非递减的 。

按 升序 返回所有好下标。

 

示例 1：

输入：nums = [2,1,1,1,3,4,1], k = 2
输出：[2,3]
解释：数组中有两个好下标：
- 下标 2 。子数组 [2,1] 是非递增的，子数组 [1,3] 是非递减的。
- 下标 3 。子数组 [1,1] 是非递增的，子数组 [3,4] 是非递减的。
注意，下标 4 不是好下标，因为 [4,1] 不是非递减的。

示例 2：

输入：nums = [2,1,1,2], k = 2
输出：[]
解释：数组中没有好下标。

 

提示：

• n == nums.length
• 3 <= n <= 105
• 1 <= nums[i] <= 106
• 1 <= k <= n / 2

方法一：递推 · Go 实现

思考

$n\le {10}^5$，对每个下标 $i$ 单独检查左右各 $k$ 个元素是否非增/非减，最坏接近 $O(nk)$。左右条件互不依赖，可预先算出「以 $i-1$ 结尾的非增长度」与「以 $i+1$ 开头的非增长度」。

从左递推 $\mathit{\text{decr}}[i]$，从右递推 $\mathit{\text{incr}}[i]$，再在 $[k,n-k)$ 上判断两端是否都不短于 $k$。注意题设左右都是非递增（右侧为 $\mathit{\text{nums}}[i+1]\ge \cdots$ 的反向叙述），与代码中两次比较 $ \le $ 一致。

我们定义两个数组 decr 和 incr，分别表示从左到右和从右到左的非递增和非递减的最长子数组长度。

遍历数组，更新 decr 和 incr 数组。

然后顺序遍历下标 $i$（其中 $k\le i<n-k$），若 $decr[i]\ge k$ 并且 $incr[i]\ge k$，则 $i$ 为好下标。

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

func goodIndices(nums []int, k int) []int {
	n := len(nums)
	decr := make([]int, n)
	incr := make([]int, n)
	for i := range decr {
		decr[i] = 1
		incr[i] = 1
	}
	for i := 2; i < n; i++ {
		if nums[i-1] <= nums[i-2] {
			decr[i] = decr[i-1] + 1
		}
	}
	for i := n - 3; i >= 0; i-- {
		if nums[i+1] <= nums[i+2] {
			incr[i] = incr[i+1] + 1
		}
	}
	ans := []int{}
	for i := k; i < n-k; i++ {
		if decr[i] >= k && incr[i] >= k {
			ans = append(ans, i)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2430. 对字母串可执行的最大删除数

困难2 种解法

标签：字符串、动态规划、字符串匹配、哈希函数、滚动哈希

题目、示例与约束

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：

• 删除 整个字符串 s ，或者
• 对于满足 1 <= i <= s.length / 2 的任意 i ，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。

例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s 的前两个字母和接下来的两个字母都等于 "ab" 。

返回删除 s 所需的最大操作数。

 

示例 1：

输入：s = "abcabcdabc"
输出：2
解释：
- 删除前 3 个字母（"abc"），因为它们和接下来 3 个字母相等。现在，s = "abcdabc"。
- 删除全部字母。
一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。
注意，在第二步操作中无法再次删除 "abc" ，因为 "abc" 的下一次出现并不是位于接下来的 3 个字母。

示例 2：

输入：s = "aaabaab"
输出：4
解释：
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "aabaab"。
- 删除前 3 个字母（"aab"），因为它们和接下来 3 个字母相等。现在，s = "aab"。 
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "ab"。
- 删除全部字母。
一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。

示例 3：

输入：s = "aaaaa"
输出：5
解释：在每一步操作中，都可以仅删除 s 的第一个字母。

 

提示：

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

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

思考

$n\le 4000$，每次操作删去一段与其后紧邻相等的前缀。若搜索所有删法，状态可由剩余后缀的起点 $i$ 描述。从 $i$ 出发枚举长度 $j$，切片比较 $s[i:i+j]$ 与 $s[i+j:i+2j]$，相等则可转移到 $i+j$ 并多一次操作；也可一次删完全部，答案至少为 $1$。

对 $dfs(i)$ 记忆化，比较代价与长度同阶，总时间 $O(n^2)$，对本题足够。

我们设计一个函数 $dfs(i)$，表示删除 $s[i..]$ 所有字符所需的最大操作数，那么答案就是 $dfs(0)$。

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

• 如果 $i\ge n$，那么 $dfs(i)=0$，直接返回。
• 否则，我们枚举字符串的长度 $j$，其中 $1\le j\le (n-1)/2$，如果 $s[i..i+j]=s[i+j..i+j+j]$，那么我们可以删除 $s[i..i+j]$，此时 $dfs(i)=max(dfs(i),dfs(i+j)+1)$。我们需要枚举所有的 $j$，求 $dfs(i)$ 的最大值即可。

这里我们需要快速判断 $s[i..i+j]$ 与 $s[i+j..i+j+j]$ 是否相等，我们可以预处理出字符串 $s$ 的所有最长公共前缀，即 $g[i][j]$ 表示 $s[i..]$ 与 $s[j..]$ 的最长公共前缀的长度。这样我们就可以快速判断 $s[i..i+j]$ 与 $s[i+j..i+j+j]$ 是否相等，即 $g[i][i+j]\ge j$。

为了避免重复计算，我们可以使用记忆化搜索，用一个数组 $f$ 记录函数 $dfs(i)$ 的值。

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

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

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

思考

方法一每次用切片判等，常数较大，且递归有缓存开销。先预处理 $g[i][j]$ 为 $s[i:]$ 与 $s[j:]$ 的 LCP，则 $g[i][i+j]\ge j$ 即可 $O(1)$ 判断。自后向前填 $f[i]$，空间降为 $O(n)$ 的一维表外加 LCP 表。

我们可以将方法一的记忆化搜索改为动态规划，定义 $f[i]$ 表示删除 $s[i..]$ 所有字符所需的最大操作数，初始时 $f[i]=1$，答案为 $f[0]$。

我们可以从后往前枚举 $i$，对于每个 $i$，我们枚举字符串的长度 $j$，其中 $1\le j\le (n-1)/2$，如果 $s[i..i+j]=s[i+j..i+j+j]$，那么我们可以删除 $s[i..i+j]$，此时 $f[i]=max(f[i],f[i+j]+1)$。我们需要枚举所有的 $j$，求 $f[i]$ 的最大值即可。

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

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

力扣原题 · Doocs 题解来源

2431. 最大限度地提高购买水果的口味 🔒

中等1 种解法

标签：数组、动态规划

题目、示例与约束

你有两个非负整数数组 price 和 tastiness，两个数组的长度都是 n。同时给你两个非负整数 maxAmount 和 maxCoupons。

对于范围 [0, n - 1] 中的每一个整数 i:

• price[i] 描述了第 i 个水果的价格。

• tastiness[i] 描述了第 i 个水果的味道。

你想购买一些水果，这样总的味道是最大的，总价不超过 maxAmount。

此外，你还可以用优惠券以 半价 购买水果 (向下取整到最接近的整数)。您最多可以使用 maxCoupons 次该优惠券。

返回可购买的最大总口味。

注意:

• 每个水果最多只能购买一次。
• 一个水果你最多只能用一次折价券。

 

示例 1:

输入: price = [10,20,20], tastiness = [5,8,8], maxAmount = 20, maxCoupons = 1
输出: 13
解释: 可以用以下方法来达到总口味:
- 无优惠券买第一个水果，总价= 0 + 10，总口味= 0 + 5。
- 用优惠券买第二个水果，总价= 10 + 10，总口味= 5 + 8。
- 不购买第三个水果，总价= 20，总口味= 13。
可以证明 13 是所能得到的最大总口味。

示例 2:

输入: price = [10,15,7], tastiness = [5,8,20], maxAmount = 10, maxCoupons = 2
输出: 28
解释: 可以用以下方法使总口味达到 20:
- 不买第一个水果，这样总价= 0，总口味= 0。
- 用优惠券买第二个水果，总价= 0 + 7，总口味= 0 + 8。
- 用优惠券买第三个水果，总价= 7 + 3，总口味= 8 + 20。
可以证明，28 是所能得到的最大总口味。

 

提示:

• n == price.length == tastiness.length
• 1 <= n <= 100
• 0 <= price[i], tastiness[i], maxAmount <= 1000
• 0 <= maxCoupons <= 5

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

思考

每个水果有买、不买、半价买三种选择，优惠券与金额有限。状态 $(i,j,k)$ 表示考虑到第 $i$ 个水果、剩余金额 $j$、剩余券 $k$，规模与 $n\times \mathit{\text{maxAmount}}\times \mathit{\text{maxCoupons}}$ 成正比，记忆化即可。

转移为跳过、全价购买（金额足够）、或用一张券半价购买。取三者最大美味度。

我们设计函数 $dfs(i,j,k)$ 表示从第 $i$ 个水果开始，剩余 $j$ 元钱，剩余 $k$ 张优惠券时，最大的总美味度。

对于第 $i$ 个水果，可以选择购买或者不购买，如果购买，那么可以选择使用优惠券或者不使用优惠券。

如果不购买，那么最大总美味度是 $dfs(i+1,j,k)$；

如果购买，如果不使用优惠券（需要满足 $j\ge price[i]$），那么最大总美味度是 $dfs(i+1,j-price[i],k)+tastiness[i]$；如果使用优惠券（需要满足 $k>0$ 并且 $j\ge \lfloor \frac{price[i]}{2}\rfloor$），那么最大总美味度是 $dfs(i+1,j-\lfloor \frac{price[i]}{2}\rfloor ,k-1)+tastiness[i]$。

最终的答案是 $dfs(0,maxAmount,maxCoupons)$。

时间复杂度 $O(n\times maxAmount\times maxCoupons)$。其中 $n$ 是水果的数量。

func maxTastiness(price []int, tastiness []int, maxAmount int, maxCoupons int) int {
	n := len(price)
	f := make([][][]int, n+1)
	for i := range f {
		f[i] = make([][]int, maxAmount+1)
		for j := range f[i] {
			f[i][j] = make([]int, maxCoupons+1)
		}
	}
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if i == n {
			return 0
		}
		if f[i][j][k] != 0 {
			return f[i][j][k]
		}
		ans := dfs(i+1, j, k)
		if j >= price[i] {
			ans = max(ans, dfs(i+1, j-price[i], k)+tastiness[i])
		}
		if j >= price[i]/2 && k > 0 {
			ans = max(ans, dfs(i+1, j-price[i]/2, k-1)+tastiness[i])
		}
		f[i][j][k] = ans
		return ans
	}
	return dfs(0, maxAmount, maxCoupons)
}

力扣原题 · Doocs 题解来源

2435. 矩阵中和能被 K 整除的路径

困难1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余 的结果。

 

示例 1：

输入：grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出：2
解释：有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。
第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。

示例 2：

输入：grid = [[0,0]], k = 5
输出：1
解释：红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。

示例 3：

输入：grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出：10
解释：每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 5 * 104
• 1 <= m * n <= 5 * 104
• 0 <= grid[i][j] <= 100
• 1 <= k <= 50

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

思考

只能向右或向下，路径数与格子乘积同阶， $mn\le 5\times {10}^4$、 $k\le 50$。需要的是路径和模 $k$ 为 $0$ 的条数，故把余数纳入状态。

令 $f[i][j][r]$ 为走到 $(i,j)$ 且和模 $K$ 为 $r$ 的方案，由上方或左方余数 $r-grid[i][j]$ 转移。起点单独置 $1$。

我们记题目中的 $k$ 为 $K$，矩阵 $\mathit{\text{grid}}$ 的行数和列数分别为 $m$ 和 $n$。

定义 $f[i][j][k]$ 表示从起点 $(0,0)$ 出发，到达位置 $(i,j)$，且路径上元素和对 $K$ 取模等于 $k$ 的路径数目。初始时， $f[0][0][\mathit{\text{grid}}[0][0]modK]=1$。 最终答案即为 $f[m-1][n-1][0]$。

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

$$f[i][j][k]=f[i-1][j][(k-\mathit{\text{grid}}[i][j])modK]+f[i][j-1][(k-\mathit{\text{grid}}[i][j])modK]$$

为了避免负数取模的问题，我们可以将上式中的 $(k-\mathit{\text{grid}}[i][j])modK$ 替换为 $((k-\mathit{\text{grid}}[i][j]modK)+K)modK$。

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

时间复杂度 $O(m\times n\times K)$，空间复杂度 $O(m\times n\times K)$。其中 $m$ 和 $n$ 分别是矩阵 $\mathit{\text{grid}}$ 的行数和列数，而 $K$ 是题目中的整数 $k$。

func numberOfPaths(grid [][]int, K int) int {
	const mod = 1e9 + 7
	m, n := len(grid), len(grid[0])
	f := make([][][]int, m)
	for i := range f {
		f[i] = make([][]int, n)
		for j := range f[i] {
			f[i][j] = make([]int, K)
		}
	}
	f[0][0][grid[0][0]%K] = 1
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < K; k++ {
				k0 := ((k - grid[i][j]%K) + K) % K
				if i > 0 {
					f[i][j][k] = (f[i][j][k] + f[i-1][j][k0]) % mod
				}
				if j > 0 {
					f[i][j][k] = (f[i][j][k] + f[i][j-1][k0]) % mod
				}
			}
		}
	}
	return f[m-1][n-1][0]
}

力扣原题 · Doocs 题解来源

2436. 使子数组最大公约数大于一的最小分割数 🔒

中等1 种解法

标签：贪心、数组、数学、动态规划、数论、欧几里得算法

题目、示例与约束

给定一个由正整数组成的数组 nums。

将数组拆分为 一个或多个 互相不覆盖的子数组，如下所示:

• 数组中的每个元素都 只属于一个 子数组，并且
• 每个子数组元素的 最大公约数 严格大于 1。

返回拆分后可获得的子数组的最小数目。

注意:

• 子数组的 最大公约数 是能将子数组中所有元素整除的最大正整数。

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

 

示例 1:

输入: nums = [12,6,3,14,8]
输出: 2
解释: 我们可以把数组分成子数组:[12,6,3] 和 [14,8]。
- 12、6、3 的最大公约数是 3，严格大于 1。
- 14 和 8 的最大公约数是 2，严格来说大于 1。
可以看出，如果不拆分数组将使最大公约数 = 1。

示例 2:

输入: nums = [4,12,6,14]
输出: 1
解释: 我们可以将数组拆分为一个子数组，即整个数组。

 

提示:

• 1 <= nums.length <= 2000
• 2 <= nums[i] <= 109

方法一：贪心 + 数学 · Go 实现

思考

子数组 GCD 必须大于 $1$，分割份数尽量少，即每段尽量长。从左延伸当前段的 GCD，一旦与下一元素互质就不得不切开。

维护当前段 GCD $g$，遇 $gcd(g,x)=1$ 则份数加一并把 $g$ 重置为 $x$。贪心切开是必要的：继续并入只会使 GCD 更小。

对于数组中的每个元素，如果它与前面的元素的最大公约数为 $1$，那么它需要作为一个新的子数组的第一个元素。否则，它可以与前面的元素放在同一个子数组中。

因此，我们先初始化一个变量 $g$，表示当前子数组的最大公约数。初始时 $g=0$，答案变量 $ans=1$。

接下来，我们从前往后遍历数组，维护当前子数组的最大公约数 $g$。如果当前元素 $x$ 与 $g$ 的最大公约数为 $1$，那么我们需要将当前元素作为一个新的子数组的第一个元素，因此，答案加 $1$，并将 $g$ 更新为 $x$。否则，当前元素可以与前面的元素放在同一个子数组中。继续遍历数组，直到遍历结束。

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

func minimumSplits(nums []int) int {
	ans, g := 1, 0
	for _, x := range nums {
		g = gcd(g, x)
		if g == 1 {
			ans++
			g = x
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

2439. 最小化数组中的最大值

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。

每一步操作中，你需要：

• 选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
• 将 nums[i] 减 1 。
• 将 nums[i - 1] 加 1 。

你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。

 

示例 1：

输入：nums = [3,7,1,6]
输出：5
解释：
一串最优操作是：
1. 选择 i = 1 ，nums 变为 [4,6,1,6] 。
2. 选择 i = 3 ，nums 变为 [4,6,2,5] 。
3. 选择 i = 1 ，nums 变为 [5,5,2,5] 。
nums 中最大值为 5 。无法得到比 5 更小的最大值。
所以我们返回 5 。

示例 2：

输入：nums = [10,1]
输出：10
解释：
最优解是不改动 nums ，10 是最大值，所以返回 10 。

 

提示：

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

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

思考

操作只能把 $i$ 的值分给 $i-1$，等价于把超量向左传递。要最小化最终最大值， $n\le {10}^5$，对上限二分。

从右往左看：若某位超过 $mx$，差额必须继续左传。最后检查传入下标 $0$ 的量加上 $nums[0]$ 是否仍 $\le mx$。

最小化数组的最大值，容易想到二分查找。我们二分枚举数组的最大值 $mx$，找到一个满足题目要求的、且值最小的 $mx$ 即可。

时间复杂度 $O(n\times \log M)$，其中 $n$ 为数组的长度，而 $M$ 为数组中的最大值。

func minimizeArrayValue(nums []int) int {
	check := func(mx int) bool {
		d := 0
		for i := len(nums) - 1; i > 0; i-- {
			d = max(0, nums[i]+d-mx)
		}
		return nums[0]+d <= mx
	}

	left, right := 0, slices.Max(nums)
	for left < right {
		mid := (left + right) >> 1
		if check(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

2463. 最小移动总距离

困难1 种解法

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

题目、示例与约束

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。

每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。

所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。

任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。

请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意：

• 所有机器人移动速度相同。
• 如果两个机器人移动方向相同，它们永远不会碰撞。
• 如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
• 如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
• 机器人从位置 x 到位置 y 的移动距离为 |y - x| 。

 

示例 1：

输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：如上图所示：
- 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。
- 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。
- 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。

示例 2：

输入：robot = [1,-1], factory = [[-2,1],[2,1]]
输出：2
解释：如上图所示：
- 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。
- 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。

 

提示：

• 1 <= robot.length, factory.length <= 100
• factory[j].length == 2
• -109 <= robot[i], positionj <= 109
• 0 <= limitj <= robot.length
• 测试数据保证所有机器人都可以被维修。

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

思考

机器人与工厂各至多 $100$，需把机器人分配到工厂且不超容量。排序后相邻机器人应分给相邻工厂，否则交叉只会更差。

令 $dfs(i,j)$ 为从第 $i$ 个机器人、第 $j$ 个工厂起的最小路程：跳过该厂，或让该厂修连续 $0..limit$ 个机器人。记忆化后状态 $O(mn)$，转移乘上容量。

我们先对机器人和工厂进行升序排列。然后定义函数 $dfs(i,j)$ 表示从第 $i$ 个机器人开始，第 $j$ 个工厂开始维修的最小总移动距离。

对于 $dfs(i,j)$，如果第 $j$ 个工厂不维修机器人，那么 $dfs(i,j)=dfs(i,j+1)$。如果第 $j$ 个工厂维修机器人，我们可以枚举第 $j$ 个工厂维修的机器人的数量，找出最小的总移动距离。即 $dfs(i,j)=min(dfs(i+k+1,j+1)+\sum _{t=0}^k|robot[i+t]-factory[j][0|)$。

时间复杂度 $O(m^2\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为机器人数量和工厂数量。

func minimumTotalDistance(robot []int, factory [][]int) int64 {
	sort.Ints(robot)
	sort.Slice(factory, func(i, j int) bool { return factory[i][0] < factory[j][0] })
	f := make([][]int, len(robot))
	for i := range f {
		f[i] = make([]int, len(factory))
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i == len(robot) {
			return 0
		}
		if j == len(factory) {
			return 1e15
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans := dfs(i, j+1)
		t := 0
		for k := 0; k < factory[j][1]; k++ {
			if i+k >= len(robot) {
				break
			}
			t += abs(robot[i+k] - factory[j][0])
			ans = min(ans, t+dfs(i+k+1, j+1))
		}
		f[i][j] = ans
		return ans
	}
	return int64(dfs(0, 0))
}

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

力扣原题 · Doocs 题解来源

2464. 有效分割中的最少子数组数目 🔒

中等2 种解法

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

题目、示例与约束

给定一个整数数组 nums。

如果要将整数数组 nums 拆分为 子数组 后是 有效的，则必须满足:

• 每个子数组的第一个和最后一个元素的最大公约数 大于 1，且
• nums 的每个元素只属于一个子数组。

返回 nums 的 有效 子数组拆分中的 最少 子数组数目。如果不能进行有效的子数组拆分，则返回 -1。

注意:

• 两个数的 最大公约数 是能整除两个数的最大正整数。
• 子数组 是数组中连续的非空部分。

 

示例 1:

输入: nums = [2,6,3,4,3]
输出: 2
解释: 我们可以通过以下方式创建一个有效的分割: [2,6] | [3,4,3].
- 第一个子数组的起始元素是 2，结束元素是 6。它们的最大公约数是 2，大于 1。
- 第二个子数组的起始元素是 3，结束元素是 3。它们的最大公约数是 3，大于 1。
可以证明，2 是我们在有效分割中可以获得的最少子数组数。

示例 2:

输入: nums = [3,5]
输出: 2
解释: 我们可以通过以下方式创建一个有效的分割: [3] | [5].
- 第一个子数组的起始元素是 3，结束元素是 3。它们的最大公约数是 3，大于 1。
- 第二个子数组的起始元素是 5，结束元素是 5。它们的最大公约数是 5，大于 1。
可以证明，2 是我们在有效分割中可以获得的最少子数组数。

示例 3:

输入: nums = [1,2,1]
输出: -1
解释: 不可能创建有效的分割。

 

提示:

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

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

思考

一段合法当且仅当两端 $gcd>1$，分割份数最少。从 $i$ 枚举右端 $j$，能切开则 $1+dfs(j+1)$。 $n$ 通常不大，记忆化 $O(n^2)$ 次 $gcd$。无法分割则返回 $-1$。

我们设计一个函数 $dfs(i)$ 表示从下标 $i$ 开始的最小分割数。对于下标 $i$，我们可以枚举所有的分割点 $j$，即 $i\le j<n$，其中 $n$ 为数组长度。对于每个分割点 $j$，我们需要判断 $nums[i]$ 和 $nums[j]$ 的最大公约数是否大于 $1$，如果大于 $1$，则可以进行分割，此时分割数为 $1+dfs(j+1)$，否则分割数为 $+\mathrm{\infty }$。最后我们取所有分割数的最小值即可。

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

func validSubarraySplit(nums []int) int {
	n := len(nums)
	f := make([]int, n)
	var dfs func(int) int
	const inf int = 0x3f3f3f3f
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if f[i] > 0 {
			return f[i]
		}
		ans := inf
		for j := i; j < n; j++ {
			if gcd(nums[i], nums[j]) > 1 {
				ans = min(ans, 1+dfs(j+1))
			}
		}
		f[i] = ans
		return ans
	}
	ans := dfs(0)
	if ans < inf {
		return ans
	}
	return -1
}

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

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

思考

枚举全部切法是指数级的。数组长度可以到 $1000$，而从左端点试右端点时，下一段的下标总是严格变大，递归深度就是 $n$。一段是否合法只看两端的最大公约数是否大于 $1$，下标 $i$ 起的最少段数只依赖更靠右的答案。于是令 $f[i]$ 为从 $i$ 开始的最少段数， $f[n]=0$，再从右往左枚举右端点 $j$，在 $gcd(nums[i],nums[j])>1$ 时用 $1+f[j+1]$ 更新。

设 $f[i]$ 为从下标 $i$ 开始的最少分割段数，边界 $f[n]=0$。从 $i=n-1$ 递减到 $0$，枚举右端点 $j$（ $i\le j<n$）。若 $gcd(nums[i],nums[j])>1$，则区间 $[i,j]$ 是一段合法子数组，用 $1+f[j+1]$ 更新 $f[i]$。最后若 $f[0]$ 仍为无穷大，说明无法完成分割，返回 $-1$，否则返回 $f[0]$。

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

func validSubarraySplit(nums []int) int {
	n := len(nums)
	const inf int = 0x3f3f3f3f
	f := make([]int, n+1)
	for i := 0; i < n; i++ {
		f[i] = inf
	}
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if gcd(nums[i], nums[j]) > 1 {
				f[i] = min(f[i], 1+f[j+1])
			}
		}
	}
	if f[0] < inf {
		return f[0]
	}
	return -1
}

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

力扣原题 · Doocs 题解来源

2466. 统计构造好字符串的方案数

中等2 种解法

标签：动态规划

题目、示例与约束

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

• 将 '0' 在字符串末尾添加 zero  次。
• 将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：low = 3, high = 3, zero = 1, one = 1
输出：8
解释：
一个可能的好字符串是 "011" 。
可以这样构造得到："" -> "0" -> "01" -> "011" 。
从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。

示例 2：

输入：low = 2, high = 3, zero = 1, one = 2
输出：5
解释：好字符串为 "00" ，"11" ，"000" ，"110" 和 "011" 。

 

提示：

• 1 <= low <= high <= 105
• 1 <= zero, one <= low

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

思考

每次追加 $zero$ 个 $0$ 或 $one$ 个 $1$，长度落在 $[low,high]$ 即好串。 $high\le {10}^5$，令 $dfs(i)$ 为已拼出长度 $i$ 时的方案：若 $i$ 已在区间内先计 $1$，再分支 $i+zero$ 与 $i+one$。越界为 $0$。

我们设计一个函数 $dfs(i)$ 表示从第 $i$ 位开始构造的好字符串的个数，答案即为 $dfs(0)$。

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

• 如果 $i>high$，返回 $0$；
• 如果 $ low \leq i \leq high$，答案累加 $1$，然后 $i$ 之后既可以添加 zero 个 $0$，也可以添加 one 个 $1$，因此答案累加上 $dfs(i+zero)+dfs(i+one)$。

过程中，我们需要对答案取模，并且可以使用记忆化搜索减少重复计算。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n=high$。

func countGoodStrings(low int, high int, zero int, one int) int {
	f := make([]int, high+1)
	for i := range f {
		f[i] = -1
	}
	const mod int = 1e9 + 7
	var dfs func(i int) int
	dfs = func(i int) int {
		if i > high {
			return 0
		}
		if f[i] != -1 {
			return f[i]
		}
		ans := 0
		if i >= low && i <= high {
			ans++
		}
		ans += dfs(i+zero) + dfs(i+one)
		ans %= mod
		f[i] = ans
		return ans
	}
	return dfs(0)
}

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

思考

每次追加 $zero$ 个 $0$ 或 $one$ 个 $1$，长度落在 $[low,high]$ 才是好串。 $high\le {10}^5$，按追加顺序展开会重复大量长度。

较短的那一档总是先递归。 $zero$ 与 $one$ 都不小于 $1$，这次调用一定走向更大的长度，最坏调用链长度为 $high$，栈会溢出。

更长的长度在从 $high$ 往 $0$ 填时已经就绪。令 $f[i]$ 为当前长度已是 $i$ 时的好串数：区间内先计 $1$，再加上 $f[i+zero]$ 与 $f[i+one]$，越过 $high$ 的项视为 $0$。

令 $f[i]$ 表示当前长度已经是 $i$ 时，能够构造出的好字符串个数。答案为 $f[0]$。长度超过 $high$ 的贡献为 $0$。

从 $i=high$ 填到 $0$。若 $low\le i\le high$，当前字符串本身就是好串，先计入 $1$。之后仍可追加 $zero$ 个 $0$ 或 $one$ 个 $1$，把 $f[i+zero]$ 与 $f[i+one]$ 加进来；下标超过 $high$ 时该项为 $0$。每一步都对 ${10}^9+7$ 取模。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n=high$。

func countGoodStrings(low int, high int, zero int, one int) int {
	const mod int = 1e9 + 7
	f := make([]int, high+1)
	for i := high; i >= 0; i-- {
		ans := 0
		if i >= low && i <= high {
			ans++
		}
		if i+zero <= high {
			ans += f[i+zero]
		}
		if i+one <= high {
			ans += f[i+one]
		}
		f[i] = ans % mod
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

2472. 不重叠回文子字符串的最大数目

困难1 种解法

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

题目、示例与约束

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

• 每个子字符串的长度 至少 为 k 。
• 每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

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

 

示例 1 ：

输入：s = "abaccdbbd", k = 3
输出：2
解释：可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。

示例 2 ：

输入：s = "adbcda", k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。

 

提示：

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

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

思考

要选出尽量多条长度至少为 $k$ 且互不重叠的回文子串。 $n\le 2000$，按切分方案搜索状态过多。子串是否回文可以先用区间 DP 在 $O(n^2)$ 内全部算好，记在 $g[i][j]$。剩下只是在这些合法区间里做不重叠选取：从位置 $i$ 出发，要么丢掉 $s[i]$，要么选一条以 $i$ 开头、长度至少为 $k$ 的回文再跳到它的右端点之后。从右往左填 $f[i]$，每个位置的决策只依赖更大的下标。

我们先预处理字符串 $s$，得到 $g[i][j]$ 表示子串 $s[i..j]$ 是否为回文串。

然后定义 $f[i]$ 表示从字符串 $s[i..]$ 中能选出的不重叠回文子串的最大个数。初始时 $f[n]=0$。对于 $i$ 从 $n-1$ 倒序遍历到 $0$，可以选择跳过 $s[i]$，即 $f[i]=f[i+1]$；也可以枚举结束位置 $j$（ $j\ge i+k-1$），若 $g[i][j]$ 为真，则可以选中该回文串，并从 $j+1$ 继续。即：

$$\begin{array}{rl}f[i]& =\{\begin{array}{ll}0,& i\ge n\\ max\{f[i+1],\underset{\begin{array}{c}j\ge i+k-1\\ g[i][j]\end{array}}{max}\{f[j+1]+1\}\},& i<n\end{array}\end{array}$$

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

func maxPalindromes(s string, k int) int {
	n := len(s)
	g := make([][]bool, n)
	for i := range g {
		g[i] = make([]bool, n)
		for j := range g[i] {
			g[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			g[i][j] = s[i] == s[j] && g[i+1][j-1]
		}
	}
	f := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		f[i] = f[i+1]
		for j := i + k - 1; j < n; j++ {
			if g[i][j] {
				f[i] = max(f[i], 1+f[j+1])
			}
		}
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

2478. 完美分割的方案数

困难1 种解法

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

题目、示例与约束

给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。

如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：

• s 被分成 k 段互不相交的子字符串。
• 每个子字符串长度都 至少 为 minLength 。
• 每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 '2' ，'3' ，'5' 和 '7' ，剩下的都是非质数数字。

请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 109 + 7 取余 后的结果。

一个 子字符串 是字符串中一段连续字符串序列。

 

示例 1：

输入：s = "23542185131", k = 3, minLength = 2
输出：3
解释：存在 3 种完美分割方案：
"2354 | 218 | 5131"
"2354 | 21851 | 31"
"2354218 | 51 | 31"

示例 2：

输入：s = "23542185131", k = 3, minLength = 3
输出：1
解释：存在一种完美分割方案："2354 | 218 | 5131" 。

示例 3：

输入：s = "3312958", k = 3, minLength = 1
输出：1
解释：存在一种完美分割方案："331 | 29 | 58" 。

 

提示：

• 1 <= k, minLength <= s.length <= 1000
• s 每个字符都为数字 '1' 到 '9' 之一。

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

思考

每段必须以质数数字开头、非质数结尾，长度至少 $\mathit{\text{minLength}}$，共 $k$ 段。 $n\le 1000$，令 $f[i][j]$ 为前 $i$ 个字符分成 $j$ 段的方案。仅当 $s[i-1]$ 可作段尾时， $f[i][j]$ 等于此前合法段尾的 $f[\cdot ][j-1]$ 之和。

用前缀和 $g$ 把求和变成 $g[i-\mathit{\text{minLength}}][j-1]$。首字符非质数或末字符为质数则无解。

我们定义 $f[i][j]$ 表示前 $i$ 个字符分割成 $j$ 段的方案数。初始化 $f[0][0]=1$，其余 $f[i][j]=0$。

首先，我们需要判断第 $i$ 个字符是否能成为第 $j$ 段的最后一个字符，它需要同时满足以下条件：

1. 第 $i$ 个字符是一个非质数；
2. 第 $i+1$ 个字符是一个质数，或者第 $i$ 个字符是整个字符串的最后一个字符。

如果第 $i$ 个字符不能成为第 $j$ 段的最后一个字符，那么 $f[i][j]=0$。否则有：

$$f[i][j]=\sum _{t=0}^{i-minLength}f[t][j-1]$$

也就是说，我们要枚举上一段的结尾是哪个字符。这里我们用前缀和数组 $g[i][j]=\sum _{t=0}^{i}f[t][j]$ 来优化枚举的时间复杂度。

那么有：

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

时间复杂度 $O(n\times k)$，空间复杂度 $O(n\times k)$。其中 $n$ 和 $k$ 分别是字符串 $s$ 的长度和分割的段数。

func beautifulPartitions(s string, k int, minLength int) int {
	prime := func(c byte) bool {
		return c == '2' || c == '3' || c == '5' || c == '7'
	}
	n := len(s)
	if !prime(s[0]) || prime(s[n-1]) {
		return 0
	}
	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[0][0], g[0][0] = 1, 1
	for i := 1; i <= n; i++ {
		if i >= minLength && !prime(s[i-1]) && (i == n || prime(s[i])) {
			for j := 1; j <= k; j++ {
				f[i][j] = g[i-minLength][j-1]
			}
		}
		for j := 0; j <= k; j++ {
			g[i][j] = (g[i-1][j] + f[i][j]) % mod
		}
	}
	return f[n][k]
}

力扣原题 · Doocs 题解来源

2484. 统计回文子序列数目

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 109 + 7 取余 后返回。

提示：

• 如果一个字符串从前往后和从后往前读相同，那么它是 回文字符串 。
• 子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。

 

示例 1：

输入：s = "103301"
输出：2
解释：
总共有 6 长度为 5 的子序列："10330" ，"10331" ，"10301" ，"10301" ，"13301" ，"03301" 。
它们中有两个（都是 "10301"）是回文的。

示例 2：

输入：s = "0000000"
输出：21
解释：所有 21 个长度为 5 的子序列都是 "00000" ，都是回文的。

示例 3：

输入：s = "9999900000"
输出：2
解释：仅有的两个回文子序列是 "99999" 和 "00000" 。

 

提示：

• 1 <= s.length <= 104
• s 只包含数字字符。

方法一：枚举 + 计数 · Go 实现

思考

长度为 $5$ 的回文子序列形如 $abxba$。 $n\le {10}^4$、字符为数字，枚举中心 $i$ 与两端数字对 $(j,k)$，左侧 $jk$ 出现次数乘右侧 $jk$ 出现次数。

预处理前缀 $\mathit{\text{pre}}[i][j][k]$ 与后缀 $\mathit{\text{suf}}$：扫到数字 $v$ 时，对每个已出现的 $j$ 累加二元组 $(j,v)$。中心两侧相乘后取模。

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

func countPalindromes(s string) int {
	n := len(s)
	pre := [10010][10][10]int{}
	suf := [10010][10][10]int{}
	t := make([]int, n)
	for i, c := range s {
		t[i] = int(c - '0')
	}
	c := [10]int{}
	for i := 1; i <= n; i++ {
		v := t[i-1]
		for j := 0; j < 10; j++ {
			for k := 0; k < 10; k++ {
				pre[i][j][k] = pre[i-1][j][k]
			}
		}
		for j := 0; j < 10; j++ {
			pre[i][j][v] += c[j]
		}
		c[v]++
	}
	c = [10]int{}
	for i := n; i > 0; i-- {
		v := t[i-1]
		for j := 0; j < 10; j++ {
			for k := 0; k < 10; k++ {
				suf[i][j][k] = suf[i+1][j][k]
			}
		}
		for j := 0; j < 10; j++ {
			suf[i][j][v] += c[j]
		}
		c[v]++
	}
	ans := 0
	const mod int = 1e9 + 7
	for i := 1; i <= n; i++ {
		for j := 0; j < 10; j++ {
			for k := 0; k < 10; k++ {
				ans += pre[i-1][j][k] * suf[i+1][j][k]
				ans %= mod
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源