LeetCode Go · 动态规划（14）

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

来源与许可

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

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

2771. 构造最长非递减子数组

中等1 种解法

标签：数组、动态规划

题目、示例与约束

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

让我们定义另一个下标从 0 开始、长度为 n 的整数数组，nums3 。对于范围 [0, n - 1] 的每个下标 i ，你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。

你的任务是使用最优策略为 nums3 赋值，以最大化 nums3 中 最长非递减子数组 的长度。

以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列。

 

示例 1：

输入：nums1 = [2,3,1], nums2 = [1,2,1]
输出：2
解释：构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]
从下标 0 开始到下标 1 结束，形成了一个长度为 2 的非递减子数组 [2,2] 。 
可以证明 2 是可达到的最大长度。

示例 2：

输入：nums1 = [1,3,2,1], nums2 = [2,2,3,4]
输出：4
解释：构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]
整个数组形成了一个长度为 4 的非递减子数组，并且是可达到的最大长度。

示例 3：

输入：nums1 = [1,1], nums2 = [2,2]
输出：2
解释：构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums1[1]] => [1,1] 
整个数组形成了一个长度为 2 的非递减子数组，并且是可达到的最大长度。

 

提示：

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

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

思考

每个下标从 $nums1$ 或 $nums2$ 取一个值，求最长非递减连续段。枚举选取序列是指数级，但段必须连续，只需看相邻两列如何衔接。

用 $f,g$ 分别表示以本列 $nums1$、 $nums2$ 结尾的最长长度，由上一列两个选择中能接上的那些转移。滚动更新并维护全局最大。

我们定义两个变量 $f$ 和 $g$，分别表示当前位置的最长非递减子数组长度，其中 $f$ 表示以 $nums1$ 元素为结尾的最长非递减子数组长度，而 $g$ 表示以 $nums2$ 元素为结尾的最长非递减子数组长度。初始时 $f=g=1$，初始答案 $ans=1$。

接下来，我们在 $i\in [1,n)$ 的范围内遍历数组元素，对于每个 $i$，我们定义两个变量 $ff$ 和 $gg$，分别表示以 $nums1[i]$ 和 $nums2[i]$ 元素为结尾的最长非递减子数组长度，初始化时 $ff=gg=1$。

我们可以通过 $f$ 和 $g$ 的值来计算出 $ff$ 和 $gg$ 的值：

• 如果 $nums1[i]\ge nums1[i-1]$，那么 $ff=max(ff,f+1)$；
• 如果 $nums1[i]\ge nums2[i-1]$，那么 $ff=max(ff,g+1)$；
• 如果 $nums2[i]\ge nums1[i-1]$，那么 $gg=max(gg,f+1)$；
• 如果 $nums2[i]\ge nums2[i-1]$，那么 $gg=max(gg,g+1)$。

然后，我们更新 $f=ff$ 和 $g=gg$，并将 $ans$ 更新为 $max(ans,f,g)$。

遍历结束后，我们返回 $ans$ 即可。

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

func maxNonDecreasingLength(nums1 []int, nums2 []int) int {
	n := len(nums1)
	f, g, ans := 1, 1, 1
	for i := 1; i < n; i++ {
		ff, gg := 1, 1
		if nums1[i] >= nums1[i-1] {
			ff = max(ff, f+1)
		}
		if nums1[i] >= nums2[i-1] {
			ff = max(ff, g+1)
		}
		if nums2[i] >= nums1[i-1] {
			gg = max(gg, f+1)
		}
		if nums2[i] >= nums2[i-1] {
			gg = max(gg, g+1)
		}
		f, g = ff, gg
		ans = max(ans, max(f, g))
	}
	return ans
}

力扣原题 · Doocs 题解来源

2786. 访问数组中的位置使分数最大

中等1 种解法

标签：数组、动态规划

题目、示例与约束

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

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

• 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
• 对于你访问的位置 i ，你可以获得分数 nums[i] 。
• 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

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

注意 ，你一开始的分数为 nums[0] 。

 

示例 1：

输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：

输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。

 

提示：

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

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

思考

从下标 $0$ 向右访问，加上所在值，若与上一步奇偶不同则再减 $x$，求最大得分。不必访问每个下标，但跳跃选择很多。

得分只依赖「上一次奇偶」。 $f[0],f[1]$ 分别表示当前以偶/奇结尾的最大得分：从同奇偶转移不扣分，从另一奇偶转移扣 $x$，再加上本值。扫描后取两者较大。

根据题目描述，我们可以得到以下结论：

1. 从位置 $i$ 移动到位置 $j$ 时，如果 $nums[i]$ 和 $nums[j]$ 的奇偶性不同，那么会损失 $x$ 分；
2. 从位置 $i$ 移动到位置 $j$ 时，如果 $nums[i]$ 和 $nums[j]$ 的奇偶性相同，那么不会损失分数。

因此，我们可以用一个长度为 $2$ 的数组 $f$ 来表示当前位置的奇偶性为 $0$ 和 $1$ 时的最大得分。初始时 $f$ 的值为 $-\mathrm{\infty }$，然后我们再初始化 $f[nums[0]\mathrm{\&}1]=nums[0]$，表示初始位置的得分。

接下来，我们从位置 $1$ 开始遍历数组 $nums$，对于每个位置 $i$ 对应的值 $v$，我们更新 $f[v\mathrm{\&}1]$ 的值为 $f[v\mathrm{\&}1]$ 和 $f[v\mathrm{\&}1\oplus 1]-x$ 的较大值再加上 $v$，即 $f[v\mathrm{\&}1]=max(f[v\mathrm{\&}1],f[v\mathrm{\&}1\oplus 1]-x)+v$。

答案为 $f[0]$ 和 $f[1]$ 中的较大值。

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

func maxScore(nums []int, x int) int64 {
	const inf int = 1 << 40
	f := [2]int{-inf, -inf}
	f[nums[0]&1] = nums[0]
	for _, v := range nums[1:] {
		f[v&1] = max(f[v&1], f[v&1^1]-x) + v
	}
	return int64(max(f[0], f[1]))
}

力扣原题 · Doocs 题解来源

2787. 将一个数字表示成幂的和的方案数

中等1 种解法

标签：动态规划

题目、示例与约束

给你两个 正 整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

 

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。

 

提示：

• 1 <= n <= 300
• 1 <= x <= 5

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

思考

把 $n$ 写成若干互不相同正整数的 $x$ 次幂之和，求方案数。幂次增长很快，可用的底数不超过 $n$，但选或不选仍是子集问题。

这是以 $i^x$ 为物品、容量为 $n$ 的 $0$-$1$ 背包。 $f[i][j]$ 表示考虑前 $i$ 个底数、和为 $j$ 的方案，转移为不选或选 $i^x$。答案为 $f[n][n]$，对 ${10}^9+7$ 取模。

我们定义 $f[i][j]$ 表示在前 $i$ 个正整数中选取一些数的 $x$ 次幂之和等于 $j$ 的方案数，初始时 $f[0][0]=1$，其余均为 $0$。答案为 $f[n][n]$。

对于每个正整数 $i$，我们可以选择不选它或者选它：

• 不选它：此时方案数为 $f[i-1][j]$；
• 选它：此时方案数为 $f[i-1][j-i^x]$（前提是 $j\ge i^x$）。

因此状态转移方程为：

$$f[i][j]=f[i-1][j]+(j\ge i^x?f[i-1][j-i^x]:0)$$

注意到答案可能非常大，我们需要对 ${10}^9+7$ 取余。

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

func numberOfWays(n int, x int) int {
	const mod int = 1e9 + 7
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	for i := 1; i <= n; i++ {
		k := int(math.Pow(float64(i), float64(x)))
		for j := 0; j <= n; j++ {
			f[i][j] = f[i-1][j]
			if k <= j {
				f[i][j] = (f[i][j] + f[i-1][j-k]) % mod
			}
		}
	}
	return f[n][n]
}

力扣原题 · Doocs 题解来源

2801. 统计范围内的步进数字数目

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。

如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。

请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

注意：步进数字不能有前导 0 。

 

示例 1：

输入：low = "1", high = "11"
输出：10
解释：区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。

示例 2：

输入：low = "90", high = "101"
输出：2
解释：区间 [90,101] 内的步进数字为 98 和 101 。总共有 2 个步进数字。所以输出为 2 。

 

提示：

• 1 <= int(low) <= int(high) < 10100
• 1 <= low.length, high.length <= 100
• low 和 high 只包含数字。
• low 和 high 都不含前导 0 。

方法一：数位 DP · Go 实现

思考

$low$ 与 $high$ 以数字串给出，直接枚举区间内每个整数并检查相邻数位之差是否为 $1$，在位数很大时不可行。区间计数可改为 $F(high)-F(low-1)$。步进数只约束相邻数位，与具体数值无关，适合数位 DP。按位置 $pos$、前一位 $pre$、前导零 $lead$ 与上界 $limit$ 记忆化：前导零不参与相邻比较，非前导零仅当尚无前一位或 $|i-pre|=1$ 时转移。

我们注意到，题目求的是区间 $[low,high]$ 内的步进数的个数，对于这种区间 $[l,..r]$ 的问题，我们通常可以考虑转化为求 $[1,r]$ 和 $[1,l-1]$ 的答案，然后相减即可。另外，题目中只涉及到不同数位之间的关系，而不涉及具体的数值，因此我们可以考虑使用数位 DP 来解决。

我们设计一个函数 $dfs(pos,pre,lead,limit)$，表示当前处理到第 $pos$ 位，前一位数字是 $pre$，当前数字是否只包含前导零 $lead$，当前数字是否达到上界 $limit$ 的方案数。其中，而 $pos$ 的范围是 $[0,len(num))$。

函数 $dfs(pos,pre,lead,limit)$ 的执行逻辑如下：

如果 $pos$ 超出了 $num$ 的长度，说明我们已经处理完了所有数位，如果此时 $lead$ 为真，说明当前数字只包含前导零，不是一个合法的数字，我们可以返回 $0$ 表示方案数为 $0$；否则我们返回 $1$ 表示方案数为 $1$。

否则，我们计算得到当前数位的上界 $up$，然后在 $[0,..up]$ 范围内枚举当前数位的数字 $i$：

• 如果 $i=0$ 且 $lead$ 为真，说明当前数字只包含前导零，我们递归计算 $dfs(pos+1,pre,true,limitandi=up)$ 的值并累加到答案中；
• 否则，如果 $pre$ 为 $-1$，或者 $i$ 和 $pre$ 之间的差的绝对值为 $1$，说明当前数字是一个合法的步进数，我们递归计算 $dfs(pos+1,i,false,limitandi=up)$ 的值并累加到答案中。

最终我们返回答案。

在主函数中，我们分别计算 $[1,high]$ 和 $[1,low-1]$ 的答案 $a$ 和 $b$，最终答案为 $a-b$。注意答案的取模运算。

时间复杂度 $O(\log M\times |\mathrm{\Sigma }{|}^2)$，空间复杂度 $O(\log M\times |\mathrm{\Sigma }|)$，其中 $M$ 表示 $high$ 数字的大小，而 $|\mathrm{\Sigma }|$ 表示数字集合。

相似题目：

• 2719. 统计整数数目

