LeetCode Go · 动态规划（13）

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

来源与许可

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

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

2495. 乘积为偶数的子数组数 🔒

中等1 种解法

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

题目、示例与约束

给定一个整数数组 nums，返回具有偶数乘积的 nums 子数组的数目。

 

示例 1:

输入: nums = [9,6,7,13]
输出: 6
解释: 有6个子数组的乘积是偶数:
- nums[0..1] = 9 * 6 = 54.
- nums[0..2] = 9 * 6 * 7 = 378.
- nums[0..3] = 9 * 6 * 7 * 13 = 4914.
- nums[1..1] = 6.
- nums[1..2] = 6 * 7 = 42.
- nums[1..3] = 6 * 7 * 13 = 546.

示例 2:

输入: nums = [7,3,5]
输出: 0
解释: 没有乘积是偶数的子数组

 

提示:

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

方法一：一次遍历 · Go 实现

思考

子数组乘积为偶数当且仅当其中含至少一个偶数。以 $i$ 为右端时，左端可取最近偶数及更左的任意位置，共 $last+1$ 个（无偶数则为 $0$）。扫一遍维护 $last$。

我们知道，一个子数组的乘积为偶数，当且仅当该子数组中至少有一个偶数。

因此，我们可以遍历数组，记录最近一个偶数的下标 last，则以当前元素结尾的子数组中，乘积为偶数的子数组个数为 last + 1，累加到结果中即可。

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