func countSteppingNumbers(low string, high string) int {
	const mod = 1e9 + 7
	f := [110][10]int{}
	for i := range f {
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	num := high
	var dfs func(int, int, bool, bool) int
	dfs = func(pos, pre int, lead bool, limit bool) int {
		if pos >= len(num) {
			if lead {
				return 0
			}
			return 1
		}
		if !lead && !limit && f[pos][pre] != -1 {
			return f[pos][pre]
		}
		var ans int
		up := 9
		if limit {
			up = int(num[pos] - '0')
		}
		for i := 0; i <= up; i++ {
			if i == 0 && lead {
				ans += dfs(pos+1, pre, true, limit && i == up)
			} else if pre == -1 || abs(pre-i) == 1 {
				ans += dfs(pos+1, i, false, limit && i == up)
			}
			ans %= mod
		}
		if !lead && !limit {
			f[pos][pre] = ans
		}
		return ans
	}
	a := dfs(0, -1, true, true)
	t := []byte(low)
	for i := len(t) - 1; i >= 0; i-- {
		if t[i] != '0' {
			t[i]--
			break
		}
		t[i] = '9'
	}
	num = string(t)
	f = [110][10]int{}
	for i := range f {
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	b := dfs(0, -1, true, true)
	return (a - b + mod) % mod
}

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

力扣原题 · Doocs 题解来源

2809. 使数组和小于等于 x 的最少时间

困难2 种解法

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

题目、示例与约束

给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：

• 选择任一满足 0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。

同时给你一个整数 x 。

请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间，如果无法实现，那么返回 -1 。

 

示例 1：

输入：nums1 = [1,2,3], nums2 = [1,2,3], x = 4
输出：3
解释：
第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。
第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。
第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。
现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。

示例 2：

输入：nums1 = [1,2,3], nums2 = [3,3,3], x = 4
输出：-1
解释：不管如何操作，nums1 的和总是会超过 x 。

 

提示：

• 1 <= nums1.length <= 103
• 1 <= nums1[i] <= 103
• 0 <= nums2[i] <= 103
• nums1.length == nums2.length
• 0 <= x <= 106

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

思考

同一位置多次操作只有最后一次有效，故操作次数至多为 $n$。第 $j$ 次操作对位置 $i$ 的减量为 $num{s}_1[i]+num{s}_2[i]\cdot j$，为使总减量最大，应将较大的 $num{s}_2$ 尽量靠后操作。按 $num{s}_2$ 排序后， $f[i][j]$ 表示考虑前 $i$ 个数、操作 $j$ 次的最大减量，再找最小 $j$ 使剩余和不超过 $x$。

我们注意到，如果我们多次操作同一个数，那么只有最后一次操作是有意义的，其余的对该数的操作，只会使得其它数字增大。因此，我们最多对每个数操作一次，也即是说，操作次数在 $[0,..n]$ 之间。

我们不妨假设进行了 $j$ 次操作，操作的数字下标分别为 $i_1,i_2,\cdots ,i_j$，那么对于这 $j$ 次操作，每一次可以使得数组元素和减少的值为：

$$\begin{array}{rl}& d_1=num{s}_1[i_1]+num{s}_2[i_1]\times 1\\ & d_2=num{s}_1[i_2]+num{s}_2[i_2]\times 2\\ & \cdots \\ & d_j=num{s}_1[i_j]+num{s}_2[i_j]\times j\end{array}$$

从贪心的角度考虑，为了使得数组元素和的减少量最大，我们应当让 $num{s}_2$ 中的较大元素尽可能放在后面操作。因此，我们可以对 $num{s}_1$ 和 $num{s}_2$ 按照 $num{s}_2$ 的元素值从小到大进行排序。

接下来，我们考虑动态规划的实现。我们用 $f[i][j]$ 表示对于数组 $num{s}_1$ 的前 $i$ 个元素，进行 $j$ 次操作，所能减少的数组元素和的最大值。我们可以得到如下的状态转移方程：

$$f[i][j]=max\{f[i-1][j],f[i-1][j-1]+num{s}_1[i]+num{s}_2[i]\times j\}$$

最后，我们枚举 $j$，找到最小的满足 $s_1+s_2\times j-f[n][j]\le x$ 的 $j$ 即可。

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

func minimumTime(nums1 []int, nums2 []int, x int) int {
	n := len(nums1)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	type pair struct{ a, b int }
	nums := make([]pair, n)
	var s1, s2 int
	for i := range nums {
		s1 += nums1[i]
		s2 += nums2[i]
		nums[i] = pair{nums1[i], nums2[i]}
	}
	sort.Slice(nums, func(i, j int) bool { return nums[i].b < nums[j].b })
	for i := 1; i <= n; i++ {
		for j := 0; j <= n; j++ {
			f[i][j] = f[i-1][j]
			if j > 0 {
				a, b := nums[i-1].a, nums[i-1].b
				f[i][j] = max(f[i][j], f[i-1][j-1]+a+b*j)
			}
		}
	}
	for j := 0; j <= n; j++ {
		if s1+s2*j-f[n][j] <= x {
			return j
		}
	}
	return -1
}

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

思考

$f[i][j]$ 只依赖上一行的 $j$ 与 $j-1$，滚动并倒序枚举 $j$ 即可把空间降为 $O(n)$，转移含义不变。

我们注意到 $f[i][j]$ 只与 $f[i-1][j]$ 和 $f[i-1][j-1]$ 有关，因此可以去掉第一维并从大到小枚举 $j$，将空间复杂度降低到 $O(n)$。

func minimumTime(nums1 []int, nums2 []int, x int) int {
	n := len(nums1)
	f := make([]int, n+1)
	type pair struct{ a, b int }
	nums := make([]pair, n)
	var s1, s2 int
	for i := range nums {
		s1 += nums1[i]
		s2 += nums2[i]
		nums[i] = pair{nums1[i], nums2[i]}
	}
	sort.Slice(nums, func(i, j int) bool { return nums[i].b < nums[j].b })
	for _, e := range nums {
		a, b := e.a, e.b
		for j := n; j > 0; j-- {
			f[j] = max(f[j], f[j-1]+a+b*j)
		}
	}
	for j := 0; j <= n; j++ {
		if s1+s2*j-f[j] <= x {
			return j
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

2811. 判断是否能拆分数组

中等1 种解法

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

题目、示例与约束

给你一个长度为 n 的数组 nums 和一个整数 m 。请你判断能否执行一系列操作，将数组拆分成 n 个 非空 数组。

一个数组被称为 好 的，如果：

• 子数组的长度为 1 ，或者
• 子数组元素之和 大于或等于  m 。

在每一步操作中，你可以选择一个 长度至少为 2 的现有数组（之前步骤的结果） 并将其拆分成 2 个子数组，而得到的 每个 子数组都需要是好的。

如果你可以将给定数组拆分成 n 个满足要求的数组，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [2, 2, 1], m = 4

输出：true

解释：

• 将 [2, 2, 1] 切分为 [2, 2] 和 [1]。数组 [1] 的长度为 1，数组 [2, 2] 的元素之和等于 4 >= m，所以两者都是好的数组。
• 将 [2, 2] 切分为 [2] 和 [2]。两个数组的长度都是 1，所以都是好的数组。

示例 2：

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

输出：false

解释：

第一步必须是以下之一：

• 将 [2, 1, 3] 切分为 [2, 1] 和 [3]。数组 [2, 1] 既不是长度为 1，也没有大于或等于 m 的元素和。
• 将 [2, 1, 3] 切分为 [2] 和 [1, 3]。数组 [1, 3] 既不是长度为 1，也没有大于或等于 m 的元素和。

因此，由于这两个操作都无效（它们没有将数组分成两个好的数组），因此我们无法将 nums 分成 n 个大小为 1 的数组。

示例 3：

输入：nums = [2, 3, 3, 2, 3], m = 6

输出：true

解释：

• 将 [2, 3, 3, 2, 3] 切分为 [2] 和 [3, 3, 2, 3]。
• 将 [3, 3, 2, 3] 切分为 [3, 3, 2] 和 [3]。
• 将 [3, 3, 2] 切分为 [3, 3] 和 [2]。
• 将 [3, 3] 切分为 [3] 和 [3]。

 

提示：

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

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

思考

每次拆分要求切出的两段要么长度为 $1$，要么元素和至少为 $m$。区间状态有 $O(n^2)$ 个，可以记忆化。预处理前缀和后， $dfs(i,j)$ 枚举切点 $k$，检查左右段是否合法并递归两端。

我们先预处理得到前缀和数组 $s$，其中 $s[i]$ 表示数组 $nums$ 的前 $i$ 个元素之和。

接下来，我们设计一个函数 $dfs(i,j)$，表示对于数组 $nums$ 的下标范围 $[i,j]$，是否存在一种满足条件的拆分方法。如果存在，返回 true，否则返回 false。

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

如果 $i=j$，那么只有一个元素，不需要拆分，返回 true；

否则，我们枚举拆分点 $k$，其中 $k\in [i,j]$，如果满足以下条件，那么就可以拆分成 $nums[i,..k]$ 和 $nums[k+1,..j]$ 两个子数组：

• 子数组 $nums[i,..k]$ 只有一个元素，或者子数组 $nums[i,..k]$ 的元素之和大于等于 $m$；
• 子数组 $nums[k+1,..j]$ 只有一个元素，或者子数组 $nums[k+1,..j]$ 的元素之和大于等于 $m$；
• $dfs(i,k)$ 和 $dfs(k+1,j)$ 都为 true。

为了避免重复计算，我们使用记忆化搜索的方法，用一个二维数组 $f$ 记录所有的 $dfs(i,j)$ 的返回值，其中 $f[i][j]$ 表示 $dfs(i,j)$ 的返回值。

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

func canSplitArray(nums []int, m int) bool {
	n := len(nums)
	f := make([][]int, n)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	for i := range f {
		f[i] = make([]int, n)
	}
	var dfs func(i, j int) bool
	dfs = func(i, j int) bool {
		if i == j {
			return true
		}
		if f[i][j] != 0 {
			return f[i][j] == 1
		}
		for k := i; k < j; k++ {
			a := k == i || s[k+1]-s[i] >= m
			b := k == j-1 || s[j+1]-s[k+1] >= m
			if a && b && dfs(i, k) && dfs(k+1, j) {
				f[i][j] = 1
				return true
			}
		}
		f[i][j] = -1
		return false
	}
	return dfs(0, n-1)
}

力扣原题 · Doocs 题解来源

2826. 将三个组排序

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums 。nums 的每个元素是 1，2 或 3。在每次操作中，你可以删除 nums 中的一个元素。返回使 nums 成为 非递减 顺序所需操作数的 最小值。

 

示例 1：

输入：nums = [2,1,3,2,1]
输出：3
解释：
其中一个最优方案是删除 nums[0]，nums[2] 和 nums[3]。

示例 2：

输入：nums = [1,3,2,1,3,3]
输出：2
解释：
其中一个最优方案是删除 nums[1] 和 nums[2]。

示例 3：

输入：nums = [2,2,2,2,3,3]
输出：0
解释：
nums 已是非递减顺序的。

 

提示：

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

进阶：你可以使用 O(n) 时间复杂度以内的算法解决吗？

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

思考

美丽数组是值域为 $\{1,2,3\}$ 的非降序列，每次可将一个数改成另一值。若枚举每个位置的最终值，需保证从左到右不降。 $f[j]$ 表示当前前缀末项变为 $j+1$ 的最少操作，转移只从不超过 $j$ 的前一状态而来，并滚动保存三态。

我们定义 $f[i][j]$ 表示将前 $i$ 个数变成美丽数组，并且第 $i$ 个数变成 $j+1$ 的最少操作次数。那么答案就是 $min(f[n][0],f[n][1],f[n][2])$。

我们可以枚举第 $i$ 个数变成 $j+1$ 的所有情况，然后取最小值。这里我们可以用滚动数组优化空间复杂度。

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

func minimumOperations(nums []int) int {
	f := make([]int, 3)
	for _, x := range nums {
		g := make([]int, 3)
		if x == 1 {
			g[0] = f[0]
			g[1] = min(f[0], f[1]) + 1
			g[2] = min(f[0], min(f[1], f[2])) + 1
		} else if x == 2 {
			g[0] = f[0] + 1
			g[1] = min(f[0], f[1])
			g[2] = min(f[0], min(f[1], f[2])) + 1
		} else {
			g[0] = f[0] + 1
			g[1] = min(f[0], f[1]) + 1
			g[2] = min(f[0], min(f[1], f[2]))
		}
		f = g
	}
	return min(f[0], min(f[1], f[2]))
}

力扣原题 · Doocs 题解来源

2827. 范围中美丽整数的数目

困难1 种解法

标签：数学、动态规划

题目、示例与约束

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是 美丽的 ：

• 偶数数位的数目与奇数数位的数目相同。
• 这个整数可以被 k 整除。

请你返回范围 [low, high] 中美丽整数的数目。

 

示例 1：

输入：low = 10, high = 20, k = 3
输出：2
解释：给定范围中有 2 个美丽数字：[12,18]
- 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
- 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
以下是一些不是美丽整数的例子：
- 16 不是美丽整数，因为它不能被 k = 3 整除。
- 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
给定范围内总共有 2 个美丽整数。

示例 2：

输入：low = 1, high = 10, k = 1
输出：1
解释：给定范围中有 1 个美丽数字：[10]
- 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。

示例 3：

输入：low = 5, high = 5, k = 2
输出：0
解释：给定范围中有 0 个美丽数字。
- 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。

 

提示：

• 0 < low <= high <= 109
• 0 < k <= 20

方法一：数位 DP · Go 实现

思考

美丽整数要求偶数位与奇数位个数相等且能被 $k$ 整除，区间上界很大，不宜枚举。化为 $F(high)-F(low-1)$ 后做数位 DP：余数 $mod$、奇偶个数差 $diff$（以 $10$ 为偏移避免负数）、前导零与上界。前导零不计入奇偶差。

我们注意到，题目求的是区间 $[low,high]$ 内的美丽整数的个数，对于这种区间 $[l,..r]$ 的问题，我们通常可以考虑转化为求 $[1,r]$ 和 $[1,l-1]$ 的答案，然后相减即可。另外，题目中只涉及到不同数位之间的关系，而不涉及具体的数值，因此我们可以考虑使用数位 DP 来解决。

我们设计一个函数 $dfs(pos,mod,diff,lead,limit)$，表示当前处理到第 $pos$ 位，当前数字模 $k$ 的结果为 $mod$，当前数字的奇偶数位差为 $diff$，当前数字是否有前导零为 $lead$，当前数字是否达到上界为 $limit$ 时的方案数。

函数 $dfs(pos,mod,diff,lead,limit)$ 的执行逻辑如下：

如果 $pos$ 超出了 $num$ 的长度，说明我们已经处理完了所有数位，如果此时 $mod=0$，并且 $diff=0$，说明当前数字满足题目要求，我们返回 $1$，否则返回 $0$。

否则，我们计算得到当前数位的上界 $up$，然后在 $[0,..up]$ 范围内枚举当前数位的数字 $i$：

• 如果 $i=0$ 且 $lead$ 为真，说明当前数字只包含前导零，我们递归计算 $dfs(pos+1,mod,diff,1,limitandi=up)$ 的值并累加到答案中；
• 否则，我们根据 $i$ 的奇偶性更新 $diff$ 的值，然后递归计算 $dfs(pos+1,(mod\times 10+i)modk,diff,0,limitandi=up)$ 的值并累加到答案中。

最终我们返回答案。

在主函数中，我们分别计算 $[1,high]$ 和 $[1,low-1]$ 的答案 $a$ 和 $b$，最终答案为 $a-b$。

时间复杂度 $O((\log M{)}^2\times k\times |\mathrm{\Sigma }|)$，空间复杂度 $O((\log M{)}^2\times k\times )$，其中 $M$ 表示 $high$ 数字的大小，而 $|\mathrm{\Sigma }|$ 表示数字集合。

相似题目：

• 2719. 统计整数数目

func numberOfBeautifulIntegers(low int, high int, k int) int {
	s := strconv.Itoa(high)
	f := g(len(s), k, 21)

	var dfs func(pos, mod, diff int, lead, limit bool) int
	dfs = func(pos, mod, diff int, lead, limit bool) int {
		if pos >= len(s) {
			if mod == 0 && diff == 10 {
				return 1
			}
			return 0
		}
		if !lead && !limit && f[pos][mod][diff] != -1 {
			return f[pos][mod][diff]
		}
		up := 9
		if limit {
			up = int(s[pos] - '0')
		}
		ans := 0
		for i := 0; i <= up; i++ {
			if i == 0 && lead {
				ans += dfs(pos+1, mod, diff, true, limit && i == up)
			} else {
				nxt := diff + 1
				if i%2 == 0 {
					nxt -= 2
				}
				ans += dfs(pos+1, (mod*10+i)%k, nxt, false, limit && i == up)
			}
		}
		if !lead && !limit {
			f[pos][mod][diff] = ans
		}
		return ans
	}

	a := dfs(0, 0, 10, true, true)
	s = strconv.Itoa(low - 1)
	f = g(len(s), k, 21)
	b := dfs(0, 0, 10, true, true)
	return a - b
}

func g(m, n, k int) [][][]int {
	f := make([][][]int, m)
	for i := 0; i < m; i++ {
		f[i] = make([][]int, n)
		for j := 0; j < n; j++ {
			f[i][j] = make([]int, k)
			for d := 0; d < k; d++ {
				f[i][j][d] = -1
			}
		}
	}
	return f
}

力扣原题 · Doocs 题解来源

2830. 销售利润最大化

中等1 种解法

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

题目、示例与约束

给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。

另给你一个二维整数数组 offers ，其中 offers[i] = [starti, endi, goldi] 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 endi 的所有房屋。

作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。

返回你可以赚取的金币的最大数目。

注意 同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。

 

示例 1：

输入：n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
输出：3
解释：
有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,0] 范围内的房屋以 1 金币的价格出售给第 1 位买家，并将位于 [1,3] 范围内的房屋以 2 金币的价格出售给第 3 位买家。
可以证明我们最多只能获得 3 枚金币。

示例 2：

输入：n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
输出：10
解释：有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,2] 范围内的房屋以 10 金币的价格出售给第 2 位买家。
可以证明我们最多只能获得 10 枚金币。

 

提示：

• 1 <= n <= 105
• 1 <= offers.length <= 105
• offers[i].length == 3
• 0 <= starti <= endi <= n - 1
• 1 <= goldi <= 103

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

思考

房屋不能重叠出售，要约之间存在先后约束。按结束位置排序后， $f[i]$ 表示前 $i$ 个要约的最大收益：不选第 $i$ 个则继承 $f[i-1]$，选则需找到最后一个结束位置不超过其起点的要约。结束位置单调，故该前驱可用二分在 $O(\log n)$ 内定位。

我们将所有的购买要约按照 $end$ 从小到大排序，然后使用动态规划求解。

定义 $f[i]$ 表示前 $i$ 个购买要约中，我们可以获得的最大金币数。答案即为 $f[n]$。

对于 $f[i]$，我们可以选择不卖出第 $i$ 个购买要约，此时 $f[i]=f[i-1]$；也可以选择卖出第 $i$ 个购买要约，此时 $f[i]=f[j]+gol{d}_i$，其中 $j$ 是满足 $en{d}_j\le star{t}_i$ 的最大下标。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是购买要约的数量。

func maximizeTheProfit(n int, offers [][]int) int {
	sort.Slice(offers, func(i, j int) bool { return offers[i][1] < offers[j][1] })
	n = len(offers)
	f := make([]int, n+1)
	g := []int{}
	for _, o := range offers {
		g = append(g, o[1])
	}
	for i := 1; i <= n; i++ {
		j := sort.SearchInts(g, offers[i-1][0])
		f[i] = max(f[i-1], f[j]+offers[i-1][2])
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

2836. 在传球游戏中最大化函数值

困难1 种解法

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

题目、示例与约束

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。

总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。

你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。

如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver(k)[x] 。

你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。

请你返回函数的 最大值 。

注意：receiver 可能含有重复元素。

 

示例 1：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			2
1	2	1	3
2	1	0	3
3	0	2	5
4	2	1	6

 

输入：receiver = [2,0,1], k = 4
输出：6
解释：上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。

示例 2：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			4
1	4	3	7
2	3	2	9
3	2	1	10

 

输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

 

提示：

• 1 <= receiver.length == n <= 105
• 0 <= receiver[i] <= n - 1
• 1 <= k <= 1010

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

思考

从每名玩家沿 $receiver$ 走 $k$ 步并累加编号， $k$ 很大，逐步模拟不可行。传球关系是函数图，可用倍增： $f[i][j]$ 为走 $2^j$ 步到达的点， $g[i][j]$ 为这段路径上的编号和（不含终点）。按 $k$ 的二进制位拼接即可。

题目要我们寻找从每个玩家 $i$ 开始，传球 $k$ 次内所有接触过球玩家的编号之和的最大值。如果暴力求解，需要从 $i$ 开始向上遍历 $k$ 次，时间复杂度为 $O(k)$，显然会超时。

我们可以使用动态规划，结合倍增的思想来处理。

我们定义 $f[i][j]$ 表示从玩家 $i$ 开始，传球 $2^j$ 次所能到达的玩家编号，定义 $g[i][j]$ 表示从玩家 $i$ 开始，传球 $2^j$ 次所能到达的玩家编号之和（不包括最后一个玩家）。

当 $j=0$ 是，传球次数为 $1$，所以 $f[i][0]=receiver[i]$，而 $g[i][0]=i$。

当 $j>0$ 时，传球次数为 $2^j$，相当于从玩家 $i$ 开始，传球 $2^{j-1}$ 次，再从玩家 $f[i][j-1]$ 开始，传球 $2^{j-1}$ 次，所以 $f[i][j]=f[f[i][j-1]][j-1]$，而 $g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]$。

接下来，我们可以枚举每个玩家 $i$ 作为开始玩家，然后根据 $k$ 的二进制表示，累计向上查询，最终得到玩家 $i$ 开始，传球 $k$ 次内所有接触过球玩家的编号之和的最大值。

时间复杂度 $O(n\times \log k)$，空间复杂度 $O(n\times \log k)$。其中 $n$ 为玩家数。

相似题目：

• 1483. 树节点的第 K 个祖先

func getMaxFunctionValue(receiver []int, k int64) (ans int64) {
	n, m := len(receiver), bits.Len(uint(k))
	f := make([][]int, n)
	g := make([][]int64, n)
	for i := range f {
		f[i] = make([]int, m)
		g[i] = make([]int64, m)
		f[i][0] = receiver[i]
		g[i][0] = int64(i)
	}
	for j := 1; j < m; j++ {
		for i := 0; i < n; i++ {
			f[i][j] = f[f[i][j-1]][j-1]
			g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1]
		}
	}
	for i := 0; i < n; i++ {
		p := i
		t := int64(0)
		for j := 0; j < m; j++ {
			if k>>j&1 == 1 {
				t += g[p][j]
				p = f[p][j]
			}
		}
		ans = max(ans, t+int64(p))
	}
	return
}

力扣原题 · Doocs 题解来源

2850. 将石头分散到网格图的最少移动次数

中等2 种解法

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

题目、示例与约束

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

 

示例 1：

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。

示例 2：

输入：grid = [[1,3,0],[1,0,0],[1,0,3]]
输出：4
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。
2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。
3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。
总共需要 4 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 4 。

 

提示：

• grid.length == grid[i].length == 3
• 0 <= grid[i][j] <= 9
• grid 中元素之和为 9 。

方法一：朴素 BFS · Go 实现

思考

格子仅 $3\times 3$，状态空间很小。把多余石头移到相邻空缺是最短路问题，从初始网格 BFS 到每格恰有一枚石头即可。

题目实际上是求一个状态图中从初始状态到目标状态的最短路径，因此可以使用 BFS 求解。初始状态为 grid，目标状态为 [[1, 1, 1], [1, 1, 1], [1, 1, 1]]，在每次操作中，我们可以将一个单元格大于 $1$ 的石头移动到相邻的一个不超过 $1$ 的单元格。如果找到了目标状态，那么就可以返回当前的层数，即为最少移动次数。

type Queue []string

func (q *Queue) Push(s string) {
	*q = append(*q, s)
}

func (q *Queue) Pop() string {
	s := (*q)[0]
	*q = (*q)[1:]
	return s
}

func (q *Queue) Empty() bool {
	return len(*q) == 0
}

func minimumMoves(grid [][]int) int {
	q := Queue{f(grid)}
	vis := map[string]bool{f(grid): true}
	dirs := []int{-1, 0, 1, 0, -1}

	for ans := 0; ; ans++ {
		sz := len(q)
		for ; sz > 0; sz-- {
			p := q.Pop()
			if p == "111111111" {
				return ans
			}
			cur := g(p)

			for i := 0; i < 3; i++ {
				for j := 0; j < 3; j++ {
					if cur[i][j] > 1 {
						for d := 0; d < 4; d++ {
							x, y := i+dirs[d], j+dirs[d+1]
							if x >= 0 && x < 3 && y >= 0 && y < 3 && cur[x][y] < 2 {
								nxt := make([][]int, 3)
								for r := range nxt {
									nxt[r] = append([]int(nil), cur[r]...)
								}
								nxt[i][j]--
								nxt[x][y]++
								s := f(nxt)
								if !vis[s] {
									vis[s] = true
									q.Push(s)
								}
							}
						}
					}
				}
			}
		}
	}
}

func f(grid [][]int) string {
	var sb strings.Builder
	for _, row := range grid {
		for _, x := range row {
			sb.WriteByte(byte(x) + '0')
		}
	}
	return sb.String()
}

func g(s string) [][]int {
	grid := make([][]int, 3)
	for i := range grid {
		grid[i] = make([]int, 3)
		for j := 0; j < 3; j++ {
			grid[i][j] = int(s[i*3+j] - '0')
		}
	}
	return grid
}

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

思考

BFS 仍要展开邻接移动。空格与多余石头一一对应，最少步数是最小费用匹配。空格数至多 $8$，用二进制表示已匹配的多余石头，按曼哈顿距离做状态压缩 DP，避免逐步模拟移动。

我们可以把所有值为 $0$ 的单元格坐标 $(i,j)$ 放入数组 $left$ 中，如果单元格的值 $v$ 大于 $1$，那么我们把 $v-1$ 个坐标 $(i,j)$ 放入数组 $right$ 中。那么问题就转化为，每个 $right$ 中的坐标 $(i,j)$ 都要移动到 $left$ 中的一个坐标 $(x,y)$，求最少的移动次数。

我们记 $left$ 的长度为 $n$，那么我们可以使用 $n$ 位二进制数来表示 $left$ 中的每个坐标是否被 $right$ 中的坐标填充，其中 $1$ 表示被填充，而 $0$ 表示未被填充。初始时 $f[i]=\mathrm{\infty }$，其余 $f[0]=0$。

考虑 $f[i]$，记当前 $i$ 的二进制表示中 $1$ 的个数为 $k$，我们在 $[0..n)$ 的范围内枚举 $j$，如果 $i$ 的第 $j$ 位为 $1$，那么 $f[i]$ 可以由 $f[i\oplus (1<<j)]$ 转移而来，转移的代价为 $cal(left[k-1],right[j])$，其中 $cal$ 表示两个坐标之间的曼哈顿距离。最终答案为 $f[(1<<n)-1]$。

时间复杂度 $O(n\times 2^n)$，空间复杂度 $O(2^n)$。其中 $n$ 表示 $left$ 的长度，本题中 $n\le 9$。

func minimumMoves(grid [][]int) int {
	left := [][2]int{}
	right := [][2]int{}
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if grid[i][j] == 0 {
				left = append(left, [2]int{i, j})
			} else {
				for k := 1; k < grid[i][j]; k++ {
					right = append(right, [2]int{i, j})
				}
			}
		}
	}
	cal := func(a, b [2]int) int {
		return abs(a[0]-b[0]) + abs(a[1]-b[1])
	}
	n := len(left)
	f := make([]int, 1<<n)
	f[0] = 0
	for i := 1; i < 1<<n; i++ {
		f[i] = 1 << 30
		k := bits.OnesCount(uint(i))
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				f[i] = min(f[i], f[i^(1<<j)]+cal(left[k-1], right[j]))
			}
		}
	}
	return f[(1<<n)-1]
}

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

力扣原题 · Doocs 题解来源

2851. 字符串转换

困难1 种解法

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

题目、示例与约束

给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作：

• 将 s 长度为 l （0 < l < n）的 后缀字符串 删除，并将它添加在 s 的开头。
  比方说，s = 'abcd' ，那么一次操作中，你可以删除后缀 'cd' ，并将它添加到 s 的开头，得到 s = 'cdab' 。

给你一个整数 k ，请你返回 恰好 k 次操作将 s 变为 t 的方案数。

由于答案可能很大，返回答案对 109 + 7 取余 后的结果。

 

示例 1：

输入：s = "abcd", t = "cdab", k = 2
输出：2
解释：
第一种方案：
第一次操作，选择 index = 3 开始的后缀，得到 s = "dabc" 。
第二次操作，选择 index = 3 开始的后缀，得到 s = "cdab" 。

第二种方案：
第一次操作，选择 index = 1 开始的后缀，得到 s = "bcda" 。
第二次操作，选择 index = 1 开始的后缀，得到 s = "cdab" 。

示例 2：

输入：s = "ababab", t = "ababab", k = 1
输出：2
解释：
第一种方案：
选择 index = 2 开始的后缀，得到 s = "ababab" 。

第二种方案：
选择 index = 4 开始的后缀，得到 s = "ababab" 。

 

提示：

• 2 <= s.length <= 5 * 105
• 1 <= k <= 1015
• s.length == t.length
• s 和 t 都只包含小写英文字母。

方法一 · Go 实现

思考

每次操作是把 $s$ 旋转一位，结果可由 $s[0]$ 的新下标表示。在 $s+t+t$ 上做 Z 函数，即可找出哪些旋转与 $t$ 相同。 $k$ 次旋转的方案数只区分「回到原串」与「其它旋转」两类，转移是常系数线性递推，用矩阵快速幂在 $O(\log k)$ 内求出后再按匹配位置累加。