func evenProduct(nums []int) int64 {
	ans, last := 0, -1
	for i, v := range nums {
		if v%2 == 0 {
			last = i
		}
		ans += last + 1
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2501. 数组中最长的方波

中等2 种解法

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

题目、示例与约束

给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：

• 子序列的长度至少为 2 ，并且
• 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。

返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。

子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。

 

示例 1 ：

输入：nums = [4,3,6,16,8,2]
输出：3
解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。
- 4 = 2 * 2.
- 16 = 4 * 4.
因此，[4,16,2] 是一个方波.
可以证明长度为 4 的子序列都不是方波。

示例 2 ：

输入：nums = [2,3,5,6,7]
输出：-1
解释：nums 不存在方波，所以返回 -1 。

 

提示：

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

方法一：哈希表 + 枚举 · Go 实现

思考

方波要求相邻项满足后者为前者的平方。枚举全部子序列在 $n\le {10}^5$ 下不可行；即便只检查有序链，若每次在数组中线性查找后继，仍会浪费有序性之外的结构。

注意到后继由 $x\mapsto x^2$ 唯一确定，只需判断平方是否仍在数组中。将 $\mathit{\text{nums}}$ 放入集合后，从每个起点反复平方即可得到该链长度。平方增长极快，链长仅为 $O(\log \log M)$，故总时间可接受。长度不超过 $1$ 时按题意记为 $-1$。

我们先用哈希表记录数组中的所有元素，然后枚举数组中的每个元素作为子序列的第一个元素，将该元素不断平方，并判断平方后的结果是否在哈希表中，如果在，则将平方后的结果作为下一个元素，继续判断，直到平方后的结果不在哈希表中，此时判断子序列的长度是否大于 $1$，如果是，则更新答案。

时间复杂度 $O(n\times \log \log M)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度，而 $M$ 为数组 $\mathit{\text{nums}}$ 中的元素的最大值。

func longestSquareStreak(nums []int) int {
	s := map[int]bool{}
	for _, x := range nums {
		s[x] = true
	}
	ans := -1
	for x := range s {
		t := 0
		for s[x] {
			x *= x
			t++
		}
		if t > 1 {
			ans = max(ans, t)
		}
	}
	return ans
}

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

思考

方法一从每个起点独立延伸，若两条链共享后缀（例如 $2,4,16$ 与 $4,16$），则会重复计算。

以 $\mathit{\text{dfs}}(x)$ 表示从 $x$ 出发的方波长度，转移为 $1+\mathit{\text{dfs}}(x^2)$，不在集合中则返回 $0$。记忆化后每个值只算一次，时间降为线性。答案取所有起点的最大值，不足 $2$ 则返回 $-1$。

与方法一类似，我们先用哈希表记录数组中的所有元素。然后设计一个函数 $\mathit{\text{dfs}}(x)$，表示以 $x$ 为第一个元素的方波的长度。那么答案就是 $max(\mathit{\text{dfs}}(x))$，其中 $x$ 为数组 $\mathit{\text{nums}}$ 中的元素。

函数 $\mathit{\text{dfs}}(x)$ 的计算过程如下：

• 如果 $x$ 不在哈希表中，则返回 $0$。
• 否则，返回 $1+\mathit{\text{dfs}}(x^2)$。

过程中我们可以使用记忆化搜索，即使用哈希表记录函数 $\mathit{\text{dfs}}(x)$ 的值，避免重复计算。

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

func longestSquareStreak(nums []int) (ans int) {
	s := map[int]bool{}
	for _, x := range nums {
		s[x] = true
	}
	f := map[int]int{}
	var dfs func(int) int
	dfs = func(x int) int {
		if !s[x] {
			return 0
		}
		if v, ok := f[x]; ok {
			return v
		}
		f[x] = 1 + dfs(x*x)
		return f[x]
	}
	for x := range s {
		if t := dfs(x); ans < t {
			ans = t
		}
	}
	if ans < 2 {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2510. 检查是否有路径经过相同数量的 0 和 1 🔒

中等1 种解法

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

题目、示例与约束

给定一个 下标从 0 开始 的 m x n 的 二进制 矩阵 grid ，从坐标为 (row, col) 的元素可以向右走 (row, col+1) 或向下走 (row+1, col) 。

返回一个布尔值，表示从 (0, 0) 出发是否存在一条路径，经过 相同 数量的 0 和 1，到达终点 (m-1, n-1) 。如果存在这样的路径返回 true ，否则返回 false 。

 

示例 1 ：

输入：grid = [[0,1,0,0],[0,1,0,0],[1,0,1,0]]
输出：true
解释：以上图中用蓝色标记的路径是一个有效的路径，因为路径上有 3 个值为 1 的单元格和 3 个值为 0 的单元格。由于存在一个有效的路径，因此返回 true 。

示例 2 ：

输入：grid = [[1,1,0],[0,0,1],[1,0,0]]
输出：false
解释：这个网格中没有一条路径经过相等数量的0和1。

 

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 100
• grid[i][j] 不是 0 就是 1 。

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

思考

从左上走到右下只能向右或向下，路径长度固定为 $m+n-1$。若该长度为奇数，则 $0$ 与 $1$ 的个数不可能相等，直接否定。 $m,n\le 100$，枚举全部路径数量过大。

记目标为各出现 $s=(m+n-1)/2$ 次。状态 $(i,j,k)$ 表示走到 $(i,j)$ 且路径上 $1$ 的个数为 $k$。若 $k$ 或 $0$ 的个数已超过 $s$ 则可剪枝。记忆化后状态量为 $O(mn(m+n))$。

根据题目描述我们知道，从左上角到右下角的路径上 $0$ 的个数和 $1$ 的个数相等，个数总和为 $m+n-1$，即 $0$ 的个数和 $1$ 的个数都为 $(m+n-1)/2$。

因此我们可以使用记忆化搜索，从左上角开始，向右或向下移动，直到到达右下角，判断路径上 $0$ 的个数和 $1$ 的个数是否相等即可。

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

func isThereAPath(grid [][]int) bool {
	m, n := len(grid), len(grid[0])
	s := m + n - 1
	if s%2 == 1 {
		return false
	}
	s >>= 1
	f := [100][100][200]int{}
	var dfs func(i, j, k int) bool
	dfs = func(i, j, k int) bool {
		if i >= m || j >= n {
			return false
		}
		k += grid[i][j]
		if f[i][j][k] != 0 {
			return f[i][j][k] == 1
		}
		f[i][j][k] = 2
		if k > s || i+j+1-k > s {
			return false
		}
		if i == m-1 && j == n-1 {
			return k == s
		}
		res := dfs(i+1, j, k) || dfs(i, j+1, k)
		if res {
			f[i][j][k] = 1
		}
		return res
	}
	return dfs(0, 0, 0)
}

力扣原题 · Doocs 题解来源

2518. 好分区的数目

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个正整数数组 nums 和一个整数 k 。

分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。

返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。

如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。

 

示例 1：

输入：nums = [1,2,3,4], k = 4
输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。

示例 2：

输入：nums = [3,3,3], k = 4
输出：0
解释：数组中不存在好分区。

示例 3：

输入：nums = [6,6], k = 2
输出：2
解释：可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。

 

提示：

• 1 <= nums.length, k <= 1000
• 1 <= nums[i] <= 109

方法一：逆向思维 + 动态规划 · Go 实现

思考

把数组分成两个子序列（每个元素入且只入一侧），要求两侧元素和都不小于 $k$。全部 $2^n$ 种分法在 $n\le {10}^3$、 $k\le {10}^3$ 时不能直接枚举；若某一侧和已经小于 $k$，则该分法不合法。

若总和不足 $2k$，两侧不可能同时达标，答案为 $0$。否则先算全部 $2^n$ 个划分，再减去“某一侧和小于 $k$”的坏划分。坏划分对应选出一个和小于 $k$ 的子集作为其中一侧，这是容量为 $k-1$ 的 $0$-$1$ 背包；每一侧都可扮演“小和”角色，故坏方案数为子集数的两倍。

对于一个长度为 $n$ 的数组 nums，每个元素都可以选择放入第一个分区或第二个分区，因此一共有 $2^n$ 种分区方式。每一种分区方式，得到的结果可以是“好分区”或者“坏分区”，题目要我们求“好分区”的个数，我们可以转换为求“坏分区”的个数。那么“好分区”的个数就是 $2^n$ 减去“坏分区”的个数。

“坏分区”实际上就是从数组 nums 中选出若干个元素，使得这若干个元素之和不超过 $k$。这可以通过动态规划（0-1 背包问题）来求解。

我们用 $f[i][j]$ 表示从数组 nums 的前 $i$ 个元素中选出若干个元素，使得这若干个元素之和为 $j$ 的方案数。那么 $f[i][j]$ 的状态转移方程为：

$$f[i][j]=\{\begin{array}{rlr}& f[i-1][j]& \mathit{\text{如果不选第 }}i\mathit{\text{ 个元素}}\\ & f[i-1][j-nums[i-1]]& \mathit{\text{如果选第 }}i\mathit{\text{ 个元素}}\end{array}$$

那么“坏分区”的个数就是 $\sum _{j=0}^{k-1}f[n][j]\times 2$，其中 $n$ 为数组 nums 的长度。最后，我们用 $2^n$ 减去“坏分区”的个数，即可得到“好分区”的个数。

时间复杂度 $O(n\times k)$，空间复杂度 $O(n\times k)$。其中 $n$ 为数组 nums 的长度，而 $k$ 为整数 $k$。

func countPartitions(nums []int, k int) int {
	s := 0
	for _, v := range nums {
		s += v
	}
	if s < k*2 {
		return 0
	}
	const mod int = 1e9 + 7
	n := len(nums)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k)
	}
	f[0][0] = 1
	ans := 1
	for i := 1; i <= n; i++ {
		v := nums[i-1]
		ans = ans * 2 % mod
		for j := 0; j < k; j++ {
			f[i][j] = f[i-1][j]
			if j >= v {
				f[i][j] = (f[i][j] + f[i-1][j-v]) % mod
			}
		}
	}
	for j := 0; j < k; j++ {
		ans = (ans - f[n][j]*2%mod + mod) % mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

2522. 将字符串分割成值不超过 K 的子字符串

中等2 种解法

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

题目、示例与约束

给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。

如果一个字符串 s 的分割满足以下条件，我们称它是一个 好 分割：

• s 中每个数位 恰好 属于一个子字符串。
• 每个子字符串的值都小于等于 k 。

请你返回 s 所有的 好 分割中，子字符串的 最少 数目。如果不存在 s 的 好 分割，返回 -1 。

注意：

• 一个字符串的 值 是这个字符串对应的整数。比方说，"123" 的值为 123 ，"1" 的值是 1 。
• 子字符串 是字符串中一段连续的字符序列。

 

示例 1：

输入：s = "165462", k = 60
输出：4
解释：我们将字符串分割成子字符串 "16" ，"54" ，"6" 和 "2" 。每个子字符串的值都小于等于 k = 60 。
不存在小于 4 个子字符串的好分割。

示例 2：

输入：s = "238182", k = 5
输出：-1
解释：这个字符串不存在好分割。

 

提示：

• 1 <= s.length <= 105
• s[i] 是 '1' 到 '9' 之间的数字。
• 1 <= k <= 109

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

思考

要把数字串切成若干段，每段表示的整数值不超过 $k$，并最小化段数。 $n\le {10}^5$、 $k$ 的位数很少，枚举全部切法不可行，但合法段的长度上界为 $k$ 的位数，从每个起点只能延伸常数段。

令 $\mathit{\text{dfs}}(i)$ 为从下标 $i$ 起的最少段数。自 $i$ 向右累加数值，一旦超过 $k$ 即停止，对每个合法终点取 $1+\mathit{\text{dfs}}(j+1)$ 的最小者。记忆化后每个起点只算一次；无法切开时得到 $\mathrm{\infty }$，对外返回 $-1$。

我们设计一个函数 $dfs(i)$ 表示从字符串 $s$ 的下标 $i$ 开始的最少分割数，那么答案就是 $dfs(0)$。

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

• 如果 $i\ge n$，说明已经到达字符串末尾，返回 $0$。
• 否则，我们枚举 $i$ 开始的所有子字符串，如果子字符串的值小于等于 $k$，那么我们可以将子字符串作为一个分割，那么我们可以得到 $dfs(j+1)$，其中 $j$ 是子字符串的末尾下标，然后我们取所有可能的分割中的最小值，再加上 $1$，即为 $dfs(i)$ 的值。

最后，如果 $dfs(0)=\mathrm{\infty }$，说明不存在好分割，返回 $-1$，否则返回 $dfs(0)$。

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

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

func minimumPartition(s string, k int) int {
	n := len(s)
	f := make([]int, n)
	const inf int = 1 << 30
	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if f[i] > 0 {
			return f[i]
		}
		res, v := inf, 0
		for j := i; j < n; j++ {
			v = v*10 + int(s[j]-'0')
			if v > k {
				break
			}
			res = min(res, dfs(j+1))
		}
		f[i] = res + 1
		return f[i]
	}
	ans := dfs(0)
	if ans < inf {
		return ans
	}
	return -1
}

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

思考

枚举全部切法是指数级的。字符串长度可以到 ${10}^5$，而每一位都是 $1$ 到 $9$，只要当前数字不超过 $k$，第一次递归总是落到下一个下标，调用深度就是 $n$。一段的数值一旦超过 $k$ 就不能再延长，所以从下标 $i$ 出发的最少段数只依赖更靠后的位置。令 $f[i]$ 为从 $i$ 起到末尾的最少段数， $f[n]=0$，按 $i$ 从 $n-1$ 降到 $0$，向右累加子串值，对每个不超过 $k$ 的终点用 $f[j+1]$ 更新后再加一。 $f[0]$ 仍不小于哨兵时返回 $-1$。

我们令 $f[i]$ 表示从字符串 $s$ 的下标 $i$ 开始的最少分割数， $f[n]=0$。答案是 $f[0]$。

按 $i$ 从 $n-1$ 递减到 $0$。从 $i$ 向右累加子串对应的整数，一旦超过 $k$ 就停止。对每个不超过 $k$ 的终点 $j$，用 $f[j+1]$ 更新 $f[i]$，然后把 $f[i]$ 加一。

若 $f[0]$ 不小于预先设定的上界，说明不存在好分割，返回 $-1$，否则返回 $f[0]$。

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

func minimumPartition(s string, k int) int {
	n := len(s)
	const inf = 1 << 30
	f := make([]int, n+1)
	for i := 0; i < n; i++ {
		f[i] = inf
	}
	for i := n - 1; i >= 0; i-- {
		v := 0
		for j := i; j < n; j++ {
			v = v*10 + int(s[j]-'0')
			if v > k {
				break
			}
			f[i] = min(f[i], f[j+1])
		}
		f[i]++
	}
	if f[0] < inf {
		return f[0]
	}
	return -1
}

力扣原题 · Doocs 题解来源

2533. 好二进制字符串的数量 🔒

中等1 种解法

标签：动态规划

题目、示例与约束

给你四个整数 minLength、maxLength、oneGroup 和 zeroGroup 。

好 二进制字符串满足下述条件：

• 字符串的长度在 [minLength, maxLength] 之间。
• 每块连续 1 的个数是 oneGroup 的整数倍
  • 例如在二进制字符串 00110111100 中，每块连续 1 的个数分别是[2,4] 。
• 每块连续 0 的个数是 zeroGroup 的整数倍
  • 例如在二进制字符串 00110111100 中，每块连续 0 的个数分别是 [2,1,2] 。

请返回 好 二进制字符串的个数。答案可能很大，请返回对 109 + 7 取余 后的结果。

注意：0 可以被认为是所有数字的倍数。

 

示例 1：

输入：minLength = 2, maxLength = 3, oneGroup = 1, zeroGroup = 2
输出：5
解释：在本示例中有 5 个好二进制字符串: "00", "11", "001", "100", 和 "111" 。
可以证明只有 5 个好二进制字符串满足所有的条件。

示例 2：

输入：minLength = 4, maxLength = 4, oneGroup = 4, zeroGroup = 3
输出：1
解释：在本示例中有 1 个好二进制字符串: "1111" 。
可以证明只有 1 个好字符串满足所有的条件。

 

提示：

• 1 <= minLength <= maxLength <= 105
• 1 <= oneGroup, zeroGroup <= maxLength

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

思考

好串由长度为 $\mathit{\text{oneGroup}}$ 的全 $1$ 段与长度为 $\mathit{\text{zeroGroup}}$ 的全 $0$ 段拼接而成，总长落在 $[\mathit{\text{minLength}},\mathit{\text{maxLength}}]$。段的拼接顺序任意，枚举切分方式数量过大。

令 $f[i]$ 为长度为 $i$ 的好串个数。最后一段只能是一组 $1$ 或一组 $0$，故 $f[i]=f[i-\mathit{\text{oneGroup}}]+f[i-\mathit{\text{zeroGroup}}]$（下标合法时）， $f[0]=1$。答案为 $f[\mathit{\text{minLength}}]$ 到 $f[\mathit{\text{maxLength}}]$ 之和。

我们定义 $f[i]$ 表示长度为 $i$ 的字符串中满足条件的个数。状态转移方程为：

$$f[i]=\{\begin{array}{ll}1& i=0\\ f[i-oneGroup]+f[i-zeroGroup]& i\ge 1\end{array}$$

最终答案为 $f[minLength]+f[minLength+1]+\cdots +f[maxLength]$。

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

func goodBinaryStrings(minLength int, maxLength int, oneGroup int, zeroGroup int) (ans int) {
	const mod int = 1e9 + 7
	f := make([]int, maxLength+1)
	f[0] = 1
	for i := 1; i <= maxLength; i++ {
		if i-oneGroup >= 0 {
			f[i] += f[i-oneGroup]
		}
		if i-zeroGroup >= 0 {
			f[i] += f[i-zeroGroup]
		}
		f[i] %= mod
	}
	for _, v := range f[minLength:] {
		ans = (ans + v) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

2547. 拆分数组的最小代价

困难2 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。

将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。

令 trimmed(subarray) 作为子数组的一个特征，其中所有仅出现一次的数字将会被移除。

• 例如，trimmed([3,1,2,4,3,4]) = [3,4,3,4] 。

子数组的 重要性 定义为 k + trimmed(subarray).length 。

• 例如，如果一个子数组是 [1,2,3,3,3,4,4] ，trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4] 。这个子数组的重要性就是 k + 5 。

找出并返回拆分 nums 的所有可行方案中的最小代价。

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

 

示例 1：

输入：nums = [1,2,1,2,1,3,3], k = 2
输出：8
解释：将 nums 拆分成两个子数组：[1,2], [1,2,1,3,3]
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1,3,3] 的重要性是 2 + (2 + 2) = 6 。
拆分的代价是 2 + 6 = 8 ，可以证明这是所有可行的拆分方案中的最小代价。

示例 2：

输入：nums = [1,2,1,2,1], k = 2
输出：6
解释：将 nums 拆分成两个子数组：[1,2], [1,2,1] 。
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1] 的重要性是 2 + (2) = 4 。
拆分的代价是 2 + 4 = 6 ，可以证明这是所有可行的拆分方案中的最小代价。

示例 3：

输入：nums = [1,2,1,2,1], k = 5
输出：10
解释：将 nums 拆分成一个子数组：[1,2,1,2,1].
[1,2,1,2,1] 的重要性是 5 + (3 + 2) = 10 。
拆分的代价是 10 ，可以证明这是所有可行的拆分方案中的最小代价。

 

提示：

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

 

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

思考

把数组切成若干段，每段代价为 $k$ 加上其中出现超过一次的元素个数（即长度减去只出现一次的个数）。 $n\le {10}^3$，枚举全部切法过多，但切点只有 $n$ 个。

令 $\mathit{\text{dfs}}(i)$ 为从 $i$ 切到末尾的最小代价。枚举本段右端 $j$，用计数器维护“出现恰好一次”的个数 $\mathit{\text{one}}$，本段代价为 $k+(j-i+1)-\mathit{\text{one}}$，再加上 $\mathit{\text{dfs}}(j+1)$。记忆化后状态 $O(n)$、转移 $O(n)$。

我们设计一个函数 $dfs(i)$，表示从下标 $i$ 开始拆分的最小代价。那么答案就是 $dfs(0)$。

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

• 如果 $i\ge n$，说明已经拆分到了数组末尾，此时返回 $0$。
• 否则，我们枚举子数组的末尾 $j$，过程中用一个数组或哈希表 cnt 统计子数组中每个数字出现的次数，用一个变量 one 统计子数组中出现次数为 $1$ 的数字的个数。那么子数组的重要性就是 $k+j-i+1-one$，拆分的代价就是 $k+j-i+1-one+dfs(j+1)$。我们枚举所有的 $j$，取其中的最小值作为 $dfs(i)$ 的返回值。

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

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

func minCost(nums []int, k int) int {
	n := len(nums)
	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]
		}
		ans, one := 1<<30, 0
		cnt := make([]int, n)
		for j := i; j < n; j++ {
			cnt[nums[j]]++
			x := cnt[nums[j]]
			if x == 1 {
				one++
			} else if x == 2 {
				one--
			}
			ans = min(ans, k+j-i+1-one+dfs(j+1))
		}
		f[i] = ans
		return ans
	}
	return dfs(0)
}

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

思考

枚举全部切法是指数级的。数组长度可以到 $1000$，而本段右端从当前位置开始试，第一次总会先算紧邻后缀，递归深度就是 $n$。从下标 $i$ 起的最小代价只依赖更靠右的答案。于是令 $f[i]$ 为从 $i$ 拆到末尾的最小代价， $f[n]=0$，从右往左枚举右端点 $j$，用计数维护恰好出现一次的个数 $\mathit{\text{one}}$，以 $k+(j-i+1)-\mathit{\text{one}}+f[j+1]$ 更新。

设 $f[i]$ 为从下标 $i$ 开始拆分的最小代价，边界 $f[n]=0$。从 $i=n-1$ 递减到 $0$，枚举本段右端 $j$。用数组 $\mathit{\text{cnt}}$ 统计 $nums[i..j]$ 里每个值的出现次数，用 $\mathit{\text{one}}$ 统计恰好出现一次的值的个数。这一段的重要性是 $k+j-i+1-\mathit{\text{one}}$，再加上后缀代价 $f[j+1]$， $f[i]$ 取所有右端点中的最小值。答案为 $f[0]$。

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

func minCost(nums []int, k int) int {
	n := len(nums)
	f := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		cnt := make([]int, n)
		one := 0
		ans := k + n + 1
		for j := i; j < n; j++ {
			cnt[nums[j]]++
			x := cnt[nums[j]]
			if x == 1 {
				one++
			} else if x == 2 {
				one--
			}
			ans = min(ans, k+j-i+1-one+f[j+1])
		}
		f[i] = ans
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

2556. 二进制矩阵中翻转最多一次使路径不连通

中等2 种解法

标签：深度优先搜索、广度优先搜索、数组、动态规划、矩阵

题目、示例与约束

给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 不连通 的。

你可以翻转 最多一个 格子的值（也可以不翻转）。你 不能翻转 格子 (0, 0) 和 (m - 1, n - 1) 。

如果可以使矩阵不连通，请你返回 true ，否则返回 false 。

注意 ，翻转一个格子的值，可以使它的值从 0 变 1 ，或从 1 变 0 。

 

示例 1：

输入：grid = [[1,1,1],[1,0,0],[1,1,1]]
输出：true
解释：按照上图所示我们翻转蓝色格子里的值，翻转后从 (0, 0) 到 (2, 2) 没有路径。

示例 2：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：false
解释：无法翻转至多一个格子，使 (0, 0) 到 (2, 2) 没有路径。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 105
• grid[0][0] == grid[m - 1][n - 1] == 1

方法一：两次 DFS · Go 实现

思考

只能向右或向下走，问能否翻转至多一个非端点格子，使左上到右下不连通。枚举翻转位置再判连通是立方级。

网格上若存在两条顶点内部不交的路径，则必须翻两格才能切断。先 DFS 找一条路径并把途经格（除恢复的两端）置 $0$，再 DFS 一次：若仍能到达，说明存在第二条不相交路径，无法用一次翻转断开。

我们先进行一次 DFS，判断从 $(0,0)$ 到 $(m-1,n-1)$ 是否存在路径，记结果为 $a$。在 DFS 的过程中，我们将访问过的格子的值置为 $0$，以防止重复访问。

接下来，我们将 $(0,0)$ 和 $(m-1,n-1)$ 的值置为 $1$，再进行一次 DFS，判断从 $(0,0)$ 到 $(m-1,n-1)$ 是否存在路径，记结果为 $b$。在 DFS 的过程中，我们将访问过的格子的值置为 $0$，避免重复访问。

最后，如果 $a$ 和 $b$ 都为 true，则返回 false，否则返回 true。

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

func isPossibleToCutPath(grid [][]int) bool {
	m, n := len(grid), len(grid[0])
	var dfs func(i, j int) bool
	dfs = func(i, j int) bool {
		if i >= m || j >= n || grid[i][j] == 0 {
			return false
		}
		if i == m-1 && j == n-1 {
			return true
		}
		grid[i][j] = 0
		return dfs(i+1, j) || dfs(i, j+1)
	}
	a := dfs(0, 0)
	grid[0][0], grid[m-1][n-1] = 1, 1
	b := dfs(0, 0)
	return !(a && b)
}

方法二：两次显式栈 · Go 实现

思考

只能向右或向下走，问能否翻转至多一个非端点格子，使左上到右下不连通。枚举翻转位置再判连通是立方级。网格上若存在两条内部不相交的路径，一次翻转就不够。先向下优先找出一条路径，把经过的格子清零，两端再恢复，然后同样再搜一次。行数可以到 $1000$，而第一步总是向下，调用深度就是 $m$。因此用显式栈保持同一顺序：先压入右方，再压入下方。

搜索使用显式栈，进入格子时把它置为 $0$，先处理下方再处理右方。

我们先用显式栈搜索一次，判断从 $(0,0)$ 到 $(m-1,n-1)$ 是否存在路径，记结果为 $a$。搜索过程中，我们将访问过的格子的值置为 $0$，以防止重复访问。

接下来，我们将 $(0,0)$ 和 $(m-1,n-1)$ 的值置为 $1$，再用显式栈搜索一次，判断从 $(0,0)$ 到 $(m-1,n-1)$ 是否存在路径，记结果为 $b$。搜索过程中，我们将访问过的格子的值置为 $0$，避免重复访问。

最后，如果 $a$ 和 $b$ 都为 true，则返回 false，否则返回 true。

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

func isPossibleToCutPath(grid [][]int) bool {
	m, n := len(grid), len(grid[0])
	dfs := func() bool {
		stk := [][2]int{{0, 0}}
		for len(stk) > 0 {
			i, j := stk[len(stk)-1][0], stk[len(stk)-1][1]
			stk = stk[:len(stk)-1]
			if i >= m || j >= n || grid[i][j] == 0 {
				continue
			}
			grid[i][j] = 0
			if i == m-1 && j == n-1 {
				return true
			}
			stk = append(stk, [2]int{i, j + 1}, [2]int{i + 1, j})
		}
		return false
	}
	a := dfs()
	grid[0][0], grid[m-1][n-1] = 1, 1
	b := dfs()
	return !(a && b)
}

力扣原题 · Doocs 题解来源

2560. 打家劫舍 IV

中等1 种解法

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

题目、示例与约束

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

 

示例 1：

输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。

示例 2：

输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= (nums.length + 1)/2

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

思考

能力定义为所偷房屋金额的最大值，房屋不能相邻，要偷至少 $k$ 间并最小化该能力。枚举子集在 $n\le {10}^5$ 下不可行。

能力 $x$ 越大越容易凑满 $k$ 间，故对 $x$ 二分。检验时从左到右贪心：金额不超过 $x$ 且与上一间不相邻就偷，能偷满 $k$ 则 $x$ 可行。 $\mathit{\text{bisect\_left}}$ 给出最小可行能力。

题目求的是窃贼的最小窃取能力，我们可以二分枚举窃贼的窃取能力，对于枚举的能力 $x$，我们可以通过贪心的方式判断窃贼是否能够窃取至少 $k$ 间房屋，具体地，我们从左到右遍历数组，对于当前遍历到的房屋 $i$，如果 $nums[i]\le x$ 且 $i$ 与上一个窃取的房屋的下标之差大于 $1$，则窃贼可以窃取房屋 $i$，否则窃贼不能窃取房屋 $i$。累计窃取的房屋数，如果窃取的房屋数大于等于 $k$，则说明窃贼可以窃取至少 $k$ 间房屋，此时窃贼的窃取能力 $x$ 可能是最小的，否则窃贼的窃取能力 $x$ 不是最小的。

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

func minCapability(nums []int, k int) int {
	return sort.Search(1e9+1, func(x int) bool {
		cnt, j := 0, -2
		for i, v := range nums {
			if v > x || i == j+1 {
				continue
			}
			cnt++
			j = i
		}
		return cnt >= k
	})
}

力扣原题 · Doocs 题解来源

2571. 将整数减少到零需要的最少操作数

中等1 种解法

标签：贪心、位运算、动态规划

题目、示例与约束

给你一个正整数 n ，你可以执行下述操作 任意 次：

• n 加上或减去 2 的某个 幂

返回使 n 等于 0 需要执行的 最少 操作数。

如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。

 

示例 1：

输入：n = 39
输出：3
解释：我们可以执行下述操作：
- n 加上 20 = 1 ，得到 n = 40 。
- n 减去 23 = 8 ，得到 n = 32 。
- n 减去 25 = 32 ，得到 n = 0 。
可以证明使 n 等于 0 需要执行的最少操作数是 3 。

示例 2：

输入：n = 54
输出：3
解释：我们可以执行下述操作：
- n 加上 21 = 2 ，得到 n = 56 。
- n 加上 23 = 8 ，得到 n = 64 。
- n 减去 26 = 64 ，得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。 

 

提示：

• 1 <= n <= 105

方法一：贪心 + 位运算 · Go 实现

思考

每次可加或减一个 $2$ 的幂，把 $n$ 变为 $0$，求最少次数。把每一位单独加减需要与 $1$ 的个数相同的步数，但连续的 $1$ 可以加一个更高位再减，用更少步消掉。

自低向高扫描连续 $1$ 段：长度为 $1$ 则一次减去该位；更长则一次加上更高位，相当于把进位留给后面（计数留 $1$）。扫完后若仍剩一段，长度为 $1$ 再加一次，更长则加两次（先加后清）。

我们将整数 $n$ 转换为二进制，从最低位开始：

• 如果当前位为 $1$，我们就累加当前连续的 $1$ 的个数；
• 如果当前位为 $0$，我们就判断当前连续的 $1$ 的个数是否超过 $0$。如果是，判断当前连续的 $1$ 的个数是否为 $1$，如果是，说明我们通过一次操作可以消除 $1$；如果大于 $1$，说明我们通过一次操作，可以把连续的 $1$ 的个数减少到 $1$。

最后，我们还需要判断当前连续的 $1$ 的个数是否为 $1$，如果是，说明我们通过一次操作可以消除 $1$；如果大于 $1$，我们通过两次操作，可以把连续的 $1$ 的消除。

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

func minOperations(n int) (ans int) {
	cnt := 0
	for ; n > 0; n >>= 1 {
		if n&1 == 1 {
			cnt++
		} else if cnt > 0 {
			ans++
			if cnt == 1 {
				cnt = 0
			} else {
				cnt = 1
			}
		}
	}
	if cnt == 1 {
		ans++
	} else if cnt > 1 {
		ans += 2
	}
	return
}

力扣原题 · Doocs 题解来源

2572. 无平方子集计数

中等1 种解法

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

题目、示例与约束

给你一个正整数数组 nums 。

如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个 无平方 子集。

无平方因子数 是无法被除 1 之外任何平方数整除的数字。

返回数组 nums 中 无平方 且 非空 的子集数目。因为答案可能很大，返回对 109 + 7 取余的结果。

nums 的 非空子集 是可以由删除 nums 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。

 

示例 1：

输入：nums = [3,4,4,5]
输出：3
解释：示例中有 3 个无平方子集：
- 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ，这是一个无平方因子数。
- 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ，这是一个无平方因子数。
- 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 3 个无平方子集。

示例 2：

输入：nums = [1]
输出：1
解释：示例中有 1 个无平方子集：
- 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 1 个无平方子集。

 

提示：

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

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

思考

子集乘积无平方因子，空集不计， $nums[i]\in [1,30]$。 $2^n$ 在 $n\le {10}^3$ 时不可枚举，但取值只有 $30$ 种，且含平方因子的数不能出现。

不超过 $30$ 的质数共 $10$ 个，子集的质因数集合可用 $10$ 位掩码表示。 $f[\mathit{\text{state}}]$ 为凑出该掩码的方案数； $1$ 可任意选取，故 $f[0]=2^{\mathit{\text{cnt}}[1]}$。按 $0$-$1$ 背包从大到小转移每个无平方的 $x$。全部状态之和减去空集即为答案。

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

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

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

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

注意，我们没有从数字 $1$ 开始枚举，因为我们可以选择任意个数字 $1$，加入到无平方子集中。也可以只选择任意个数字 $1$，不加入到无平方子集中，这两种情况都是合法的。那么答案就是 $(\sum _{i=0}^{2^{10}-1}f[i])-1$。

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

相似题目：

• 1994. 好子集的数目

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

力扣原题 · Doocs 题解来源

2585. 获得分数的方法数

困难1 种解法

标签：数组、动态规划、背包问题、多重背包

题目、示例与约束

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余。

注意，同类型题目无法区分。

• 比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

 

示例 1：

输入：target = 6, types = [[6,1],[3,2],[2,3]]
输出：7
解释：要获得 6 分，你可以选择以下七种方法之一：
- 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6
- 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6
- 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6
- 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6
- 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6
- 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6
- 解决 2 道第 2 种类型的题目：3 + 3 = 6

示例 2：

输入：target = 5, types = [[50,1],[50,2],[50,5]]
输出：4
解释：要获得 5 分，你可以选择以下四种方法之一：
- 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5
- 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5
- 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5
- 解决 1 道第 2 种类型的题目：5

示例 3：

输入：target = 18, types = [[6,1],[3,2],[2,3]]
输出：1
解释：只有回答所有题目才能获得 18 分。

 

提示：

• 1 <= target <= 1000
• n == types.length
• 1 <= n <= 50
• types[i].length == 2
• 1 <= counti, marksi <= 50

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

思考

每种题有数量上限与固定分值，求恰好得到 $\mathit{\text{target}}$ 分的方案数。完全背包若忽略数量上限会多算。

多重背包：令 $f[i][j]$ 为前 $i$ 种题得到 $j$ 分的方案。第 $i$ 种可做 $0..\mathit{\text{count}}$ 道，从 $f[i-1][j-k\cdot \mathit{\text{marks}}]$ 累加。 $f[0][0]=1$，答案为 $f[n][\mathit{\text{target}}]$。

我们定义 $f[i][j]$ 表示前 $i$ 种类型的题目中，恰好得到 $j$ 分的方法数。初始时 $f[0][0]=1$，其余 $f[i][j]=0$。答案即为 $f[n][target]$。

我们可以枚举第 $i$ 种类型的题目，假设该类型题目的数量为 $count$，分数为 $marks$，那么我们可以得到如下状态转移方程：

$$f[i][j]=\sum _{k=0}^{count}f[i-1][j-k\times marks]$$

其中 $k$ 表示第 $i$ 种类型的题目的数量。

最终的答案即为 $f[n][target]$。注意答案可能很大，需要对 ${10}^9+7$ 取模。

时间复杂度 $O(n\times target\times count)$，空间复杂度 $O(n\times target)$。其中 $n$ 为题目类型的数量；而 $target$ 和 $count$ 分别为题目的目标分数和每种类型题目的数量。

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

力扣原题 · Doocs 题解来源

2597. 美丽子集的数目

中等1 种解法

标签：数组、哈希表、数学、动态规划、回溯、组合数学、排序

题目、示例与约束

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

 

示例 1：

输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

示例 2：

输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。 

 

提示：

• 1 <= nums.length <= 18
• 1 <= nums[i], k <= 1000

方法一：计数 + 回溯 · Go 实现

思考

子集美丽当且仅当其中任意两数之差的绝对值不为 $k$，空集不计。 $n\le 20$，枚举 $2^n$ 个子集可行。

回溯时对每个数选择或不选；选 $x$ 当且仅当 $x-k$ 与 $x+k$ 都尚未出现。用计数器维护已选频次，初始答案为 $-1$ 以扣除空集。

我们用哈希表或数组 $\mathit{\text{cnt}}$ 记录当前已经选择的数字以及它们的个数，用 $\mathit{\text{ans}}$ 记录美丽子集的数目，初始时 $\mathit{\text{ans}}=-1$，表示排除空集。

对于数组 $\mathit{\text{nums}}$ 中的每个数字 $x$，我们有两种选择：

• 不选择 $x$，此时直接递归到下一个数字；
• 选择 $x$，此时需要判断 $x+k$ 和 $x-k$ 是否已经在 $\mathit{\text{cnt}}$ 中出现过，如果都没有出现过，那么我们就可以选择 $x$，此时我们将 $x$ 的个数加一，然后递归到下一个数字，最后将 $x$ 的个数减一。

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

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

func beautifulSubsets(nums []int, k int) int {
	ans := -1
	n := len(nums)
	cnt := [1010]int{}
	var dfs func(int)
	dfs = func(i int) {
		if i >= n {
			ans++
			return
		}
		dfs(i + 1)
		ok1 := nums[i]+k >= len(cnt) || cnt[nums[i]+k] == 0
		ok2 := nums[i]-k < 0 || cnt[nums[i]-k] == 0
		if ok1 && ok2 {
			cnt[nums[i]]++
			dfs(i + 1)
			cnt[nums[i]]--
		}
	}
	dfs(0)
	return ans
}

力扣原题 · Doocs 题解来源

2606. 找到最大开销的子字符串

中等2 种解法

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

题目、示例与约束

给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。

子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。

字符的价值 定义如下：

• 如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
  • 比方说，'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。
• 否则，如果这个字符在 chars 中的位置为 i ，那么它的价值就是 vals[i] 。

请你返回字符串 s 的所有子字符串中的最大开销。

 

示例 1：

输入：s = "adaa", chars = "d", vals = [-1000]
输出：2
解释：字符 "a" 和 "d" 的价值分别为 1 和 -1000 。
最大开销子字符串是 "aa" ，它的开销为 1 + 1 = 2 。
2 是最大开销。

示例 2：

输入：s = "abc", chars = "abc", vals = [-1,-1,-1]
输出：0
解释：字符 "a" ，"b" 和 "c" 的价值分别为 -1 ，-1 和 -1 。
最大开销子字符串是 "" ，它的开销为 0 。
0 是最大开销。

 

提示：

• 1 <= s.length <= 105
• s 只包含小写英文字母。
• 1 <= chars.length <= 26
• chars 只包含小写英文字母，且 互不相同 。
• vals.length == chars.length
• -1000 <= vals[i] <= 1000

方法一：前缀和 + 维护前缀和的最小值 · Go 实现

思考

子串开销是区间价值和，空串开销为 $0$。若枚举左右端点再求和， $n\le {10}^5$ 不可行。

固定右端后，最大开销等于当前前缀和减去历史上的最小前缀和（含空前缀 $0$）。因此扫一遍维护前缀和 $tot$ 及其最小值 $mi$，用 $tot-mi$ 更新答案。

字符价值先放入哈希表，未出现的字母取默认序号。

我们根据题目描述，遍历字符串 $s$ 的每个字符 $c$，求出其对应的价值 $v$，然后更新当前的前缀和 $tot=tot+v$，那么以 $c$ 结尾的最大开销子字符串的开销为 $tot$ 减去前缀和的最小值 $mi$，即 $tot-mi$，我们更新答案 $ans=max(ans,tot-mi)$，并维护前缀和的最小值 $mi=min(mi,tot)$。

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

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

func maximumCostSubstring(s string, chars string, vals []int) (ans int) {
	d := [26]int{}
	for i := range d {
		d[i] = i + 1
	}
	for i, c := range chars {
		d[c-'a'] = vals[i]
	}
	tot, mi := 0, 0
	for _, c := range s {
		v := d[c-'a']
		tot += v
		ans = max(ans, tot-mi)
		mi = min(mi, tot)
	}
	return
}

方法二：转化为最大子数组和问题 · Go 实现

思考

方法一显式维护全局最小前缀。同一问题等价于最大子数组和：若当前累计为负，则丢弃前缀再从下一个字符开始。

Kadane 形式 $f=max(f,0)+v$ 省去前缀数组，答案同样覆盖空串（初值 $0$）。

我们可以将每个字符 $c$ 的价值 $v$ 看作是一个整数，那么题目实际上转化为求最大子数组和问题。

我们用变量 $f$ 维护以当前字符 $c$ 结尾的最大开销子字符串的开销，每次遍历到一个字符 $c$，更新 $f=max(f,0)+v$，然后更新答案 $ans=max(ans,f)$ 即可。

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

func maximumCostSubstring(s string, chars string, vals []int) (ans int) {
	d := [26]int{}
	for i := range d {
		d[i] = i + 1
	}
	for i, c := range chars {
		d[c-'a'] = vals[i]
	}
	f := 0
	for _, c := range s {
		v := d[c-'a']
		f = max(f, 0) + v
		ans = max(ans, f)
	}
	return
}

力扣原题 · Doocs 题解来源

2616. 最小化数对的最大差值

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。我们定义空集的最大值为零。

 

示例 1：

输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

示例 2：

输入：nums = [4,2,1,2], p = 1
输出：0
解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= p <= (nums.length)/2

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

思考

要选 $p$ 对不相交下标，最小化各对差值的最大值。搜索配对方案组合数过大； $n\le {10}^5$ 需要多项式做法。

最大差值 $x$ 单调：能在上限 $x$ 下凑满 $p$ 对，则更大上限也可。排序后相邻更可能配对，从左到右能配则立刻配，以免占用后面的位置。

对 $x$ 二分，用该贪心检验能否选出 $p$ 对。

我们注意到，最大差值具备单调性，即如果最大差值 $x$ 满足条件，那么 $x-1$ 也一定满足条件。因此我们可以使用二分查找的方法，找到最小的满足条件的最大差值。

我们可以将数组 $\mathit{\text{nums}}$ 排序，然后枚举最大差值 $x$，判断是否存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$。如果存在，那么我们就可以将 $x$ 减小，否则我们就将 $x$ 增大。

判断是否存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$，可以使用贪心的方法。我们从左到右遍历数组 $\mathit{\text{nums}}$，对于当前遍历到的下标 $i$，如果 $i+1$ 位置的数与 $i$ 位置的数的差值不超过 $x$，那么我们就可以将 $i$ 和 $i+1$ 位置的数作为一个下标对，更新下标对的数量 $cnt$，然后将 $i$ 的值增加 $2$。否则，我们就将 $i$ 的值增加 $1$。遍历结束，如果 $cnt$ 的值大于等于 $p$，那么就说明存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$，否则就说明不存在。

时间复杂度 $O(n\times (\log n+\log m))$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度，而 $m$ 是数组 $\mathit{\text{nums}}$ 中的最大值与最小值的差值。空间复杂度 $O(1)$。

func minimizeMax(nums []int, p int) int {
	sort.Ints(nums)
	n := len(nums)
	r := nums[n-1] - nums[0] + 1
	return sort.Search(r, func(diff int) bool {
		cnt := 0
		for i := 0; i < n-1; i++ {
			if nums[i+1]-nums[i] <= diff {
				cnt++
				i++
			}
		}
		return cnt >= p
	})
}

力扣原题 · Doocs 题解来源

2638. 统计 K-Free 子集的总数 🔒

中等1 种解法

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

题目、示例与约束

给定一个包含 无重复 元素的整数数组 nums 和一个整数 k 。

如果一个子集中 不 存在两个差的绝对值等于 k 的元素，则称其为 k-Free 子集。注意，空集是一个 k-Free 子集。

返回 nums 中 k-Free 子集的数量。

一个数组的 子集 是该数组中的元素的选择（可能为零个）。

 

示例 1 ：

输入：nums = [5,4,6], k = 1
输出：5
解释：有 5 个合法子集：{}, {5}, {4}, {6} 和 {4, 6} 。

示例 2 ：

输入：nums = [2,3,5,8], k = 5
输出：12
解释：有12个合法子集：{}, {2}, {3}, {5}, {8}, {2, 3}, {2, 3, 5}, {2, 5}, {2, 5, 8}, {2, 8}, {3, 5} 和 {5, 8} 。

示例 3 ：

输入：nums = [10,5,9,11], k = 20
输出：16
解释：所有的子集都是有效的。由于子集的总数为 2^4 = 16，因此答案为 16 。

 

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 1000
• 1 <= k <= 1000

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

思考

子集中不能同时包含差为 $k$ 的两数。枚举 $2^n$ 个子集在 $n\le 50$ 时不可行。差为 $k$ 的数模 $k$ 同余，不同余类互不影响。

同类内排序后，相邻是否恰相差 $k$ 决定能否同时选取，于是化为「相邻互斥」的线性 DP：冲突则 $f[i]=f[i-1]+f[i-2]$，否则每个元素可自由选不选， $f[i]=2f[i-1]$。

各类方案数相乘，空集计入初值 $f[0]=1$。

我们先将数组 $nums$ 按照升序排序，然后将数组中的元素按照模 $k$ 分组，即 $nums[i]modk$ 相同的元素放在同一组中。那么对于任意两个不同组的元素，它们的差值的绝对值一定不等于 $k$。因此，我们可以求出每一组的子集个数，然后将每一组的子集个数相乘即可得到答案。

对于每一组 $arr$，我们可以使用动态规划求出子集个数。设 $f[i]$ 表示前 $i$ 个元素的子集个数，初始时 $f[0]=1$，而 $f[1]=2$。当 $i\ge 2$ 时，如果 $arr[i-1]-arr[i-2]=k$，如果我们选择 $arr[i-1]$，那么 $f[i]=f[i-2]$；如果我们不选择 $arr[i-1]$，那么 $f[i]=f[i-1]$。因此，当 $arr[i-1]-arr[i-2]=k$ 时，有 $f[i]=f[i-1]+f[i-2]$；否则 $f[i]=f[i-1]\times 2$。这一组的子集个数即为 $f[m]$，其中 $m$ 为数组 $arr$ 的长度。

最后，我们将每一组的子集个数相乘即可得到答案。

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

func countTheNumOfKFreeSubsets(nums []int, k int) int64 {
	sort.Ints(nums)
	g := map[int][]int{}
	for _, x := range nums {
		g[x%k] = append(g[x%k], x)
	}
	ans := int64(1)
	for _, arr := range g {
		m := len(arr)
		f := make([]int64, m+1)
		f[0] = 1
		f[1] = 2
		for i := 2; i <= m; i++ {
			if arr[i-1]-arr[i-2] == k {
				f[i] = f[i-1] + f[i-2]
			} else {
				f[i] = f[i-1] * 2
			}
		}
		ans *= f[m]
	}
	return ans
}

力扣原题 · Doocs 题解来源

2645. 构造有效字符串的最少插入数

中等1 种解法

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

题目、示例与约束

给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。

如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。

 

示例 1：

输入：word = "b"
输出：2
解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。

示例 2：

输入：word = "aaa"
输出：6
解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。

示例 3：

输入：word = "abc"
输出：0
解释：word 已经是有效字符串，不需要进行修改。 

 

提示：

• 1 <= word.length <= 50
• word 仅由字母 "a"、"b" 和 "c" 组成。

方法一：贪心 + 双指针 · Go 实现

思考

目标由若干段 abc 拼接而成，只能插入字符。若对分割点做 DP， $n\le 50$ 可行，但匹配具有唯一贪心推进方式。

用指针在循环串 abc 上走：当前字符对不上就视为插入并计一次，对上则消耗 $word$ 中一个字符。扫完后若结尾不是 c，再补齐剩余字母。

我们定义字符串 $s$ 为 "abc"，用指针 $i$ 和 $j$ 分别指向 $s$ 和 $word$。

如果 $word[j]\ne s[i]$，则需要插入 $s[i]$，我们将答案加 $1$；否则，说明 $word[j]$ 可以与 $s[i]$ 匹配，我们将 $j$ 右移一位。

然后，我们将 $i$ 右移一位，即 $i=(i+1)mod3$。继续上述操作，直到 $j$ 到达字符串 $word$ 的末尾。

最后，我们判断 $word$ 的最后一个字符是否为 'b' 或者 'a'，如果是，则需要插入 'c' 或者 'bc'，我们将答案加 $1$ 或者 $2$ 后返回即可。

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

func addMinimum(word string) (ans int) {
	s := "abc"
	n := len(word)
	for i, j := 0, 0; j < n; i = (i + 1) % 3 {
		if word[j] != s[i] {
			ans++
		} else {
			j++
		}
	}
	if word[n-1] == 'b' {
		ans++
	} else if word[n-1] == 'a' {
		ans += 2
	}
	return
}

力扣原题 · Doocs 题解来源

2681. 英雄的力量

困难1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

• i0 ，i1 ，... ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。

 

示例 1：

输入：nums = [2,1,4]
输出：141
解释：
第 1 组：[2] 的力量为 22 * 2 = 8 。
第 2 组：[1] 的力量为 12 * 1 = 1 。
第 3 组：[4] 的力量为 42 * 4 = 64 。
第 4 组：[2,1] 的力量为 22 * 1 = 4 。
第 5 组：[2,4] 的力量为 42 * 2 = 32 。
第 6 组：[1,4] 的力量为 42 * 1 = 16 。
第​ ​​​​​​7 组：[2,1,4] 的力量为 42​​​​​​​ * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。

示例 2：

输入：nums = [1,1,1]
输出：7
解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。

 

提示：

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

方法一：排序 + 数学 · Go 实现

思考

子序列贡献为 $\stackrel{2}{max}\cdot min$。顺序无关，排序后枚举最小值 $a_i$，右侧每个 $a_j$ 作为最大值的系数呈二的幂。直接枚举子序列 $2^n$ 不可行， $n\le {10}^5$。

从右向左维护加权平方和 $p$，当前 $x$ 贡献 $x^3$ 以及 $x\cdot p$，再令 $p\leftarrow 2p+x^2$，即可在线性时间内累加。

我们注意到，题目中涉及到子序列的最大值和最小值，数组中元素的顺序不影响最终的结果，因此我们可以先对数组进行排序。

接下来，我们枚举每个元素作为子序列的最小值，不妨记数组的每个元素为 $a_1,a_2,\cdots ,a_n$。以 $a_i$ 作为最小值的子序列的贡献为：

$$a_i\times (a_i^2+a_{i+1}^2+2\times a_{i+2}^2+4\times a_{i+3}^2+\cdots +2^{n-i-1}\times a_n^2)$$

我们注意到，每一个 $a_i$ 都会乘上 $a_i^2$，这一部分我们可以直接累加到答案中。剩下的部分，我们可以用一个变量 $p$ 来维护，初始时 $p=0$。

接下来从右往左枚举 $a_i$，每次我们将 $a_i\times p$ 累加到答案中，然后令 $p=p\times 2+a_i^2$。

枚举完所有的 $a_i$ 之后，返回答案即可。

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

func sumOfPower(nums []int) (ans int) {
	const mod = 1e9 + 7
	sort.Ints(nums)
	p := 0
	for i := len(nums) - 1; i >= 0; i-- {
		x := nums[i]
		ans = (ans + (x*x%mod)*x) % mod
		ans = (ans + x*p%mod) % mod
		p = (p*2 + x*x%mod) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

2684. 矩阵中移动的最大次数

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

• 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动 的 最大 次数。

 

示例 1：

输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2：

输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

 

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 105
• 1 <= grid[i][j] <= 106

方法一：BFS · Go 实现

思考

只能向右上、右、右下走到严格更大的格子。从每行起点分别 DFS 会重复访问。列推进具有 BFS 结构：第 $j$ 列能到达的行集合，决定第 $j+1$ 列的候选。

用集合保存当前列可达行，无后继则返回已走列数；走到最后一列则答案为 $n-1$。

我们定义一个队列 $q$，初始时将第一列的所有行坐标加入队列中。

接下来，我们从第一列开始，逐列进行遍历。对于每一列，我们将队列中的所有行坐标依次取出，然后对于每一个行坐标 $i$，我们得到其下一列的所有可能行坐标 $k$，并且满足 $grid[i][j]<grid[k][j+1]$，将这些行坐标加入到一个新的集合 $t$ 中。如果 $t$ 为空，说明我们无法继续移动，返回当前列数。否则，我们将 $t$ 赋值给 $q$，继续下一列的遍历。

最后，如果我们遍历完了所有列，说明我们可以移动到最后一列，返回 $n-1$。

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

func maxMoves(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	q := map[int]bool{}
	for i := range grid {
		q[i] = true
	}
	for j := 0; j < n-1; j++ {
		t := map[int]bool{}
		for i := range q {
			for k := i - 1; k <= i+1; k++ {
				if k >= 0 && k < m && grid[i][j] < grid[k][j+1] {
					t[k] = true
				}
			}
		}
		if len(t) == 0 {
			return j
		}
		q = t
	}
	return n - 1
}

力扣原题 · Doocs 题解来源

2708. 一个小组的最大实力值

中等2 种解法

标签：贪心、位运算、数组、动态规划、回溯、枚举、排序

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​] 。

请你返回老师创建的小组能得到的最大实力值为多少。

 

示例 1：

输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。

示例 2：

输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

 

提示：

• 1 <= nums.length <= 13
• -9 <= nums[i] <= 9

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

思考

实力是非空子集的乘积，需取其最大。 $n\le 13$，子集共 $2^n-1$ 个，枚举每个掩码并连乘对应元素即可得到全局最大。

空集被排除，负数与零也一并参与乘积，无需事先分类。

题目实际上是求所有子集的乘积的最大值，由于数组长度不超过 $13$，我们可以考虑使用二进制枚举的方法。

我们在 $[1,2^n)$ 的范围内枚举所有的子集，对于每个子集，我们计算其乘积，最后返回最大值即可。

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

func maxStrength(nums []int) int64 {
	ans := int64(-1e14)
	for i := 1; i < 1<<len(nums); i++ {
		var t int64 = 1
		for j, x := range nums {
			if i>>j&1 == 1 {
				t *= int64(x)
			}
		}
		ans = max(ans, t)
	}
	return ans
}

方法二：排序 + 贪心 · Go 实现

思考

二进制枚举带 $n$ 的指数。按绝对值与符号分类后，零应尽量避开，负数成对相乘才增大乘积。排序后从左扫描：连续两个负数一并乘入，单个负数与零跳过，正数全部乘入；全零或单元素等边界单独处理。

我们可以先对数组进行排序，然后根据数组的特点，我们可以得到以下结论：

• 如果数组中只有一个元素，那么最大实力值就是这个元素；
• 如果数组中有两个及以上的元素，且数组中 $nums[1]=nums[n-1]=0$，那么最大实力值就是 $0$；
• 否则，我们从小到大遍历数组，如果当前元素小于 $0$，且下一个元素也小于 $0$，那么我们将这两个元素相乘，累乘到答案中；否则，如果当前元素小于等于 $0$，我们直接跳过；如果当前元素大于 $0$，我们将这个元素累乘到答案中，最后返回答案。

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

func maxStrength(nums []int) int64 {
	sort.Ints(nums)
	n := len(nums)
	if n == 1 {
		return int64(nums[0])
	}
	if nums[1] == 0 && nums[n-1] == 0 {
		return 0
	}
	ans := int64(1)
	for i := 0; i < n; i++ {
		if nums[i] < 0 && i+1 < n && nums[i+1] < 0 {
			ans *= int64(nums[i] * nums[i+1])
			i++
		} else if nums[i] > 0 {
			ans *= int64(nums[i])
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2712. 使所有字符相等的最小成本

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

• 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
• 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

 

示例 1：

输入：s = "0011"
输出：2
解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2：

输入：s = "010101"
输出：9
解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
执行第二种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 

 

提示：

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

方法一：贪心 · Go 实现

思考

一次操作反转某个前缀或后缀，费用为该段长度。若枚举每次反转的位置，序列长度 ${10}^5$ 下不可行。

相邻两位不同时，这一分界必须被某次前缀或后缀反转恰好覆盖奇数次。把分界 $i$ 交给前缀的费用是 $i$，交给后缀是 $n-i$，取较小者累加，各分界独立决策后即得最小费用。

根据题目描述，如果 $s[i]\ne s[i-1]$，那么一定要执行操作，否则无法使所有字符相等。

我们要么选择将 $s[0..i-1]$ 的字符全部反转，反转的成本为 $i$；要么选择将 $s[i..n-1]$ 的字符全部反转，反转的成本为 $n-i$。取两者中的最小值即可。

我们遍历字符串 $s$，将所有需要反转的字符的成本相加，即可得到最小成本。

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

func minimumCost(s string) (ans int64) {
	n := len(s)
	for i := 1; i < n; i++ {
		if s[i] != s[i-1] {
			ans += int64(min(i, n-i))
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2713. 矩阵中严格递增的单元格数

困难1 种解法

标签：记忆化、数组、哈希表、二分查找、动态规划、矩阵、有序集合、排序

题目、示例与约束

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

 

示例 1：

输入：mat = [[3,1],[3,4]]
输出：2
解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。 

示例 2：

输入：mat = [[1,1],[1,1]]
输出：1
解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。 

示例 3：

输入：mat = [[3,1,6],[-9,5,7]]
输出：4
解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。  

 

提示：

• m == mat.length 
• n == mat[i].length 
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• -105 <= mat[i][j] <= 105

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

思考

从一格出发只能走到同行或同列且值严格更大的格子，求最长路径。格子数为 ${10}^5$，按边建图再记忆化会在最坏情况下带上过大的出度。

值更小的格子不可能从更大的格子走来，故按值升序处理。同一值的格子互不转移，可先用当前行、列已记录的最大链长算出终点长度，再统一写回行、列最大值，避免同值互相污染。

根据题目描述，我们顺序移动的单元格的值必须严格递增，因此，我们不妨用一个哈希表 $g$ 来记录每个值对应的所有单元格的位置，然后按照值的大小从小到大遍历。

在这个过程中，我们可以维护两个数组 rowMax 和 colMax，分别记录每一行和每一列的最大递增长度。初始时，这两个数组的所有元素都为 $0$。

对于每个值对应的所有单元格位置，我们按照位置顺序遍历，对于每个位置 $(i,j)$，我们可以计算出以该位置为终点的最大递增长度为 $1+max(\mathit{\text{rowMax}}[i],\mathit{\text{colMax}}[j])$，更新答案，然后更新 rowMax[i] 和 colMax[j]。

最后返回答案即可。

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

func maxIncreasingCells(mat [][]int) (ans int) {
	m, n := len(mat), len(mat[0])
	g := map[int][][2]int{}
	for i, row := range mat {
		for j, v := range row {
			g[v] = append(g[v], [2]int{i, j})
		}
	}
	nums := make([]int, 0, len(g))
	for k := range g {
		nums = append(nums, k)
	}
	sort.Ints(nums)
	rowMax := make([]int, m)
	colMax := make([]int, n)
	for _, k := range nums {
		pos := g[k]
		mx := make([]int, len(pos))
		for i, p := range pos {
			mx[i] = max(rowMax[p[0]], colMax[p[1]]) + 1
			ans = max(ans, mx[i])
		}
		for i, p := range pos {
			rowMax[p[0]] = max(rowMax[p[0]], mx[i])
			colMax[p[1]] = max(colMax[p[1]], mx[i])
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2719. 统计整数数目

困难1 种解法

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

题目、示例与约束

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

• num1 <= x <= num2
• min_sum <= digit_sum(x) <= max_sum.

请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后的结果。

注意，digit_sum(x) 表示 x 各位数字之和。

 

示例 1：

输入：num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
输出：11
解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。

示例 2：

输入：num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
输出：5
解释：数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。

 

提示：

• 1 <= num1 <= num2 <= 1022
• 1 <= min_sum <= max_sum <= 400

方法一：数位 DP · Go 实现

思考

统计 $[num1,num2]$ 中数位和落在 $[min\mathrm{\_}sum,max\mathrm{\_}sum]$ 的个数。区间长度可达 ${10}^{22}$ 量级，枚举整数不可行。

转化为 $[0,num2]$ 与 $[0,num1-1]$ 的差。数位 DP 按高位到低位填写，状态为 $(pos,s,limit)$：已放位数、当前数位和、是否贴上界。末位时判断 $s$ 是否落在给定闭区间，记忆化后对 ${10}^9+7$ 取模。

题目实际上求的是区间 $[num1,..num2]$ 中，数位和在 $[min\mathrm{\_}sum,..max\mathrm{\_}sum]$ 的数的个数。对于这种区间 $[l,..r]$ 的问题，我们可以考虑转化为求 $[1,..r]$ 和 $[1,..l-1]$ 的答案，然后相减即可。

对于 $[1,..r]$ 的答案，我们可以使用数位 DP 来求解。我们设计一个函数 $dfs(pos,s,limit)$ 表示当前处理到第 $pos$ 位，数位和为 $s$，当前数是否有上界限制 $limit$ 的方案数。其中 $pos$ 从高到低枚举。

对于 $dfs(pos,s,limit)$，我们可以枚举当前数位 $i$ 的值，然后递归计算 $dfs(pos+1,s+i,limit\bigcap i==up)$，其中 $up$ 表示当前数位的上界。如果 $limit$ 为真，那么 $up$ 就是当前数位的上界，否则 $up$ 为 $9$。如果 $pos$ 大于等于 $num$ 的长度，那么我们就可以判断 $s$ 是否在 $[min\mathrm{\_}sum,..max\mathrm{\_}sum]$ 的范围内，如果在就返回 $1$，否则返回 $0$。

时间复杂度 $O(10\times n\times max\mathrm{\_}sum)$，空间复杂度 $O(n\times max\mathrm{\_}sum)$。其中 $n$ 表示 $num$ 的长度。

相似题目：

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

func count(num1 string, num2 string, min_sum int, max_sum int) int {
	const mod = 1e9 + 7
	f := [23][220]int{}
	for i := range f {
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	num := num2
	var dfs func(int, int, bool) int
	dfs = func(pos, s int, limit bool) int {
		if pos >= len(num) {
			if s >= min_sum && s <= max_sum {
				return 1
			}
			return 0
		}
		if !limit && f[pos][s] != -1 {
			return f[pos][s]
		}
		var ans int
		up := 9
		if limit {
			up = int(num[pos] - '0')
		}
		for i := 0; i <= up; i++ {
			ans = (ans + dfs(pos+1, s+i, limit && i == up)) % mod
		}
		if !limit {
			f[pos][s] = ans
		}
		return ans
	}
	a := dfs(0, 0, true)
	t := []byte(num1)
	for i := len(t) - 1; i >= 0; i-- {
		if t[i] != '0' {
			t[i]--
			break
		}
		t[i] = '9'
	}
	num = string(t)
	f = [23][220]int{}
	for i := range f {
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	b := dfs(0, 0, true)
	return (a - b + mod) % mod
}

力扣原题 · Doocs 题解来源

2741. 特别的排列

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：

• 对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。

请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余 后返回。

 

示例 1：

输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。

示例 2：

输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。

 

提示：

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

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

思考

统计满足相邻元素互相整除的排列数。 $n\le 14$，全排列 $n!$ 偏大，但已用集合与末项决定后续选择。

令 $f[i][j]$ 表示已选掩码为 $i$、末项下标为 $j$ 的方案数。单点掩码为 $1$，否则枚举上一项 $k$，在整除条件成立时从 $f[i\oplus 2^j][k]$ 转移。对满掩码求和并取模。

我们注意到题目中数组的长度最大不超过 $14$，因此，我们可以用一个二进制整数来表示当前的状态，其中第 $i$ 位为 $1$ 表示数组中的第 $i$ 个数已经被选取，为 $0$ 表示数组中的第 $i$ 个数还未被选取。

我们定义 $f[i][j]$ 表示当前选取的整数状态为 $i$，且最后一个选取的整数下标为 $j$ 的方案数。初始时 $f[0][0]=0$，答案为 $\sum _{j=0}^{n-1}f[2^n-1][j]$。

考虑 $f[i][j]$，如果当前只有一个数被选取，那么 $f[i][j]=1$。否则，我们可以枚举上一个选择的数的下标 $k$，如果 $k$ 与 $j$ 对应的数满足题目要求，那么 $f[i][j]$ 可以从 $f[i\oplus 2^j][k]$ 转移而来。即：

$$f[i][j]=\{\begin{array}{ll}1,& i=2^j\\ \sum _{k=0}^{n-1}f[i\oplus 2^j][k],& i\ne 2^j\mathit{\text{且}}\mathit{\text{nums}}[j]\mathit{\text{与}}\mathit{\text{nums}}[k]\mathit{\text{满足题目要求}}\end{array}$$

最终答案即为 $\sum _{j=0}^{n-1}f[2^n-1][j]$。注意答案可能很大，需要对 ${10}^9+7$ 取模。

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

func specialPerm(nums []int) (ans int) {
	const mod int = 1e9 + 7
	n := len(nums)
	m := 1 << n
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	for i := 1; i < m; i++ {
		for j, x := range nums {
			if i>>j&1 == 1 {
				ii := i ^ (1 << j)
				if ii == 0 {
					f[i][j] = 1
					continue
				}
				for k, y := range nums {
					if x%y == 0 || y%x == 0 {
						f[i][j] = (f[i][j] + f[ii][k]) % mod
					}
				}
			}
		}
	}
	for _, x := range f[m-1] {
		ans = (ans + x) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

2742. 给墙壁刷油漆

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

• 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
• 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少。

 

示例 1：

输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。

示例 2：

输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。

 

提示：

• 1 <= cost.length <= 500
• cost.length == time.length
• 1 <= cost[i] <= 106
• 1 <= time[i] <= 500

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

思考

付费油漆匠刷第 $i$ 面墙花费 $cost[i]$ 并耗时 $time[i]$，其间免费匠可刷同样数量的墙。枚举付费集合后验证时间，子集数为 $2^n$、 $n\le 500$，不可行。

从左到右决定当前墙给谁刷：付给费匠则剩余免费额度增加 $time[i]$，给免费匠则额度减 $1$。状态 $(i,j)$ 表示从第 $i$ 面起、当前免费时能为 $j$ 的最少花费；剩余墙数不超过 $j$ 时花费为 $0$。记忆化后复杂度与 $n^2$ 同阶。

我们可以考虑每一堵墙是给付费油漆匠刷还是给免费油漆匠刷，设计一个函数 $dfs(i,j)$，表示从第 $i$ 堵墙开始，且当前剩余的免费油漆匠工作时间为 $j$ 时，刷完剩余所有墙壁的最小开销。那么答案为 $dfs(0,0)$。

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

• 如果 $n-i\le j$，表示剩余的墙壁不超过免费油漆匠的工作时间，那么剩余的墙壁都由免费油漆匠刷，开销为 $0$；
• 如果 $i\ge n$，返回 $+\mathrm{\infty }$；
• 否则，如果第 $i$ 堵墙由付费油漆匠刷，开销为 $cost[i]$，那么 $dfs(i,j)=dfs(i+1,j+time[i])+cost[i]$；如果第 $i$ 堵墙由免费油漆匠刷，开销为 $0$，那么 $dfs(i,j)=dfs(i+1,j-1)$。

注意，参数 $j$ 可能小于 $0$，因此，在实际编码过程中，除了 $Python$ 语言外，我们对 $j$ 加上一个偏移量 $n$，使得 $j$ 的取值范围为 $[0,2n]$。

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

func paintWalls(cost []int, time []int) int {
	n := len(cost)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n<<1|1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if n-i <= j-n {
			return 0
		}
		if i >= n {
			return 1 << 30
		}
		if f[i][j] == -1 {
			f[i][j] = min(dfs(i+1, j+time[i])+cost[i], dfs(i+1, j-1))
		}
		return f[i][j]
	}
	return dfs(0, n)
}

力扣原题 · Doocs 题解来源

2745. 构造最长的新字符串

中等1 种解法

标签：贪心、脑筋急转弯、数学、动态规划

题目、示例与约束

给你三个整数 x ，y 和 z 。

这三个整数表示你有 x 个 "AA" 字符串，y 个 "BB" 字符串，和 z 个 "AB" 字符串。你需要选择这些字符串中的部分字符串（可以全部选择也可以一个都不选择），将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 "AAA" 或者 "BBB" 。

请你返回 新字符串的最大可能长度。

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

 

示例 1：

输入：x = 2, y = 5, z = 1
输出：12
解释： 我们可以按顺序连接 "BB" ，"AA" ，"BB" ，"AA" ，"BB" 和 "AB" ，得到新字符串 "BBAABBAABBAB" 。
字符串长度为 12 ，无法得到一个更长的符合题目要求的字符串。

示例 2：

输入：x = 3, y = 2, z = 2
输出：14
解释：我们可以按顺序连接 "AB" ，"AB" ，"AA" ，"BB" ，"AA" ，"BB" 和 "AA" ，得到新字符串 "ABABAABBAABBAA" 。
字符串长度为 14 ，无法得到一个更长的符合题目要求的字符串。

 

提示：

• 1 <= x, y, z <= 50

方法一：分类讨论 · Go 实现

思考

用 $x$ 个 $AA$、 $y$ 个 $BB$、 $z$ 个 $AB$ 拼接，要求不出现 $AAA$ 或 $BBB$，求最长长度。搜索拼接顺序在数量达 $50$ 时状态偏多。

$AB$ 两端都安全，可任意穿插； $AA$ 与 $BB$ 必须交替。较多的那种至多比另一种多一个，否则会相邻冲突。按 $x$ 与 $y$ 的大小关系写成闭式即可。

我们观察发现，字符串 'AA' 之后只能跟 'BB'，而字符串 'AB' 可以放在字符串开头或结尾。因此：

• 如果 $x<y$，那么我们可以先交替放置 'BBAABBAA..BB'，一共放置 $x$ 个 'AA' 和 $x+1$ 个 'BB'，然后放置剩余的 $z$ 个 'AB'，总长度为 $(x\times 2+z+1)\times 2$；
• 如果 $x>y$，那么我们可以先交替放置 'AABBAABB..AA'，一共放置 $y$ 个 'BB' 和 $y+1$ 个 'AA'，然后放置剩余的 $z$ 个 'AB'，总长度为 $(y\times 2+z+1)\times 2$；
• 如果 $x=y$，我们只需要交替放置 'AABB'，一共放置 $x$ 个 'AA' 和 $y$ 个 'BB'，然后放置剩余的 $z$ 个 'AB'，总长度为 $(x+y+z)\times 2$。

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

func longestString(x int, y int, z int) int {
	if x < y {
		return (x*2 + z + 1) * 2
	}
	if x > y {
		return (y*2 + z + 1) * 2
	}
	return (x + y + z) * 2
}

力扣原题 · Doocs 题解来源

2746. 字符串连接删减字母

中等2 种解法

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

题目、示例与约束

给你一个下标从 0 开始的数组 words ，它包含 n 个字符串。

定义 连接 操作 join(x, y) 表示将字符串 x 和 y 连在一起，得到 xy 。如果 x 的最后一个字符与 y 的第一个字符相等，连接后两个字符中的一个会被 删除 。

比方说 join("ab", "ba") = "aba" ， join("ab", "cde") = "abcde" 。

你需要执行 n - 1 次 连接 操作。令 str0 = words[0] ，从 i = 1 直到 i = n - 1 ，对于第 i 个操作，你可以执行以下操作之一：

• 令 stri = join(stri - 1, words[i])
• 令 stri = join(words[i], stri - 1)

你的任务是使 strn - 1 的长度 最小 。

请你返回一个整数，表示 strn - 1 的最小长度。

 

示例 1：

输入：words = ["aa","ab","bc"]
输出：4
解释：这个例子中，我们按以下顺序执行连接操作，得到 str2 的最小长度：
str0 = "aa"
str1 = join(str0, "ab") = "aab"
str2 = join(str1, "bc") = "aabc" 
str2 的最小长度为 4 。

示例 2：

输入：words = ["ab","b"]
输出：2
解释：这个例子中，str0 = "ab"，可以得到两个不同的 str1：
join(str0, "b") = "ab" 或者 join("b", str0) = "bab" 。
第一个字符串 "ab" 的长度最短，所以答案为 2 。

示例 3：

输入：words = ["aaa","c","aba"]
输出：6
解释：这个例子中，我们按以下顺序执行连接操作，得到 str2 的最小长度：
str0 = "aaa"
str1 = join(str0, "c") = "aaac"
str2 = join("aba", str1) = "abaaac"
str2 的最小长度为 6 。

 

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 50
• words[i] 中只包含小写英文字母。

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

思考

按给定顺序把单词接到当前串的左端或右端，相邻端点相同则删一个字符，求最短终长。每步两种选择，深度为 $n\le 1000$，裸搜索不可行。

终长只依赖已接串的首尾字符。 $dfs(i,a,b)$ 表示从第 $i$ 个词起、当前首尾为 $a,b$ 时还需付出的最小长度；接到右侧比较 $s[0]$ 与 $b$，接到左侧比较 $s[-1]$ 与 $a$。记忆化后状态为 $O(n\cdot {26}^2)$。

我们注意到，字符串连接时，字符串的第一个字符和最后一个字符会影响到连接后字符串的长度。因此，我们设计一个函数 $dfs(i,a,b)$，表示从第 $i$ 个字符串开始连接，且此前已经连接的字符串的第一个字符为 $a$，最后一个字符为 $b$ 时，连接后字符串的最小长度。

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

• 如果 $i=n$，说明所有字符串已经连接完毕，返回 $0$；
• 否则，我们考虑将第 $i$ 个字符串连接到已经连接的字符串的末尾或者开头，得到连接后字符串的长度 $x$ 和 $y$，则 $dfs(i,a,b)=min(x,y)+|words[i]|$。

为了避免重复计算，我们使用记忆化搜索的方法。具体地，我们使用一个三维数组 $f$ 存储所有的 $dfs(i,a,b)$ 的返回值。当我们需要计算 $dfs(i,a,b)$ 时，如果 $f[i][a][b]$ 已经被计算过，我们直接返回 $f[i][a][b]$；否则我们按照上述的递推关系计算 $dfs(i,a,b)$ 的值，并将其存入 $f[i][a][b]$ 中。

在主函数中，我们直接返回 $|words[0]|+dfs(1,words[0][0],words[0][|words[0]|-1])$。

时间复杂度 $O(n\times C^2)$，空间复杂度 $O(n\times C^2)$，其中 $C$ 表示字符串的最大长度。

func minimizeConcatenatedLength(words []string) int {
	n := len(words)
	f := make([][26][26]int, n)
	var dfs func(i, a, b int) int
	dfs = func(i, a, b int) int {
		if i >= n {
			return 0
		}
		if f[i][a][b] > 0 {
			return f[i][a][b]
		}
		s := words[i]
		m := len(s)
		x := dfs(i+1, a, int(s[m-1]-'a'))
		y := dfs(i+1, int(s[0]-'a'), b)
		if int(s[0]-'a') == b {
			x--
		}
		if int(s[m-1]-'a') == a {
			y--
		}
		f[i][a][b] = m + min(x, y)
		return f[i][a][b]
	}
	return len(words[0]) + dfs(1, int(words[0][0]-'a'), int(words[0][len(words[0])-1]-'a'))
}

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

思考

每个词只能接到当前串的左端或右端，相邻字母相同就少记一个字符。单词个数可以到 $1000$，而先尝试接到右端时下标总是加一，递归深度就是 $n$。已经接好的串对后面的影响只剩首尾两个字母。于是令 $f[i][a][b]$ 为从第 $i$ 个词起、当前首尾为 $a,b$ 时还要增加的最短长度， $f[n]$ 为 $0$，再按 $i$ 从大到小、枚举全部首尾填写。

设 $f[i][a][b]$ 表示从第 $i$ 个单词开始连接，且此前字符串的首字符为 $a$、尾字符为 $b$ 时，还能增加的最短长度。边界 $f[n][a][b]=0$。从 $i=n-1$ 递减到 $1$，对每个首尾 $a,b$ 考虑两种接法：把 $words[i]$ 接到右侧时，若它的首字符等于 $b$ 则少一个字符，新的尾字符是它的末字符；接到左侧时，若它的末字符等于 $a$ 则少一个字符，新的首字符是它的首字符。 $f[i][a][b]$ 取两种接法中较短的那个，再加上 $|words[i]|$。答案为 $|words[0]|+f[1][words[0][0]][words[0][|words[0]|-1]]$。

时间复杂度 $O(n\times |\mathrm{\Sigma }{|}^2)$，空间复杂度 $O(n\times |\mathrm{\Sigma }{|}^2)$。其中 $n$ 为单词个数， $|\mathrm{\Sigma }|$ 为字符集大小，本题中 $|\mathrm{\Sigma }|=26$。

func minimizeConcatenatedLength(words []string) int {
	n := len(words)
	f := make([][26][26]int, n+1)
	for i := n - 1; i > 0; i-- {
		s := words[i]
		m := len(s)
		c := int(s[0] - 'a')
		d := int(s[m-1] - 'a')
		for a := 0; a < 26; a++ {
			for b := 0; b < 26; b++ {
				x := f[i+1][a][d]
				y := f[i+1][c][b]
				if c == b {
					x--
				}
				if d == a {
					y--
				}
				f[i][a][b] = m + min(x, y)
			}
		}
	}
	a := int(words[0][0] - 'a')
	b := int(words[0][len(words[0])-1] - 'a')
	return len(words[0]) + f[1][a][b]
}

力扣原题 · Doocs 题解来源

2750. 将数组划分成若干好子数组的方式

中等1 种解法

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

题目、示例与约束

给你一个二元数组 nums 。

如果数组中的某个子数组 恰好 只存在 一 个值为 1 的元素，则认为该子数组是一个 好子数组 。

请你统计将数组 nums 划分成若干 好子数组 的方法数，并以整数形式返回。由于数字可能很大，返回其对 109 + 7 取余 之后的结果。

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

 

示例 1：

输入：nums = [0,1,0,0,1]
输出：3
解释：存在 3 种可以将 nums 划分成若干好子数组的方式：
- [0,1] [0,0,1]
- [0,1,0] [0,1]
- [0,1,0,0] [1]

示例 2：

输入：nums = [0,1,0]
输出：1
解释：存在 1 种可以将 nums 划分成若干好子数组的方式：
- [0,1,0]

 

提示：

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

方法一：乘法原理 · Go 实现

思考

好子数组恰好含一个 $1$，求把数组切成若干好子数组的方案数。切分位置由 $1$ 的分布完全决定，不必枚举所有断点组合。

相邻两个 $1$ 之间有 $i-j$ 个可放置分割线的空隙（含「贴在右侧 $1$ 左边」），各段选择互相独立，方案数是这些空隙数之积。没有 $1$ 则无法划分，答案为 $0$。

根据题目描述，我们可以在两个 $1$ 之间画一条分割线，假设两个 $1$ 之间的下标分别为 $j$ 和 $i$，那么可以画的不同分割线的数量为 $i-j$。我们找出所有满足条件的 $j$ 和 $i$，然后将所有的 $i-j$ 相乘即可。如果找不到两个 $1$ 之间的分割线，那么说明数组中不存在 $1$，此时答案为 $0$。

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

func numberOfGoodSubarraySplits(nums []int) int {
	const mod int = 1e9 + 7
	ans, j := 1, -1
	for i, x := range nums {
		if x == 0 {
			continue
		}
		if j > -1 {
			ans = ans * (i - j) % mod
		}
		j = i
	}
	if j == -1 {
		return 0
	}
	return ans
}

力扣原题 · Doocs 题解来源

2767. 将字符串分割为最少的美丽子字符串

中等1 种解法

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

题目、示例与约束

给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串  ，使每个子字符串都是 美丽 的。

如果一个字符串满足以下条件，我们称它是 美丽 的：

• 它不包含前导 0 。
• 它是 5 的幂的 二进制 表示。

请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串，请你返回 -1 。

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

 

示例 1：

输入：s = "1011"
输出：2
解释：我们可以将输入字符串分成 ["101", "1"] 。
- 字符串 "101" 不包含前导 0 ，且它是整数 51 = 5 的二进制表示。
- 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 2 个美丽子字符串。

示例 2：

输入：s = "111"
输出：3
解释：我们可以将输入字符串分成 ["1", "1", "1"] 。
- 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 3 个美丽子字符串。

示例 3：

输入：s = "0"
输出：-1
解释：无法将给定字符串分成任何美丽子字符串。

 

提示：

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

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

思考

把二进制串切成尽量少的段，每段无前导零且值为 $5$ 的幂。枚举切分在 $n\le 15$ 下可行，但带前导零的非法前缀应立刻剪枝。

预处理长度范围内所有 $5$ 的幂。 $dfs(i)$ 从下标 $i$ 起的最少段数：若 $s[i]=0$ 则非法；否则向右累加二进制值，落在幂集合中则尝试 $1+dfs(j+1)$。记忆化后取不到有限值则返回 $-1$。

题目中需要判断一个字符串是否是 $5$ 的幂的二进制表示，因此，我们不妨先预处理出所有 $5$ 的幂的数字，记录在哈希表 $ss$ 中。

接下来，我们设计一个函数 $dfs(i)$，表示从字符串 $s$ 的第 $i$ 个字符开始，到字符串末尾的最少分割次数。那么答案就是 $dfs(0)$。

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

• 如果 $i\ge n$，表示已经处理完了所有字符，那么答案就是 $0$；
• 如果 $s[i]=0$，表示当前字符串包含前导 $0$，不符合美丽字符串的定义，因此答案是无穷大；
• 否则，我们从 $i$ 开始枚举子字符串的结束位置 $j$，用 $x$ 表示子字符串 $s[i..j]$ 的十进制值，如果 $x$ 在哈希表 $ss$ 中，那么我们就可以将 $s[i..j]$ 作为一个美丽子字符串，此时答案就是 $1+dfs(j+1)$。我们需要枚举所有可能的 $j$，并取所有答案中的最小值。

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

在主函数中，我们首先预处理出所有 $5$ 的幂的数字，然后调用 $dfs(0)$，如果返回值为无穷大，那么说明无法将字符串 $s$ 分割成美丽子字符串，答案返回 $-1$，否则返回 $dfs(0)$ 的值。

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

func minimumBeautifulSubstrings(s string) int {
	ss := map[int]bool{}
	n := len(s)
	x := 1
	f := make([]int, n+1)
	for i := 0; i <= n; i++ {
		ss[x] = true
		x *= 5
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if s[i] == '0' {
			return n + 1
		}
		if f[i] != -1 {
			return f[i]
		}
		f[i] = n + 1
		x := 0
		for j := i; j < n; j++ {
			x = x<<1 | int(s[j]-'0')
			if ss[x] {
				f[i] = min(f[i], 1+dfs(j+1))
			}
		}
		return f[i]
	}
	ans := dfs(0)
	if ans > n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2770. 达到末尾下标所需的最大跳跃次数

中等2 种解法

标签：数组、动态规划

题目、示例与约束

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

你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：

• 0 <= i < j < n
• -target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ，返回 -1 。

 

示例 1：

输入：nums = [1,3,6,4,1,2], target = 2
输出：3
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。 

示例 2：

输入：nums = [1,3,6,4,1,2], target = 3
输出：5
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 2 。 
- 从下标 2 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 4 。 
- 从下标 4 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。 

示例 3：

输入：nums = [1,3,6,4,1,2], target = 0
输出：-1
解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。 

 

提示：

• 2 <= nums.length == n <= 1000
• -109 <= nums[i] <= 109
• 0 <= target <= 2 * 109

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

思考

从 $0$ 跳到末下标，一步要求值差的绝对值不超过 $target$，求最多跳数。 $n\le 1000$，若用最短路思想会得到最少跳数，与题意相反。

$dfs(i)$ 为从 $i$ 出发的最多跳数：枚举合法的 $j>i$ 取 $1+dfs(j)$ 的最大，到终点为 $0$，无路则为负无穷。记忆化后若结果为负则返回 $-1$。

对于每个位置 $i$，我们考虑向后搜索能跳到的位置 $j$，如果满足 $|nums[i]-nums[j]|\le target$，那么我们就可以从 $i$ 跳到 $j$，并且从 $j$ 开始继续向后搜索。

因此，我们设计一个函数 $dfs(i)$，表示从位置 $i$ 开始跳跃到末尾下标所需的最大跳跃次数。那么答案就是 $dfs(0)$。

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

• 如果 $i=n-1$，那么我们已经到达了末尾下标，不需要跳跃，因此返回 $0$；
• 否则，我们需要枚举从位置 $i$ 开始能跳到的位置 $j$，并计算从 $j$ 开始跳跃到末尾下标所需的最大跳跃次数，那么 $dfs(i)$ 就等于所有 $dfs(j)$ 中的最大值加 $1$。如果不存在从 $i$ 开始能跳到的位置 $j$，那么 $dfs(i)=-\mathrm{\infty }$。

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

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

func maximumJumps(nums []int, target int) int {
	n := len(nums)
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i == n-1 {
			return 0
		}
		if f[i] != -1 {
			return f[i]
		}
		f[i] = -(1 << 30)
		for j := i + 1; j < n; j++ {
			if abs(nums[i]-nums[j]) <= target {
				f[i] = max(f[i], 1+dfs(j))
			}
		}
		return f[i]
	}
	ans := dfs(0)
	if ans < 0 {
		return -1
	}
	return ans
}

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

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

思考

枚举全部跳跃序列是指数级的。数组长度可以到 $1000$，而相邻元素之差不超过 $target$ 时，第一次总会先跳到下一个下标，递归深度就是 $n$。从位置 $i$ 出发的最多跳数只依赖更靠右的位置。于是令 $f[i]$ 为从 $i$ 到末尾的最多跳数， $f[n-1]=0$，从右往左枚举合法落点 $j$，用 $1+f[j]$ 更新；若 $f[0]$ 仍为负，说明到不了终点，返回 $-1$。

设 $f[i]$ 为从下标 $i$ 跳到末尾的最多跳跃次数，边界 $f[n-1]=0$，其余位置先记为 $-\mathrm{\infty }$。从 $i=n-2$ 递减到 $0$，枚举落点 $j$（ $i<j<n$）。若 $|nums[i]-nums[j]|\le target$，则可以用 $1+f[j]$ 更新 $f[i]$。若 $f[0]$ 仍为负，说明无法到达末尾，返回 $-1$，否则返回 $f[0]$。

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

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

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

力扣原题 · Doocs 题解来源