func numberOfWays(s string, t string, k int64) int {
	const mod = 1_000_000_007
	add := func(x, y int) int {
		x += y
		if x >= mod {
			x -= mod
		}
		return x
	}
	mul := func(x, y int) int {
		return int(int64(x) * int64(y) % mod)
	}
	getZ := func(s string) []int {
		n := len(s)
		z := make([]int, n)
		left, right := 0, 0
		for i := 1; i < n; i++ {
			if i <= right && z[i-left] <= right-i {
				z[i] = z[i-left]
			} else {
				zI := right - i + 1
				if zI < 0 {
					zI = 0
				}
				for i+zI < n && s[i+zI] == s[zI] {
					zI++
				}
				z[i] = zI
			}
			if i+z[i]-1 > right {
				left = i
				right = i + z[i] - 1
			}
		}
		return z
	}
	matrixMultiply := func(a, b [][]int) [][]int {
		m, n, p := len(a), len(a[0]), len(b[0])
		r := make([][]int, m)
		for i := range r {
			r[i] = make([]int, p)
			for j := 0; j < p; j++ {
				for k := 0; k < n; k++ {
					r[i][j] = add(r[i][j], mul(a[i][k], b[k][j]))
				}
			}
		}
		return r
	}
	matrixPower := func(a [][]int, y int64) [][]int {
		n := len(a)
		r := make([][]int, n)
		x := make([][]int, n)
		for i := 0; i < n; i++ {
			r[i] = make([]int, n)
			x[i] = make([]int, n)
			r[i][i] = 1
			copy(x[i], a[i])
		}
		for y > 0 {
			if y&1 == 1 {
				r = matrixMultiply(r, x)
			}
			x = matrixMultiply(x, x)
			y >>= 1
		}
		return r
	}
	n := len(s)
	dp := matrixPower([][]int{{0, 1}, {n - 1, n - 2}}, k)[0]
	s += t + t
	z := getZ(s)
	result := 0
	for i := n; i < n+n; i++ {
		if z[i] >= n {
			if i-n == 0 {
				result = add(result, dp[0])
			} else {
				result = add(result, dp[1])
			}
		}
	}
	return result
}

力扣原题 · Doocs 题解来源

2892. 将相邻元素相乘后得到最小化数组 🔒

中等1 种解法

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

题目、示例与约束

给定一个整数数组 nums 和一个整数 k，你可以对数组执行以下操作任意次数：

• 选择数组中的两个 相邻 元素，例如 x 和 y，使得 x * y <= k ，并用一个值为 x * y 的 单个元素 替换它们（例如，在一次操作中，数组 [1, 2, 2, 3]，其中 k = 5 可以变为 [1, 4, 3] 或 [2, 2, 3]，但不能变为 [1, 2, 6]）。

返回 经过任意次数的操作后， nums 的 最小 可能长度。

 

示例 1：

输入：nums = [2,3,3,7,3,5], k = 20
输出：3
解释：我们执行以下操作：
1. [2,3,3,7,3,5] -> [6,3,7,3,5]
2. [6,3,7,3,5] -> [18,7,3,5]
3. [18,7,3,5] -> [18,7,15]
可以证明，在执行给定操作后，最小可能长度为3.

示例 2：

输入：nums = [3,3,3,3], k = 6
输出：4
解释：由于每两个相邻元素的乘积都大于 6，所以无法执行任何操作。因此，答案为 4。

 

约束条件：

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

方法一：贪心 · Go 实现

思考

相邻且乘积不超过 $k$ 的数可以合并。出现 $0$ 时整段乘积为 $0$，长度可缩至 $1$。否则从左到右能乘就乘进当前段，否则新开一段，这样得到的段数最少。

我们用一个变量 $ans$ 记录当前数组的长度，用一个变量 $y$ 记录当前数组的乘积，初始时 $ans=1$, $y=nums[0]$。

我们从数组的第二个元素开始遍历，设当前元素为 $x$：

• 如果 $x=0$，那么整个数组的乘积为 $0\le k$，因此答案数组的最小长度为 $1$，直接返回即可。
• 如果 $x\times y\le k$，那么我们可以将 $x$ 与 $y$ 合并，即 $y=x\times y$。
• 如果 $x\times y>k$，那么我们无法将 $x$ 与 $y$ 合并，因此我们需要将 $x$ 单独作为一个元素，即 $ans=ans+1$，并且 $y=x$。

最终答案即为 $ans$。

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

func minArrayLength(nums []int, k int) int {
	ans, y := 1, nums[0]
	for _, x := range nums[1:] {
		if x == 0 {
			return 1
		}
		if x*y <= k {
			y *= x
		} else {
			y = x
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2896. 执行操作使两个字符串相等

中等1 种解法

标签：字符串、动态规划

题目、示例与约束

给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 x 。

你可以对字符串 s1 执行以下操作 任意次 ：

• 选择两个下标 i 和 j ，将 s1[i] 和 s1[j] 都反转，操作的代价为 x 。
• 选择满足 i < n - 1 的下标 i ，反转 s1[i] 和 s1[i + 1] ，操作的代价为 1 。

请你返回使字符串 s1 和 s2 相等的 最小 操作代价之和，如果无法让二者相等，返回 -1 。

注意 ，反转字符的意思是将 0 变成 1 ，或者 1 变成 0 。

 

示例 1：

输入：s1 = "1100011000", s2 = "0101001010", x = 2
输出：4
解释：我们可以执行以下操作：
- 选择 i = 3 执行第二个操作。结果字符串是 s1 = "1101111000" 。
- 选择 i = 4 执行第二个操作。结果字符串是 s1 = "1101001000" 。
- 选择 i = 0 和 j = 8 ，执行第一个操作。结果字符串是 s1 = "0101001010" = s2 。
总代价是 1 + 1 + 2 = 4 。这是最小代价和。

示例 2：

输入：s1 = "10110", s2 = "00011", x = 4
输出：-1
解释：无法使两个字符串相等。

 

提示：

• n == s1.length == s2.length
• 1 <= n, x <= 500
• s1 和 s2 只包含字符 '0' 和 '1' 。

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

思考

每次翻转两位，不同位置个数为奇数则无解。把不同下标收入 $idx$ 后，区间 $dfs(i,j)$ 的最小代价来自三种配对：两端用代价 $x$ 配对，或左端与次左、右端与次右按距离配对。

我们注意到，由于每次操作都是反转两个字符，因此，如果不同的字符个数为奇数，那么无法使两个字符串相等，直接返回 $-1$。否则，我们将两个字符串中不同的字符的下标存入数组 $idx$ 中，记数组长度为 $m$。

接下来，我们设计一个函数 $dfs(i,j)$，表示将 $idx[i..j]$ 中的字符反转的最小操作代价。答案即为 $dfs(0,m-1)$。

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

如果 $i>j$，那么不需要进行任何操作，返回 $0$；

否则，我们考虑对区间 $[i,j]$ 的端点进行操作：

• 如果我们对端点 $i$ 进行第一种操作，由于代价 $x$ 已经固定，因此，我们最优的选择是将 $idx[i]$ 和 $idx[j]$ 反转，然后递归计算 $dfs(i+1,j-1)$，总代价为 $dfs(i+1,j-1)+x$；
• 如果我们对端点 $i$ 进行第二种操作，那么我们需要将 $[idx[i]..idx[i+1]]$ 中的字符全部反转，然后递归计算 $dfs(i+2,j)$，总代价为 $dfs(i+2,j)+idx[i+1]-idx[i]$；
• 如果我们对端点 $j$ 进行第二种操作，那么我们需要将 $[idx[j-1]..idx[j]]$ 中的字符全部反转，然后递归计算 $dfs(i,j-2)$，总代价为 $dfs(i,j-2)+idx[j]-idx[j-1]$。

我们取上述三种操作的最小值，即为 $dfs(i,j)$ 的值。

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

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

func minOperations(s1 string, s2 string, x int) int {
	idx := []int{}
	for i := range s1 {
		if s1[i] != s2[i] {
			idx = append(idx, i)
		}
	}
	m := len(idx)
	if m&1 == 1 {
		return -1
	}
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, m)
		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 {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		f[i][j] = dfs(i+1, j-1) + x
		f[i][j] = min(f[i][j], dfs(i+2, j)+idx[i+1]-idx[i])
		f[i][j] = min(f[i][j], dfs(i, j-2)+idx[j]-idx[j-1])
		return f[i][j]
	}
	return dfs(0, m-1)
}

力扣原题 · Doocs 题解来源

2900. 最长相邻不相等子序列 I

简单1 种解法

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

题目、示例与约束

给定一个字符串数组 words ，和一个 二进制 数组 groups ，两个数组长度都是 n 。

如果 words 的一个 子序列 是交替的，那么对于序列中的任意两个连续字符串，它们在 groups 中相同索引的对应元素是 不同 的（也就是说，不能有连续的 0 或 1），

你需要从 words 中选出 最长交替子序列。

返回选出的子序列。如果有多个答案，返回 任意 一个。

注意：words 中的元素是不同的 。

 

示例 1：

输入：words = ["e","a","b"], groups = [0,0,1]
输出：["e","b"]
解释：一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。
所以一个可行的答案是 [words[0],words[2]] = ["e","b"] 。
另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。
得到答案为 [words[1],words[2]] = ["a","b"] 。
这也是一个可行的答案。
符合题意的最长子序列的长度为 2 。

示例 2：

输入：words = ["a","b","c","d"], groups = [1,0,1,1]
输出：["a","b","c"]
解释：一个可行的子序列为 [0,1,2] 因为 groups[0] != groups[1] 且 groups[1] != groups[2] 。
所以一个可行的答案是 [words[0],words[1],words[2]] = ["a","b","c"] 。
另一个可行的子序列为 [0,1,3] 因为 groups[0] != groups[1] 且 groups[1] != groups[3] 。
得到答案为 [words[0],words[1],words[3]] = ["a","b","d"] 。
这也是一个可行的答案。
符合题意的最长子序列的长度为 3 。

 

提示：

• 1 <= n == words.length == groups.length <= 100
• 1 <= words[i].length <= 10
• groups[i] 是 0 或 1。
• words 中的字符串 互不相同 。
• words[i] 只包含小写英文字母。

方法一：贪心 + 一次遍历 · Go 实现

思考

$n\le 100$，按子序列定义枚举或用 $O(n^2)$ 动态规划均可得到最长长度。注意到 $groups$ 仅取 $0$ 或 $1$，相邻项合法当且仅当组别翻转，因此任意一组连续相同组别中至多保留一个下标。

保留每一段的第一个下标即可：它既能与上一段衔接，又不缩短后续可选长度。题目允许任意一个最长子序列，故无需在同组内再比较 $words$。一次从左到右扫描即可构造答案。

我们可以遍历数组 $groups$，对于当前遍历到的下标 $i$，如果 $i=0$ 或者 $groups[i]\ne groups[i-1]$，我们就将 $words[i]$ 加入答案数组中。

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

func getLongestSubsequence(words []string, groups []int) (ans []string) {
	for i, x := range groups {
		if i == 0 || x != groups[i-1] {
			ans = append(ans, words[i])
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2901. 最长相邻不相等子序列 II

中等1 种解法

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

题目、示例与约束

给定一个字符串数组 words ，和一个数组 groups ，两个数组长度都是 n 。

两个长度相等字符串的 汉明距离 定义为对应位置字符 不同 的数目。

你需要从下标 [0, 1, ..., n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, ..., ik - 1] ，它需要满足以下条件：

• 相邻 下标对应的 groups 值 不同。即，对于所有满足 0 < j + 1 < k 的 j 都有 groups[ij] != groups[ij + 1] 。
• 对于所有 0 < j + 1 < k 的下标 j ，都满足 words[ij] 和 words[ij + 1] 的长度 相等 ，且两个字符串之间的 汉明距离 为 1 。

请你返回一个字符串数组，它是下标子序列 依次 对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。

子序列 指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。

注意：words 中的字符串长度可能 不相等 。

 

示例 1：

输入：words = ["bab","dab","cab"], groups = [1,2,2]
输出：["bab","cab"]
解释：一个可行的子序列是 [0,2] 。
- groups[0] != groups[2]
- words[0].length == words[2].length 且它们之间的汉明距离为 1 。
所以一个可行的答案是 [words[0],words[2]] = ["bab","cab"] 。
另一个可行的子序列是 [0,1] 。
- groups[0] != groups[1]
- words[0].length = words[1].length 且它们之间的汉明距离为 1 。
所以另一个可行的答案是 [words[0],words[1]] = ["bab","dab"] 。
符合题意的最长子序列的长度为 2 。

示例 2：

输入：words = ["a","b","c","d"], groups = [1,2,3,4]
输出：["a","b","c","d"]
解释：我们选择子序列 [0,1,2,3] 。
它同时满足两个条件。
所以答案为 [words[0],words[1],words[2],words[3]] = ["a","b","c","d"] 。
它是所有下标子序列里最长且满足所有条件的。
所以它是唯一的答案。

 

提示：

• 1 <= n == words.length == groups.length <= 1000
• 1 <= words[i].length <= 10
• 1 <= groups[i] <= n
• words 中的字符串 互不相同 。
• words[i] 只包含小写英文字母。

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

思考

与上一题不同，相邻两项还须长度相同且汉明距离恰为 $1$，贪心按组别交替选取无法保证连通。 $n$ 通常不超过数百，单词长度很短，因此可以接受 $O(n^2\cdot L)$ 的转移。

以 $f[i]$ 表示以 $i$ 结尾的最长长度， $g[i]$ 记录前驱。枚举 $j<i$，仅当组别不同且 $check$ 成立时用 $f[j]+1$ 更新。最后从达到全局最大值 $mx$ 的下标沿 $g$ 回溯并反转，即得一条具体子序列。

我们定义 $f[i]$ 表示以第 $i$ 个单词结尾的最长相邻不相等子序列的长度，定义 $g[i]$ 表示以第 $i$ 个单词结尾的最长相邻不相等子序列的前驱下标。初始时 $f[i]=1$, $g[i]=-1$。

另外，我们定义一个变量 $mx$ 表示最长相邻不相等子序列的长度。

我们枚举 $i$，枚举 $j\in [0,i)$，如果 $groups[i]\ne groups[j]$ 且 $f[i]<f[j]+1$ 且 $words[i]$ 和 $words[j]$ 之间的汉明距离为 $1$，则更新 $f[i]=f[j]+1$， $g[i]=j$，并且更新 $mx=max(mx,f[i])$。

最后，我们从 $f$ 数组中找到最大值对应的下标 $i$，然后从 $i$ 开始不断往前找，直到找到 $g[i]=-1$，这样就找到了最长相邻不相等子序列。

时间复杂度 $O(n^2\times L)$，空间复杂度 $O(n)$。其中 $L$ 表示单词的最大长度。

func getWordsInLongestSubsequence(words []string, groups []int) []string {
	check := func(s, t string) bool {
		if len(s) != len(t) {
			return false
		}
		cnt := 0
		for i := range s {
			if s[i] != t[i] {
				cnt++
			}
		}
		return cnt == 1
	}
	n := len(groups)
	f := make([]int, n)
	g := make([]int, n)
	for i := range f {
		f[i] = 1
		g[i] = -1
	}
	mx := 1
	for i, x := range groups {
		for j, y := range groups[:i] {
			if x != y && f[i] < f[j]+1 && check(words[i], words[j]) {
				f[i] = f[j] + 1
				g[i] = j
				if mx < f[i] {
					mx = f[i]
				}
			}
		}
	}
	ans := make([]string, 0, mx)
	for i, x := range f {
		if x == mx {
			for j := i; j >= 0; j = g[j] {
				ans = append(ans, words[j])
			}
			break
		}
	}
	slices.Reverse(ans)
	return ans
}

力扣原题 · Doocs 题解来源

2902. 和带限制的子多重集合的数目

困难1 种解法

标签：数组、哈希表、动态规划、背包问题、滑动窗口、多重背包

题目、示例与约束

给你一个下标从 0 开始的非负整数数组 nums 和两个整数 l 和 r 。

请你返回 nums 中子多重集合的和在闭区间 [l, r] 之间的 子多重集合的数目 。

由于答案可能很大，请你将答案对 109 + 7 取余后返回。

子多重集合 指的是从数组中选出一些元素构成的 无序 集合，每个元素 x 出现的次数可以是 0, 1, ..., occ[x] 次，其中 occ[x] 是元素 x 在数组中的出现次数。

注意：

• 如果两个子多重集合中的元素排序后一模一样，那么它们两个是相同的 子多重集合 。
• 空 集合的和是 0 。

 

示例 1：

输入：nums = [1,2,2,3], l = 6, r = 6
输出：1
解释：唯一和为 6 的子集合是 {1, 2, 3} 。

示例 2：

输入：nums = [2,1,4,2,7], l = 1, r = 5
输出：7
解释：和在闭区间 [1, 5] 之间的子多重集合为 {1} ，{2} ，{4} ，{2, 2} ，{1, 2} ，{1, 4} 和 {1, 2, 2} 。

示例 3：

输入：nums = [1,2,1,3,5,2], l = 3, r = 5
输出：9
解释：和在闭区间 [3, 5] 之间的子多重集合为 {3} ，{5} ，{1, 2} ，{1, 3} ，{2, 2} ，{2, 3} ，{1, 1, 2} ，{1, 1, 3} 和 {1, 2, 2} 。

 

提示：

• 1 <= nums.length <= 2 * 104
• 0 <= nums[i] <= 2 * 104
• nums 的和不超过 2 * 104 。
• 0 <= l <= r <= 2 * 104

方法一 · Go 实现

思考

需求区间 $[l,r]$ 内的子多重集个数，元素和不超过 $2\times {10}^4$。若按 0-1 背包逐个放入，时间与 $n\cdot r$ 同阶，偏紧；同一数值至多出现多次，宜按多重背包处理。

对每个非零值 $num$ 及其频次 $freq$，先用步长 $num$ 做前缀 $stride$，使 $stride[i]$ 等于 $dp[i]+dp[i-num]+\cdots$。再减去超出 $freq$ 份的部分，即得到「至多选 $freq$ 个 $num$」的方案。 $0$ 不改变和，只需把结果乘以 $zeros+1$（含不选）。

func countSubMultisets(nums []int, l int, r int) int {
	multiset := make(map[int]int)
	for _, num := range nums {
		multiset[num]++
	}
	mem := make([]int, r+1)
	mem[0] = 1
	prefix := make([]int, len(mem))
	for num, occ := range multiset {
		copy(prefix, mem)
		for sum := num; sum <= r; sum++ {
			prefix[sum] = (prefix[sum] + prefix[sum-num]) % mod
		}
		for sum := r; sum >= 0; sum-- {
			if num > 0 {
				mem[sum] = prefix[sum]
				if sum >= num*(occ+1) {
					mem[sum] = (mem[sum] - prefix[sum-num*(occ+1)] + mod) % mod
				}
			} else {
				mem[sum] = (mem[sum] * (occ + 1)) % mod
			}
		}
	}
	var result int
	for sum := l; sum <= r; sum++ {
		result = (result + mem[sum]) % mod
	}
	return result
}
var mod int = 1e9 + 7

力扣原题 · Doocs 题解来源

2911. 得到 K 个半回文串的最少修改次数

困难1 种解法

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

题目、示例与约束

给你一个字符串 s 和一个整数 k，请将 s 划分为 k 个 非空子串 ，使得将每个子串变为 半回文串 所需的字符修改次数之和最小。

返回所需的 最少 字符修改次数。

半回文串 是一类特殊的字符串：它可以按照某种重复模式拆分后，使每一组都成为 回文串 。判断一个字符串是否为半回文串的方法如下：

1. 选择该字符串长度的一个正因数 d。其中，d 的取值范围是从 1 到严格小于字符串长度的所有正因数。对于长度为 1 的字符串，根据这一定义，它不存在合法的因数，因为唯一的因数就是其长度本身，而这是不允许的。
2. 对于给定的因数 d，将字符串按长度为 d 的重复模式分组。具体来说，第 1 组由位置 1、1 + d、1 + 2d、…… 上的字符组成；第 2 组由位置 2、2 + d、2 + 2d、…… 上的字符组成；以此类推。
3. 如果这些分组中的每一组都是回文串，则该字符串被视为半回文串。

以字符串 "abcabc" 为例：

• "abcabc" 的长度为 6。合法的因数有 1、2 和 3。
• 当 d = 1 时：整个字符串 "abcabc" 构成一组。它不是回文串。
• 当 d = 2 时：
  • 第 1 组（位置 1, 3, 5）："acb"
  • 第 2 组（位置 2, 4, 6）："bac"
  • 这两组都不是回文串。
• 当 d = 3 时：
  • 第 1 组（位置 1, 4）："aa"
  • 第 2 组（位置 2, 5）："bb"
  • 第 3 组（位置 3, 6）："cc"
  • 所有分组都是回文串。因此，"abcabc" 是一个半回文串。

 

示例 1：

输入： s = "abcac", k = 2

输出： 1

解释： 将 s 划分为 "ab" 和 "cac"。"cac" 本身已经是半回文串。将 "ab" 改为 "aa" 后，它在 d = 1 时成为半回文串。

示例 2：

输入： s = "abcdef", k = 2

输出： 2

解释： 将其划分为子串 "abc" 和 "def"。这两个子串各自都需要修改 1 个字符才能变成半回文串。

示例 3：

输入： s = "aabbaa", k = 3

输出： 0

解释： 将其划分为子串 "aa"、"bb" 和 "aa"。它们都已经是半回文串。

 

提示：

• 2 <= s.length <= 200
• 1 <= k <= s.length / 2
• s 仅由小写英文字母组成。

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

思考

把 $s$ 分成 $k$ 段半回文，修改次数最少。 $n\le 200$，可先对每个子串枚举因子 $d$，按半回文配对统计改写次数，得到代价 $g[i][j]$。

划分本身是经典的「切 $k$ 段」DP： $f[i][j]$ 表示前 $i$ 个字符切 $j$ 段的最小代价，枚举上一段右端 $h$ 转移。预处理 $O(n^3)$ 量级，加上划分后仍可接受。

先算每个子串变成半回文的代价，再用二维 $f[i][j]$ 划分成 $j$ 段。

func minimumChanges(s string, k int) int {
	n := len(s)
	g := make([][]int, n+1)
	f := make([][]int, n+1)
	const inf int = 1 << 30
	for i := range g {
		g[i] = make([]int, n+1)
		f[i] = make([]int, k+1)
		for j := range g[i] {
			g[i][j] = inf
		}
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := i; j <= n; j++ {
			m := j - i + 1
			for d := 1; d < m; d++ {
				if m%d == 0 {
					cnt := 0
					for l := 0; l < m; l++ {
						r := (m/d-1-l/d)*d + l%d
						if l >= r {
							break
						}
						if s[i-1+l] != s[i-1+r] {
							cnt++
						}
					}
					g[i][j] = min(g[i][j], cnt)
				}
			}
		}
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= k; j++ {
			for h := 0; h < i-1; h++ {
				f[i][j] = min(f[i][j], f[h][j-1]+g[h+1][i])
			}
		}
	}
	return f[n][k]
}

力扣原题 · Doocs 题解来源

2912. 在网格上移动到目的地的方法数 🔒

困难1 种解法

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

题目、示例与约束

给定两个整数 n 和 m，它们表示一个 下标从 1 开始 的网格的大小。还给定一个整数 k，以及两个 下标从 1 开始 的整数数组 source 和 dest。这两个数组 source 和 dest 形如 [x, y]，表示网格上的一个单元格。

你可以按照以下方式在网格上移动：

• 你可以从单元格 [x1, y1] 移动到 [x2, y2]，只要 x1 == x2 或 y1 == y2。
• 注意，你 不能 移动到当前所在的单元格，即 x1 == x2 且 y1 == y2。

请返回你在网格上从 source 到 dest 移动 k 次一共可以有 多少种 方法。

由于答案可能非常大，因此请对 109 + 7 取模 后返回。

 

示例 1:

输入： n = 3, m = 2, k = 2, source = [1,1], dest = [2,2]
输出： 2
解释： 有两种可能的方式从 [1,1] 到达 [2,2]：
- [1,1] -> [1,2] -> [2,2]
- [1,1] -> [2,1] -> [2,2]

示例 2:

输入： n = 3, m = 4, k = 3, source = [1,2], dest = [2,3]
输出： 9
解释： 有 9 种可能的方式从 [1,2] 到达 [2,3]：:
- [1,2] -> [1,1] -> [1,3] -> [2,3]
- [1,2] -> [1,1] -> [2,1] -> [2,3]
- [1,2] -> [1,3] -> [3,3] -> [2,3]
- [1,2] -> [1,4] -> [1,3] -> [2,3]
- [1,2] -> [1,4] -> [2,4] -> [2,3]
- [1,2] -> [2,2] -> [2,1] -> [2,3]
- [1,2] -> [2,2] -> [2,4] -> [2,3]
- [1,2] -> [3,2] -> [2,2] -> [2,3]
- [1,2] -> [3,2] -> [3,3] -> [2,3]

 

提示：

• 2 <= n, m <= 109
• 1 <= k <= 105
• source.length == dest.length == 2
• 1 <= source[1], dest[1] <= n
• 1 <= source[2], dest[2] <= m

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

思考

每一步只能改行或改列， $k$ 步后到达 $dest$。网格可达 ${10}^9$ 量级，不能按格子建状态。相对 $source$ 仅有四类位置：自身、同列不同行、同行不同列、行列皆不同。

用四维向量 $f$ 记录这四类格子的方案数，一步转移只在这四类之间发生，系数由 $n,m$ 决定。迭代 $k$ 次后，按 $dest$ 与 $source$ 的行列关系选取对应分量。

我们定义以下几个状态，其中：

• $f[0]$ 表示从 $source$ 到 $source$ 本身的方法数；
• $f[1]$ 表示从 $source$ 移动到同一列其它行的方法数；
• $f[2]$ 表示从 $source$ 移动到同一行其它列的方法数；
• $f[3]$ 表示从 $source$ 移动到其它行其它列的方法数。

初始时， $f[0]=1$，其余状态均为 $0$。

对于每个状态，我们可以根据上一次的状态计算出当前的状态，具体如下：

$$\begin{array}{rl}g[0]& =(n-1)\times f[1]+(m-1)\times f[2]\\ g[1]& =f[0]+(n-2)\times f[1]+(m-1)\times f[3]\\ g[2]& =f[0]+(m-2)\times f[2]+(n-1)\times f[3]\\ g[3]& =f[1]+f[2]+(n-2)\times f[3]+(m-2)\times f[3]\end{array}$$

我们循环 $k$ 次，最后判断 $source$ 和 $dest$ 是否在同一行或同一列，返回对应的状态即可。

时间复杂度 $O(k)$，其中 $k$ 为移动次数。空间复杂度 $O(1)$。

func numberOfWays(n int, m int, k int, source []int, dest []int) int {
	const mod int = 1e9 + 7
	f := []int{1, 0, 0, 0}
	for i := 0; i < k; i++ {
		g := make([]int, 4)
		g[0] = ((n-1)*f[1] + (m-1)*f[2]) % mod
		g[1] = (f[0] + (n-2)*f[1] + (m-1)*f[3]) % mod
		g[2] = (f[0] + (m-2)*f[2] + (n-1)*f[3]) % mod
		g[3] = (f[1] + f[2] + (n-2)*f[3] + (m-2)*f[3]) % mod
		f = g
	}

	if source[0] == dest[0] {
		if source[1] == dest[1] {
			return f[0]
		}
		return f[2]
	}

	if source[1] == dest[1] {
		return f[1]
	}
	return f[3]
}

力扣原题 · Doocs 题解来源

2915. 和为目标值的最长子序列的长度

中等2 种解法

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

题目、示例与约束

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

返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。

子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。

 

示例 1：

输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。

示例 2：

输入：nums = [4,1,3,2,1,5], target = 7
输出：4
解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。

示例 3：

输入：nums = [1,1,5,4,5], target = 3
输出：-1
解释：无法得到和为 3 的子序列。

 

提示：

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

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

思考

求元素和恰为 $target$ 的最长子序列，每个数至多用一次，属于 0-1 背包。 $n,target\le 1000$，二维 $f[i][j]$ 记录前 $i$ 个数凑出 $j$ 的最大长度，不可行状态置为 $-\mathrm{\infty }$。

转移在「不选 / 选 $x$」之间取最大。最终若 $f[n][target]$ 非正则无解。

我们定义 $f[i][j]$ 表示前 $i$ 个数中选取若干个数，使得这若干个数的和恰好为 $j$ 的最长子序列的长度。初始时 $f[0][0]=0$，其余位置均为 $-\mathrm{\infty }$。

对于 $f[i][j]$，我们考虑第 $i$ 个数 $x$，如果不选取 $x$，那么 $f[i][j]=f[i-1][j]$；如果选取 $x$，那么 $f[i][j]=f[i-1][j-x]+1$，其中 $j\ge x$。因此我们有状态转移方程：

$$f[i][j]=max\{f[i-1][j],f[i-1][j-x]+1\}$$

最终答案为 $f[n][target]$，如果 $f[n][target]\le 0$，则不存在和为 $target$ 的子序列，返回 $-1$。

时间复杂度 $O(n\times target)$，空间复杂度 $O(n\times target)$。其中 $n$ 为数组长度，而 $target$ 为目标值。

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

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

思考

方法一的 $f[i][j]$ 只依赖上一行，第一维可去掉。每个数至多选一次，内层对容量从大到小更新，以免同一元素被用两次。空间降为 $O(target)$，答案语义不变。

$f[i][j]$ 只与上一行 $f[i-1][\cdot ]$ 有关，因此可以去掉第一维。每个数最多选一次，内层对 $j$ 从大到小更新，空间复杂度降为 $O(target)$。

func lengthOfLongestSubsequence(nums []int, target int) int {
	f := make([]int, target+1)
	for i := range f {
		f[i] = -(1 << 30)
	}
	f[0] = 0
	for _, x := range nums {
		for j := target; j >= x; j-- {
			f[j] = max(f[j], f[j-x]+1)
		}
	}
	if f[target] <= 0 {
		return -1
	}
	return f[target]
}

力扣原题 · Doocs 题解来源

2919. 使数组变美的最小增量运算数

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个整数 k 。

你可以执行下述 递增 运算 任意 次（可以是 0 次）：

• 从范围 [0, n - 1] 中选择一个下标 i ，并将 nums[i] 的值加 1 。

如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。

以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。

子数组是数组中的一个连续 非空 元素序列。

 

示例 1：

输入：nums = [2,3,0,0,2], k = 4
输出：3
解释：可以执行下述递增运算，使 nums 变为美丽数组：
选择下标 i = 1 ，并且将 nums[1] 的值加 1 -> [2,4,0,0,2] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,3] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,4] 。
长度大于或等于 3 的子数组为 [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4] 。
在所有子数组中，最大元素都等于 k = 4 ，所以 nums 现在是美丽数组。
可以证明无法用少于 3 次递增运算使 nums 变为美丽数组。
因此，答案为 3 。

示例 2：

输入：nums = [0,1,3,3], k = 5
输出：2
解释：可以执行下述递增运算，使 nums 变为美丽数组：
选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,4,3] 。
选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,5,3] 。
长度大于或等于 3 的子数组为 [0,1,5]、[1,5,3]、[0,1,5,3] 。
在所有子数组中，最大元素都等于 k = 5 ，所以 nums 现在是美丽数组。
可以证明无法用少于 2 次递增运算使 nums 变为美丽数组。 
因此，答案为 2 。

示例 3：

输入：nums = [1,1,2], k = 1
输出：0
解释：在这个示例中，只有一个长度大于或等于 3 的子数组 [1,1,2] 。
其最大元素 2 已经大于 k = 1 ，所以无需执行任何增量运算。
因此，答案为 0 。

 

提示：

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

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

思考

美丽数组要求每个长度为 $3$ 的窗口最大值至少为 $k$。 $n\le {10}^5$，不能对每个窗口单独枚举加多少。对位置 $i$ 加 $max(k-nums[i],0)$ 后，它能覆盖包含它的窗口，且一个窗口只需其中一个位置达标。

因此状态只需记住「最近三个位置谁被选为覆盖者」的最小代价。滚动 $f,g,h$ 分别对应以倒数第三、二、一项为覆盖点的最优值，读入 $x$ 时用 $min(f,g,h)+max(k-x,0)$ 推进。最终三者取最小。

我们定义 $f$, $g$, $h$ 表示前 $i$ 项中，分别以最后三项作为子数组的最大值所需要的最小增量运算数，初始时 $f=0$, $g=0$, $h=0$。

接下来，我们遍历数组 $nums$，对于每个 $x$，我们需要更新 $f$, $g$, $h$ 的值，使其满足题目要求，即：

$$\begin{array}{rl}{f}^{\prime }& =g\\ g^{\prime }& =h\\ h^{\prime }& =min(f,g,h)+max(k-x,0)\end{array}$$

最后，我们只需要返回 $f$, $g$, $h$ 中的最小值即可。

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

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

力扣原题 · Doocs 题解来源

2930. 重新排列后包含指定子字符串的字符串数目

中等3 种解法

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

题目、示例与约束

给你一个整数 n 。

如果一个字符串 s 只包含小写英文字母，且 将 s 的字符重新排列后，新字符串包含 子字符串 "leet" ，那么我们称字符串 s 是一个 好 字符串。

比方说：

• 字符串 "lteer" 是好字符串，因为重新排列后可以得到 "leetr" 。
• "letl" 不是好字符串，因为无法重新排列并得到子字符串 "leet" 。

请你返回长度为 n 的好字符串 总 数目。

由于答案可能很大，将答案对 109 + 7 取余 后返回。

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

 

示例 1：

输入：n = 4
输出：12
解释：总共有 12 个字符串重新排列后包含子字符串 "leet" ："eelt" ，"eetl" ，"elet" ，"elte" ，"etel" ，"etle" ，"leet" ，"lete" ，"ltee" ，"teel" ，"tele" 和 "tlee" 。

示例 2：

输入：n = 10
输出：83943898
解释：长度为 10 的字符串重新排列后包含子字符串 "leet" 的方案数为 526083947580 。所以答案为 526083947580 % (109 + 7) = 83943898 。

 

提示：

• 1 <= n <= 105

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

思考

长度为 $n$ 的小写串经重排后须能含 $leet$，即字母表至少 $1$ 个 $l$、 $2$ 个 $e$、 $1$ 个 $t$。直接构造满足计数的串再乘排列会重复。按位填写并记录三者是否已凑齐，状态数为 $n\times 2\times 3\times 2$。

$dfs(i,l,e,t)$ 对剩余长度枚举：放其他字母、 $l$、 $e$ 或 $t$，上界分别截断到 $1,2,1$。 $n\le {10}^5$ 时记忆化次数与状态同阶，再乘常数字母选择。

我们设计一个函数 $dfs(i,l,e,t)$，表示当前剩余字符串长度为 $i$，且已至少有 $l$ 个字符 'l', $e$ 个字符 'e' 和 $t$ 个字符 't'，构成的字符串是一个好字符串的方案数。那么答案为 $dfs(n,0,0,0)$。

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

如果 $i=0$，说明当前字符串已经构造完毕，如果 $l=1$, $e=2$ 且 $t=1$，说明当前字符串是一个好字符串，返回 $1$，否则返回 $0$。

否则，我们可以考虑在当前位置添加除 'l', 'e', 't' 以外的任意一个小写字母，一共有 $23$ 种，那么此时得到的方案数为 $dfs(i-1,l,e,t)\times 23$。

我们也可以考虑在当前位置添加 'l'，此时得到的方案数为 $dfs(i-1,min(1,l+1),e,t)$。同理，添加 'e' 和 't' 的方案数分别为 $dfs(i-1,l,min(2,e+1),t)$ 和 $dfs(i-1,l,e,min(1,t+1))$。累加起来，并对 ${10}^9+7$ 取模，即可得到 $dfs(i,l,e,t)$ 的值。

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

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

func stringCount(n int) int {
	const mod int = 1e9 + 7
	f := make([][2][3][2]int, n+1)
	for i := range f {
		for j := range f[i] {
			for k := range f[i][j] {
				for l := range f[i][j][k] {
					f[i][j][k][l] = -1
				}
			}
		}
	}
	var dfs func(i, l, e, t int) int
	dfs = func(i, l, e, t int) int {
		if i == 0 {
			if l == 1 && e == 2 && t == 1 {
				return 1
			}
			return 0
		}
		if f[i][l][e][t] == -1 {
			a := dfs(i-1, l, e, t) * 23 % mod
			b := dfs(i-1, min(1, l+1), e, t)
			c := dfs(i-1, l, min(2, e+1), t)
			d := dfs(i-1, l, e, min(1, t+1))
			f[i][l][e][t] = (a + b + c + d) % mod
		}
		return f[i][l][e][t]
	}
	return dfs(n, 0, 0, 0)
}

方法二：逆向思维 + 容斥原理 · Go 实现

思考

方法一按长度递推，状态转移次数与 $n$ 成正比，常数尚可但实现偏重。补集更直接：总串数 ${26}^n$ 减去缺 $l$、缺 $t$、或 $e$ 不足两个的串，再用容斥加回交集。

各集合均为「禁用若干字母或限制 $e$ 的个数」，可用快速幂求 ${25}^n$、 ${24}^n$ 以及「恰 $0$ 或 $1$ 个 $e$」的项。 $n$ 很大时比逐步 DP 更短。

我们可以考虑逆向思维，即计算不包含子字符串 "leet" 的字符串数目，然后用总数减去该数目即可。

我们分成以下几种情况：

• 情况 $a$：表示字符串中不包含字符 'l' 的方案数，那么有 $a={25}^n$。
• 情况 $b$：与 $a$ 类似，表示字符串中不包含字符 't' 的方案数，那么有 $b={25}^n$。
• 情况 $c$：表示字符串中不包含字符 'e' 或者只包含一个字符 'e' 的方案数，那么有 $c={25}^n+n\times {25}^{n-1}$。
• 情况 $ab$：表示字符串中不包含字符 'l' 和 't' 的方案数，那么有 $ab={24}^n$。
• 情况 $ac$：表示字符串中不包含字符 'l' 和 'e' 或者只包含一个字符 'e' 的方案数，那么有 $ac={24}^n+n\times {24}^{n-1}$。
• 情况 $bc$：与 $ac$ 类似，表示字符串中不包含字符 't' 和 'e' 或者只包含一个字符 'e' 的方案数，那么有 $bc={24}^n+n\times {24}^{n-1}$。
• 情况 $abc$：表示字符串中不包含字符 'l'、't' 和 'e' 或者只包含一个字符 'e' 的方案数，那么有 $abc={23}^n+n\times {23}^{n-1}$。

那么根据容斥原理，可以得到 $a+b+c-ab-ac-bc+abc$，就是不包含子字符串 "leet" 的字符串数目。

而总数 $tot={26}^n$，所以答案为 $tot-(a+b+c-ab-ac-bc+abc)$，注意要对 ${10}^9+7$ 取模。

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

func stringCount(n int) int {
	const mod int = 1e9 + 7
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	a := qpow(25, n)
	b := a
	c := qpow(25, n) + n*qpow(25, n-1)
	ab := qpow(24, n)
	ac := (qpow(24, n) + n*qpow(24, n-1)) % mod
	bc := ac
	abc := (qpow(23, n) + n*qpow(23, n-1)) % mod
	tot := qpow(26, n)
	return ((tot-(a+b+c-ab-ac-bc+abc))%mod + mod) % mod
}

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

思考

长度为 $n$ 的小写串经重排后须能含 $leet$，即 $l$、 $e$、 $t$ 的个数至少达到 $1$、 $2$、 $1$。按计数直接乘排列会把交叉情形算重。搜索里真正用到的只是截断后的三个计数，共 $2\times 3\times 2$ 种，长度为 $i$ 的方案只由长度为 $i-1$ 的方案转移而来。

按剩余长度递归会形成长度为 $n$ 的调用链。 $n\le {10}^5$ 时调用栈放不下；若再把每一层都放进 C++ 的变长数组，约 $9.6$MB 也会压在栈上。

因此我们只保留相邻两层、每层 $12$ 个状态。空串仅在配额 $(1,2,1)$ 上记 $1$，随后逐个字符追加： $23$ 个其他字母，或受上限约束的 $l$、 $e$、 $t$。 $n$ 个字符之后，状态 $(0,0,0)$ 即为答案。

我们记 $f(i,l,e,t)$ 为长度为 $i$、已经至少含有 $l$ 个 'l'、 $e$ 个 'e' 和 $t$ 个 't' 的字符串方案数。三个计数分别截断到 $1$、 $2$ 和 $1$。答案为 $f(n,0,0,0)$。

当 $i=0$ 时，只有 $f(0,1,2,1)=1$，其余状态均为 $0$。

当 $i\ge 1$ 时，末尾字符可以是除 'l'、'e'、't' 以外的 $23$ 个字母之一，也可以是这三个字母之一：

$$f(i,l,e,t)=23\cdot f(i-1,l,e,t)+f(i-1,min(1,l+1),e,t)+f(i-1,l,min(2,e+1),t)+f(i-1,l,e,min(1,t+1))$$

每一项都对 ${10}^9+7$ 取模。第 $i$ 层只读取第 $i-1$ 层，因此实现中保留两层、每层 $12$ 个状态即可。

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

func stringCount(n int) int {
	const mod int = 1e9 + 7
	var f [2][3][2]int
	f[1][2][1] = 1
	for i := 0; i < n; i++ {
		var g [2][3][2]int
		for l := 0; l < 2; l++ {
			for e := 0; e < 3; e++ {
				for t := 0; t < 2; t++ {
					a := f[l][e][t] * 23
					b := f[min(1, l+1)][e][t]
					c := f[l][min(2, e+1)][t]
					d := f[l][e][min(1, t+1)]
					g[l][e][t] = (a + b + c + d) % mod
				}
			}
		}
		f = g
	}
	return f[0][0][0]
}

力扣原题 · Doocs 题解来源

2944. 购买水果需要的最少金币数

中等3 种解法

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

题目、示例与约束

给你一个 下标从 0 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i + 1 个水果需要花费的金币数目。

水果超市有如下促销活动：

• 如果你花费 prices[i] 购买了下标为 i + 1 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。

注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j - 1] 个金币去购买它以获得它的奖励。

请你返回获得所有水果所需要的 最少 金币数。

 

示例 1：

输入：prices = [3,1,2]

输出：4

解释：

• 用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
• 用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。
• 免费获得第 3 个水果。

请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

示例 2：

输入：prices = [1,10,1,1]

输出：2

解释：

• 用 prices[0] = 1 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
• 免费获得第 2 个水果。
• 用 prices[2] = 1 个金币购买第 3 个水果，你可以免费获得第 4 个水果。
• 免费获得第 4 个水果。

示例 3：

输入：prices = [26,18,6,12,49,7,45,45]

输出：39

解释：

• 用 prices[0] = 26 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
• 免费获得第 2 个水果。
• 用 prices[2] = 6 个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。
• 免费获得第 4 个水果。
• 免费获得第 5 个水果。
• 用 prices[5] = 7 个金币购买第 6 个水果，你可以免费获得第 7 和 第 8 个水果。
• 免费获得第 7 个水果。
• 免费获得第 8 个水果。

请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

 

提示：

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

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

思考

买下标 $i$（从 $1$ 计）可免费获得其后 $i$ 个水果，求买完全部的最少代价。 $n\le 1000$，从位置 $i$ 出发，下一步必须在 $i+1\dots 2i+1$ 中选一个再买，区间长度 $O(i)$。

$dfs(i)$ 记忆化该后继最小值；当 $2i\ge n$ 时买当前即可覆盖尾部。从 $1$ 调用。

我们定义一个函数 $\mathit{\text{dfs}}(i)$，表示从第 $i$ 个水果开始购买所有水果所需要的最少金币数。那么答案就是 $\mathit{\text{dfs}}(1)$。

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

• 如果 $i\times 2\ge n$，说明只要买第 $i-1$ 个水果即可，剩余的水果都可以免费获得，所以返回 $\mathit{\text{prices}}[i-1]$。
• 否则，我们可以购买水果 $i$，然后在接下来的 $i+1$ 到 $2i+1$ 个水果中选择一个水果 $j$ 开始购买，那么 $\mathit{\text{dfs}}(i)=\mathit{\text{prices}}[i-1]+\underset{i+1\le j\le 2i+1}{min}\mathit{\text{dfs}}(j)$。

为了避免重复计算，我们使用记忆化搜索的方法，将已经计算过的结果保存起来，下次遇到相同的情况时，直接返回结果即可。

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

func minimumCoins(prices []int) int {
	n := len(prices)
	f := make([]int, n+1)
	var dfs func(int) int
	dfs = func(i int) int {
		if i*2 >= n {
			return prices[i-1]
		}
		if f[i] == 0 {
			f[i] = 1 << 30
			for j := i + 1; j <= i*2+1; j++ {
				f[i] = min(f[i], dfs(j)+prices[i-1])
			}
		}
		return f[i]
	}
	return dfs(1)
}

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

思考

记忆化按递归展开，改成自底向上后语义不变： $f[i]$ 仍是从 $i$ 买到结尾的最少金币，转移枚举 $j\in [i+1,2i+1]$。从后往前填表，避免递归栈，并与方法一对照。

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

与方法一类似，我们定义 $f[i]$ 表示从第 $i$ 个水果开始购买所有水果所需要的最少金币数。那么答案就是 $f[1]$。

状态转移方程为 $f[i]=\underset{i+1\le j\le 2i+1}{min}f[j]+\mathit{\text{prices}}[i-1]$。

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

在代码实现上，我们可以直接使用 $\mathit{\text{prices}}$ 数组来存储 $f$ 数组，那么空间复杂度可以优化到 $O(1)$。

func minimumCoins(prices []int) int {
	for i := (len(prices) - 1) / 2; i > 0; i-- {
		prices[i-1] += slices.Min(prices[i : i*2+1])
	}
	return prices[0]
}

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

思考

方法二对每个 $i$ 线性求一段 $f[j]$ 的最小，总时间 $O(n^2)$，在 $n=1000$ 尚可。观察到 $i$ 减小时窗口 $[i+1,2i+1]$ 的右端收缩，可用单调队列维护候选下标。

从后往前：弹出超出 $2i+1$ 的队首，用队首更新 $prices[i-1]$，再按 $prices$ 值保持队列递增。原地改写后 $prices[0]$ 即为答案。

我们观察方法二中的状态转移方程，可以发现，对于每个 $i$，我们需要求出 $f[i+1],f[i+2],\cdots ,f[2i+1]$ 的最小值，并且随着 $i$ 的减小，这些值的范围也在减小。这实际上是求一个单调收窄的滑动窗口的最小值，我们可以使用单调队列来优化。

我们从后往前计算，维护一个单调递增的队列 $q$，队列中存储的是下标。如果 $q$ 的队首元素大于 $i\times 2+1$，说明 $i$ 之后的元素都不会被用到，所以我们将队首元素出队。如果 $i$ 不大于 $(n-1)/2$，那么我们可以将 $\mathit{\text{prices}}[q[0]-1]$ 加到 $\mathit{\text{prices}}[i-1]$ 上，然后将 $i$ 加入队尾。如果 $q$ 的队尾元素对应的水果价格大于等于 $\mathit{\text{prices}}[i-1]$，那么我们将队尾元素出队，直到队尾元素对应的水果价格小于 $\mathit{\text{prices}}[i-1]$ 或者队列为空，然后将 $i$ 加入队尾。

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

func minimumCoins(prices []int) int {
	n := len(prices)
	q := Deque{}
	for i := n; i > 0; i-- {
		for q.Size() > 0 && q.Front() > i*2+1 {
			q.PopFront()
		}
		if i <= (n-1)/2 {
			prices[i-1] += prices[q.Front()-1]
		}
		for q.Size() > 0 && prices[q.Back()-1] >= prices[i-1] {
			q.PopBack()
		}
		q.PushBack(i)
	}
	return prices[0]
}

// template
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 题解来源

2945. 找到最大非递减数组的长度

困难1 种解法

标签：栈、队列、数组、二分查找、动态规划、前缀和、单调队列、单调栈

题目、示例与约束

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

你可以执行任意次操作。每次操作中，你需要选择一个 子数组 ，并将这个子数组用它所包含元素的 和 替换。比方说，给定数组是 [1,3,5,6] ，你可以选择子数组 [3,5] ，用子数组的和 8 替换掉子数组，然后数组会变为 [1,8,6] 。

请你返回执行任意次操作以后，可以得到的 最长非递减 数组的长度。

子数组 指的是一个数组中一段连续 非空 的元素序列。

 

示例 1：

输入：nums = [5,2,2]
输出：1
解释：这个长度为 3 的数组不是非递减的。
我们有 2 种方案使数组长度为 2 。
第一种，选择子数组 [2,2] ，对数组执行操作后得到 [5,4] 。
第二种，选择子数组 [5,2] ，对数组执行操作后得到 [7,2] 。
这两种方案中，数组最后都不是 非递减 的，所以不是可行的答案。
如果我们选择子数组 [5,2,2] ，并将它替换为 [9] ，数组变成非递减的。
所以答案为 1 。

示例 2：

输入：nums = [1,2,3,4]
输出：4
解释：数组已经是非递减的。所以答案为 4 。

示例 3：

输入：nums = [4,3,2,6]
输出：3
解释：将 [3,2] 替换为 [5] ，得到数组 [4,5,6] ，它是非递减的。
最大可能的答案为 3 。

 

提示：

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

方法一 · Go 实现

思考

每次把一段相邻元素合并为它们的和，最终数组须非递减，求最多段数。 $n\le {10}^5$，不能枚举所有分割。设 $f[i]$ 为前 $i$ 个元素的最多段数，且最后一段之和应尽量小以便后续衔接；记该最后一段的起点相关信息于 $pre$。

前缀和 $s$ 上，下一段之和至少为上一段之和，故用二分查找最小的 $j$ 满足 $s[j]-s[i]\ge s[i]-s[pre[i]]$，并允许 $pre$ 取前缀最大以继承更优起点。一次扫描加二分得到 $f[n]$。

func findMaximumLength(nums []int) int {
	n := len(nums)
	f := make([]int, n+1)
	pre := make([]int, n+2)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	for i := 1; i <= n; i++ {
		pre[i] = max(pre[i], pre[i-1])
		f[i] = f[pre[i]] + 1
		j := sort.SearchInts(s, s[i]*2-s[pre[i]])
		pre[j] = max(pre[j], i)
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

2957. 消除相邻近似相等字符

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的字符串 word 。

一次操作中，你可以选择 word 中任意一个下标 i ，将 word[i] 修改成任意一个小写英文字母。

请你返回消除 word 中所有相邻 近似相等 字符的 最少 操作次数。

两个字符 a 和 b 如果满足 a == b 或者 a 和 b 在字母表中是相邻的，那么我们称它们是 近似相等 字符。

 

示例 1：

输入：word = "aaaaa"
输出：2
解释：我们将 word 变为 "acaca" ，该字符串没有相邻近似相等字符。
消除 word 中所有相邻近似相等字符最少需要 2 次操作。

示例 2：

输入：word = "abddez"
输出：2
解释：我们将 word 变为 "ybdoez" ，该字符串没有相邻近似相等字符。
消除 word 中所有相邻近似相等字符最少需要 2 次操作。

示例 3：

输入：word = "zyxyxyz"
输出：3
解释：我们将 word 变为 "zaxaxaz" ，该字符串没有相邻近似相等字符。
消除 word 中所有相邻近似相等字符最少需要 3 次操作

 

提示：

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

方法一：贪心 · Go 实现

思考

相邻字母码差小于 $2$ 则须改其中一个。改当前位后，它与下一位的冲突被隔开，故贪心改 $word[i]$ 并跳过 $i+1$ 不会更差。 $n\le 100$，从下标 $1$ 扫描即可。

无需真正改写字符，只累计次数。

我们从下标 $1$ 开始遍历字符串 $word$，如果 $word[i]$ 和 $word[i-1]$ 相邻近似相等，那么我们就贪心地将 $word[i]$ 替换成一个与 $word[i-1]$ 和 $word[i+1]$ 都不相等的字符（可以不执行替换操作，记录操作次数即可）。然后，我们跳过 $word[i+1]$，继续遍历字符串 $word$。

最后，我们返回记录的操作次数。

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

func removeAlmostEqualCharacters(word string) (ans int) {
	for i := 1; i < len(word); i++ {
		if abs(int(word[i])-int(word[i-1])) < 2 {
			ans++
			i++
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

2969. 购买水果需要的最少金币数 II 🔒

困难1 种解法

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

题目、示例与约束

你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。

给你一个 下标从 1 开始 的数组 prices，其中 prices[i] 表示你购买第 i 个水果所需的硬币数量。

水果市场有以下优惠活动：

• 如果你用 prices[i] 个硬币购买第 i 个水果， 那么接下来的 i 个水果你都可以免费获得。

请注意 即使你 可以 免费获得第 j 个水果，你仍然可以用 prices[j] 个硬币来购买它，以获取新的优惠。

返回 获得所有水果所需的 最小 硬币数量。

 

示例 1：

输入：prices = [3,1,2]
输出：4
解释：你可以按以下方式获取水果：
- 用3个硬币购买第1个水果，并且可以免费获得第2个水果。
- 用1个硬币购买第2个水果，并且可以免费获得第3个水果。
- 免费获得第三个水果。
请注意，即使你可以免费获得第2个水果，你还是购买了它，因为这是更优的选择。
可以证明4是获取所有水果所需的最小硬币数量。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：你可以按以下方式获取水果：
- 用1个硬币购买第1个水果，并且可以免费获得第2个水果。
- 免费获得第2个水果。
- 用1个硬币购买第3个水果，并且可以免费获得第4个水果。
- 免费获得第4个水果。
可以证明2是获取所有水果所需的最小硬币数量。

 

提示：

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

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

思考

转移与「水果 I」相同： $f[i]=prices[i-1]+\underset{i+1\le j\le 2i+1}{min}f[j]$，但 $n$ 达到 ${10}^5$，双重循环不可行。窗口右端随 $i$ 减小而收缩，单调队列可 $O(1)$ 取最小。

从后往前弹出超过 $2i+1$ 的下标，用队首更新 $prices[i-1]$，再按代价保持递增。原地滚动后 $prices[0]$ 即为答案。

我们定义 $f[i]$ 表示从第 $i$ 个水果开始购买所有水果所需要的最少金币数。那么答案就是 $f[1]$。

状态转移方程为 $f[i]=\underset{i+1\le j\le 2i+1}{min}f[j]+prices[i-1]$。

在实现上，我们从后往前计算，并且可以直接在数组 $prices$ 上进行状态转移，这样可以节省空间。

以上做法的时间复杂度为 $O(n^2)$，由于本题 $n$ 的规模达到 ${10}^5$，因此会超时。

我们观察状态转移方程，可以发现，对于每个 $i$，我们需要求出 $f[i+1],f[i+2],\cdots ,f[2i+1]$ 的最小值，并且随着 $i$ 的减小，这些值的范围也在减小。这实际上是求一个单调收窄的滑动窗口的最小值，我们可以使用单调队列来优化。

我们从后往前计算，维护一个单调递增的队列 $q$，队列中存储的是下标。如果 $q$ 的队首元素大于 $i\times 2+1$，说明 $i$ 之后的元素都不会被用到，所以我们将队首元素出队。如果 $i$ 不大于 $(n-1)/2$，那么我们可以将 $prices[q[0]-1]$ 加到 $prices[i-1]$ 上，然后将 $i$ 加入队尾。如果 $q$ 的队尾元素对应的水果价格大于等于 $prices[i-1]$，那么我们将队尾元素出队，直到队尾元素对应的水果价格小于 $prices[i-1]$ 或者队列为空，然后将 $i$ 加入队尾。

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

func minimumCoins(prices []int) int {
	n := len(prices)
	q := Deque{}
	for i := n; i > 0; i-- {
		for q.Size() > 0 && q.Front() > i*2+1 {
			q.PopFront()
		}
		if i <= (n-1)/2 {
			prices[i-1] += prices[q.Front()-1]
		}
		for q.Size() > 0 && prices[q.Back()-1] >= prices[i-1] {
			q.PopBack()
		}
		q.PushBack(i)
	}
	return prices[0]
}

// template
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 题解来源

2979. 最贵的无法购买的商品 🔒

中等1 种解法

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

题目、示例与约束

给定两个 不同的质数 primeOne 和 primeTwo。

Alice 和 Bob 正在逛市场。该市场有 无数种 商品，对于 任何 正整数 x，都存在一个价格为 x 的物品。Alice 想从市场里买一些东西送给 Bob。她有 无数个 面值为 primeOne 和 primeTwo 的硬币。她想知道她 无法 用她拥有的硬币购买的 最贵 商品的价格。

返回 Alice 无法买给 Bob 的 最贵 商品的价格。

 

示例 1:

输入：primeOne = 2, primeTwo = 5
输出：3
解释：无法购买的商品的价格有 [1,3]。所有价格大于 3 的商品都可以通过组合使用面额为 2 和 5 的硬币购买。

示例 2:

输入：primeOne = 5, primeTwo = 7
输出：23
解释：无法购买的商品的价格有 [1,2,3,4,6,8,9,11,13,16,18,23]。所有价格大于 23 的商品都可以购买。

 

提示：

• 1 < primeOne, primeTwo < 104
• primeOne, primeTwo 都是质数。
• primeOne * primeTwo < 105

方法一：Chicken McNugget 定理 · Go 实现

思考

两种面值均为质数因而互质，能表示的金额是非负整数组合 $a\cdot primeOne+b\cdot primeTwo$。Chicken McNugget 定理给出最大不能表示数为 $ab-a-b$，无需背包。

直接返回乘积减两质数。

根据 Chicken McNugget 定理，两个互质的正整数 $a$ 和 $b$，最大不能表示的数为 $ab-a-b$。

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

func mostExpensiveItem(primeOne int, primeTwo int) int {
	return primeOne*primeTwo - primeOne - primeTwo
}

力扣原题 · Doocs 题解来源

2992. 自整除排列的数量 🔒

中等2 种解法

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

题目、示例与约束

给定一个整数 n，返回 下标从 1 开始 的数组 nums = [1, 2, ..., n]的 可能的排列数量，使其满足 自整除 条件。

如果对于每个 1 <= i <= n，满足 gcd(a[i], i) == 1，数组 nums 就是 自整除 的。

数组的 排列 是对数组元素的重新排序，例如，下面是数组 [1, 2, 3] 的所有排列：

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

 

示例 1：

输入：n = 1
输出：1
解释：数组 [1] 只有一个排列，它是自整除的。

示例 2：

输入：n = 2
输出：1
解释：数组 [1,2] 有 2 个排列，但只有其中一个是自整除的：
nums = [1,2]：这不是自整除的，因为 gcd(nums[2], 2) != 1。
nums = [2,1]：这是自整除的，因为 gcd(nums[1], 1) == 1 并且 gcd(nums[2], 2) == 1。

示例 3：

输入：n = 3
输出：3
解释：数组 [1,2,3] 有 3 个自整除的排列：[1,2,3]、[2,1,3]、[3,2,1]。
其他 3 个排列不能满足自整除条件。因此答案是 3。

 

提示：

• 1 <= n <= 12

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

思考

排列满足 $gcd(i,per{m}_i)=1$。 $n$ 很小，可用二进制 $mask$ 记录已用数字。 $dfs(mask)$ 的下一个位置是 $bit\mathrm{\_}count+1$，枚举未用且与位置互质的 $j$。

记忆化状态 $2^n$，每位再乘 $n$，可接受。

我们可以用一个二进制数 $mask$ 来表示当前排列的状态，其中第 $i$ 位为 $1$ 表示数字 $i$ 已经被使用，为 $0$ 表示数字 $i$ 还未被使用。

那么，我们设计一个函数 $dfs(mask)$，表示从当前排列的状态 $mask$ 开始，能够构造出的满足题目要求的排列的数量。答案即为 $dfs(0)$。

我们可以用记忆化搜索的方法来计算 $dfs(mask)$ 的值。

在计算 $dfs(mask)$ 的过程中，我们用 $i$ 表示当前要加入排列的是第几个数字，如果 $i>n$，说明排列已经构造完毕，我们可以返回 $1$。

否则，我们枚举当前排列中还未被使用的数字 $j$，如果 $i$ 和 $j$ 满足题目要求，那么我们就可以将 $j$ 加入排列中，此时状态变为 $mask\mid 2^j$，其中 $|$ 表示按位或运算。由于 $j$ 已经被使用，因此我们需要递归计算 $dfs(mask\mid 2^j)$ 的值，并将其累加到 $dfs(mask)$ 上。

最终，我们可以得到 $dfs(0)$ 的值，即为答案。

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

func selfDivisiblePermutationCount(n int) int {
	f := make([]int, 1<<(n+1))
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(mask int) int {
		if f[mask] != -1 {
			return f[mask]
		}
		i := bits.OnesCount(uint(mask)) + 1
		if i > n {
			return 1
		}
		f[mask] = 0
		for j := 1; j <= n; j++ {
			if mask>>j&1 == 0 && gcd(i, j) == 1 {
				f[mask] += dfs(mask | 1<<j)
			}
		}
		return f[mask]
	}
	return dfs(0)
}

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

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

思考

方法一按「已用集合」递归。改成 $f[mask]$ 表示达到该集合的方案，从子集差一位转移，需保证新数字与其位置互质。初始 $f[0]=1$，答案 $f[2^n-1]$。

与搜索相比只是迭代顺序不同，便于去掉递归。

我们可以将方法一中的记忆化搜索改写为动态规划的形式，定义 $f[mask]$ 表示当前排列的状态为 $mask$，且满足题目要求的排列的数量。初始时 $f[0]=1$，其余值均为 $0$。

我们在 $[0,2^n)$ 的范围内枚举 $mask$，对于每个 $mask$，我们用 $i$ 表示当前最后一个加入排列的是第几个数字，然后我们枚举当前排列中最后一个加入的数字 $j$，如果 $i$ 和 $j$ 满足题目要求，那么状态 $f[mask]$ 就可以从状态 $f[mask\oplus 2^{(}j-1)]$ 转移而来，其中 $\oplus$ 表示按位异或运算。我们将所有转移得到的状态 $f[mask\oplus 2^{(}j-1)]$ 的值累加到 $f[mask]$ 上，即为 $f[mask]$ 的值。

最终，我们可以得到 $f[2^n-1]$ 的值，即为答案。

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

func selfDivisiblePermutationCount(n int) int {
	f := make([]int, 1<<n)
	f[0] = 1
	for mask := 0; mask < 1<<n; mask++ {
		i := bits.OnesCount(uint(mask))
		for j := 1; j <= n; j++ {
			if mask>>(j-1)&1 == 1 && gcd(i, j) == 1 {
				f[mask] += f[mask^(1<<(j-1))]
			}
		}
	}
	return f[(1<<n)-1]
}

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

力扣原题 · Doocs 题解来源

2998. 使 X 和 Y 相等的最少操作次数

中等1 种解法

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

题目、示例与约束

给你两个正整数 x 和 y 。

一次操作中，你可以执行以下四种操作之一：

1. 如果 x 是 11 的倍数，将 x 除以 11 。
2. 如果 x 是 5 的倍数，将 x 除以 5 。
3. 将 x 减 1 。
4. 将 x 加 1 。

请你返回让 x 和 y 相等的 最少 操作次数。

 

示例 1：

输入：x = 26, y = 1
输出：3
解释：我们可以通过以下操作将 26 变为 1 ：
1. 将 x 减 1
2. 将 x 除以 5
3. 将 x 除以 5
将 26 变为 1 最少需要 3 次操作。

示例 2：

输入：x = 54, y = 2
输出：4
解释：我们可以通过以下操作将 54 变为 2 ：
1. 将 x 加 1
2. 将 x 除以 11
3. 将 x 除以 5
4. 将 x 加 1
将 54 变为 2 最少需要 4 次操作。

示例 3：

输入：x = 25, y = 30
输出：5
解释：我们可以通过以下操作将 25 变为 30 ：
1. 将 x 加 1
2. 将 x 加 1
3. 将 x 加 1
4. 将 x 加 1
5. 将 x 加 1
将 25 变为 30 最少需要 5 次操作。

 

提示：

• 1 <= x, y <= 104

方法一 · Go 实现

思考

操作含 $+1/-1$ 以及在整除时 $/5$、 $/11$。 $x,y\le {10}^4$，若 $y\ge x$ 则只能连减，代价 $y-x$。否则除法能更快逼近，但未必已整除，可先加减余数或补到下一个倍数再除。

$dfs(x)$ 比较「一路减到 $y$」与四种「对齐后除 $5$ 或 $11$」的后续。记忆化避免重复状态；搜索只向变小的方向，保证结束。

func minimumOperationsToMakeEqual(x int, y int) int {
	f := map[int]int{}
	var dfs func(int) int
	dfs = func(x int) int {
		if y >= x {
			return y - x
		}
		if v, ok := f[x]; ok {
			return v
		}
		a := x%5 + 1 + dfs(x/5)
		b := 5 - x%5 + 1 + dfs(x/5+1)
		c := x%11 + 1 + dfs(x/11)
		d := 11 - x%11 + 1 + dfs(x/11+1)
		f[x] = min(x-y, a, b, c, d)
		return f[x]
	}
	return dfs(x)
}

力扣原题 · Doocs 题解来源

2999. 统计强大整数的数目

困难1 种解法

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

题目、示例与约束

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。

如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

 

示例 1：

输入：start = 1, finish = 6000, limit = 4, s = "124"
输出：5
解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。

示例 2：

输入：start = 15, finish = 215, limit = 6, s = "10"
输出：2
解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。

示例 3：

输入：start = 1000, finish = 2000, limit = 4, s = "3000"
输出：0
解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。

 

提示：

• 1 <= start <= finish <= 1015
• 1 <= limit <= 9
• 1 <= s.length <= floor(log10(finish)) + 1
• s 数位中每个数字都小于等于 limit 。
• s 不包含任何前导 0 。

方法一：数位 DP · Go 实现

思考

统计 $[start,finish]$ 中、每位 $\le limit$ 且以 $s$ 为后缀的个数。区间计数化为 $f(finish)-f(start-1)$。数位 DP 按位填写，高位受 $limit$ 与上界紧约束，低 $|s|$ 位必须匹配 $s$（紧约束时还须 $s\le$ 上界剩余）。

$t$ 比 $s$ 短则方案为 $0$。记忆化 $(pos,lim)$ 即可，上界长度不超过 $16$。

这道题实际上是求在给定区间 $[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,\mathit{\text{finish}}]$ 中满足条件的数的个数，然后减去 $[1,\mathit{\text{start}}-1]$ 中满足条件的数的个数，即可得到答案。

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

基本步骤如下：

1. 先将 $\mathit{\text{start}}$ 和 $\mathit{\text{finish}}$ 转化为字符串，方便后续的数位 DP。
2. 设计一个函数 $\mathit{\text{dfs}}(\mathit{\text{pos}},\mathit{\text{lim}})$，表示从第 $\mathit{\text{pos}}$ 位开始搜索，当前的限制条件为 $\mathit{\text{lim}}$。
3. 如果最大的数字位数小于 $\mathit{\text{s}}$ 的长度，返回 0。
4. 如果当前剩余的数字位数等于 $\mathit{\text{s}}$ 的长度，判断当前的数字是否满足条件，返回 1 或 0。
5. 否则，我们计算当前位的上限 $\mathit{\text{up}}=min(\mathit{\text{lim}}?\mathit{\text{t}}[\mathit{\text{pos}}]:9,\mathit{\text{limit}})$。然后遍历当前位的数字 $i$，从 0 到 $\mathit{\text{up}}$，递归调用 $\mathit{\text{dfs}}(\mathit{\text{pos}}+1,\mathit{\text{lim}}\mathrm{\&}\mathrm{\&}i==\mathit{\text{t}}[\mathit{\text{pos}}])$，将结果累加到答案中。
6. 如果当前的 $\mathit{\text{lim}}$ 为 false，则将当前的答案存入缓存中，避免重复计算。
7. 最后返回答案。

答案为区间 $[1,\mathit{\text{finish}}]$ 中满足条件的数的个数减去区间 $[1,\mathit{\text{start}}-1]$ 中满足条件的数的个数。

时间复杂度 $O(\log M\times D)$，空间复杂度 $O(\log M)$，其中 $M$ 为数字的上限，而 $D=10$。

func numberOfPowerfulInt(start, finish int64, limit int, s string) int64 {
	t := strconv.FormatInt(start-1, 10)
	f := make([]int64, 20)
	for i := range f {
		f[i] = -1
	}

	var dfs func(int, bool) int64
	dfs = func(pos int, lim bool) int64 {
		if len(t) < len(s) {
			return 0
		}
		if !lim && f[pos] != -1 {
			return f[pos]
		}
		if len(t)-pos == len(s) {
			if lim {
				if s <= t[pos:] {
					return 1
				}
				return 0
			}
			return 1
		}

		ans := int64(0)
		up := 9
		if lim {
			up = int(t[pos] - '0')
		}
		up = min(up, limit)
		for i := 0; i <= up; i++ {
			ans += dfs(pos+1, lim && i == int(t[pos]-'0'))
		}
		if !lim {
			f[pos] = ans
		}
		return ans
	}

	a := dfs(0, true)
	t = strconv.FormatInt(finish, 10)
	for i := range f {
		f[i] = -1
	}
	b := dfs(0, true)
	return b - a
}

力扣原题 · Doocs 题解来源