LeetCode Go · 动态规划（11）

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

来源与许可

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

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

2035. 将数组分成两个数组并最小化数组和的差

困难1 种解法

标签：位运算、数组、双指针、二分查找、动态规划、位掩码、有序集合、排序、中途相遇

题目、示例与约束

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。

请你返回 最小 的数组和之差。

 

示例 1：

输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

示例 2：

输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。

示例 3：

输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。

 

提示：

• 1 <= n <= 15
• nums.length == 2 * n
• -107 <= nums[i] <= 107

方法一 · Go 实现

思考

$2n\le 30$，分成两个等长子集使和差最小。全集枚举 $C(30,15)$ 偏紧；折半后每半 $n\le 15$，可枚举选法。

对左右两半，按所选个数 $cnt$ 记录「选中减未选」的和集合。左边选 $i$ 个则右边须选 $n-i$ 个，目标和接近相反数。

将两边集合排序后二分配对，取 $|a+b|$ 最小。 $2^{15}$ 级枚举可接受。

func minimumDifference(nums []int) int {
	n := len(nums) >> 1
	f := make([][]int, n+1)
	g := make([][]int, n+1)
	for i := 0; i < (1 << n); i++ {
		s, cnt := 0, 0
		s1, cnt1 := 0, 0
		for j := 0; j < n; j++ {
			if (i & (1 << j)) != 0 {
				s += nums[j]
				cnt++
				s1 += nums[n+j]
				cnt1++
			} else {
				s -= nums[j]
				s1 -= nums[n+j]
			}
		}
		f[cnt] = append(f[cnt], s)
		g[cnt1] = append(g[cnt1], s1)
	}

	for i := 0; i <= n; i++ {
		sort.Ints(f[i])
		sort.Ints(g[i])
	}
	ans := 1 << 30
	for i := 0; i <= n; i++ {
		for _, a := range f[i] {
			left, right := 0, len(g[n-i])-1
			b := -a
			for left < right {
				mid := (left + right) >> 1
				if g[n-i][mid] >= b {
					right = mid
				} else {
					left = mid + 1
				}
			}
			ans = min(ans, abs(a+g[n-i][left]))
			if left > 0 {
				ans = min(ans, abs(a+g[n-i][left-1]))
			}
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

2036. 最大交替子数组和 🔒

中等1 种解法

标签：数组、动态规划

题目、示例与约束

子数组是以0下标开始的数组的连续非空子序列，从 i 到 j（0 <= i <= j < nums.length）的 子数组交替和 被定义为 nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j] 。

给定一个以0下标开始的整数数组nums，返回它所有可能的交替子数组和的最大值。

 

示例 1：

输入：nums = [3,-1,1,2]
输出：5
解释：
子数组 [3,-1,1]有最大的交替子数组和3 - (-1) + 1 = 5.

示例 2：

输入：nums = [2,2,2,2,2]
输出：2
解释：
子数组 [2], [2,2,2]和 [2,2,2,2,2]有相同的最大交替子数组和为2
[2]: 2.
[2,2,2]: 2 - 2 + 2 = 2.
[2,2,2,2,2]: 2 - 2 + 2 - 2 + 2 = 2.

示例 3：

输入：nums = [1]
输出：1
解释：
仅有一个非空子数组，为 [1]，它的交替子数组和为 1

 

提示：

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

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

思考

交替子数组要求和 $\sum (-1{)}^k{a}_{i+k}$ 最大， $n\le {10}^5$ 不能枚举区间。以右端分类：最后一项带正号或带负号，转移只依赖前一位置的相反状态。

$f$ 表示以 $+nums[i]$ 结尾的最大和， $g$ 表示以 $-nums[i]$ 结尾。新的 $f$ 可接在旧 $g$ 后或单独成段， $g$ 则接在刚算出的 $f$ 上（相当于给上一项改号）。

全程 $O(1)$ 空间滚动，答案为所有 $f,g$ 的最大。

我们定义 $f$ 表示以 $nums[i]$ 结尾的交替子数组的最大和，定义 $g$ 表示以 $-nums[i]$ 结尾的交替子数组的最大和，初始时 $f$ 和 $g$ 均为 $-\mathrm{\infty }$。

接下来，我们遍历数组 $nums$，对于位置 $i$，我们需要维护 $f$ 和 $g$ 的值，即 $f=max(g,0)+nums[i]$，而 $g=f-nums[i]$。答案即为所有 $f$ 和 $g$ 中的最大值。

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

func maximumAlternatingSubarraySum(nums []int) int64 {
	const inf = 1 << 60
	ans, f, g := -inf, -inf, -inf
	for _, x := range nums {
		f, g = max(g, 0)+x, f-x
		ans = max(ans, max(f, g))
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2052. 将句子分隔成行的最低成本 🔒

中等2 种解法

标签：字符串、动态规划

题目、示例与约束

给定一个由空格分隔的单词组成的字符串 sentence 和一个整数 k。你的任务是将 sentence 分成多行，每行中的字符数最多为 k。你可以假设 sentence 不以空格开头或结尾，并且 sentence 中的单词由单个空格分隔。

你可以通过在 sentence 中的单词间插入换行来分隔 sentence 。一个单词不能被分成两行。每个单词只能使用一次，并且单词顺序不能重排。同一行中的相邻单词应该由单个空格分隔，并且每行都不应该以空格开头或结尾。

一行长度为 n 的字符串的分隔成本是 (k - n)2 ，总成本就是除开最后一行以外的其它所有行的分隔成本之和。

• 以 sentence = "i love leetcode" 和k = 12为例：
  • 将sentence 分成 "i", "love", 和"leetcode" 的成本为 (12 - 1)2 + (12 - 4)2 = 185。
  • 将sentence 分成 "i love", 和"leetcode" 的成本为 (12 - 6)2 = 36。
  • 将sentence 分成 "i", 和"love leetcode" 是不可能的，因为 "love leetcode" 的长度大于 k。

返回将sentence分隔成行的最低的可能总成本。

 

示例 1:

输入: sentence = "i love leetcode", k = 12
输出: 36
解释:
将 sentence 分成"i", "love", 和"leetcode" 的成本为 (12 - 1)2 + (12 - 4)2 = 185.
将 sentence 分成"i love", 和"leetcode" 的成本为 (12 - 6)2 = 36.
将 sentence 分成"i", "love leetcode" 是不可能的，因为 "love leetcode" 的长度为 13.
36是最低的可能总成本，因此返回它

示例 2:

输入: sentence = "apples and bananas taste great", k = 7
输出: 21
解释:
将 sentence 分成"apples", "and", "bananas", "taste", 和"great" 的成本为 (7 - 6)2 + (7 - 3)2 + (7 - 7)2 + (7 - 5)2 = 21.
21是最低的可能总成本，因此返回它

示例 3:

输入: sentence = "a", k = 5
输出: 0
解释:
最后一行的成本不包括在总成本中，而sentence只有一行，所以返回0

 

提示:

• 1 <= sentence.length <= 5000
• 1 <= k <= 5000
• sentence 中每个单词长度最大为 k.
• sentence 只包含小写字母和空格.
• sentence 不会以空格开头或结尾.
• sentence 中的单词以单个空格分隔.

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

思考

把单词序列拆成多行，除末行外代价为 $(k-\text{行宽}{)}^2$。单词数不大，但拆法指数级。从第 $i$ 个词起的最小代价只依赖后缀。

前缀和 $s$ 使区间词长与空格数可 $O(1)$ 求得。若剩余整段落进末行则代价 $0$；否则枚举下一行终点 $j$，加上 $(k-m{)}^2$ 与 $dfs(j)$。

记忆化后状态 $n$、转移 $O(n)$。

我们用一个数组 $\mathit{\text{nums}}$ 记录每个单词的长度，数组的长度记为 $n$。然后我们定义一个长度为 $n+1$ 的前缀和数组 $\mathit{\text{s}}$，其中 $\mathit{\text{s}}[i]$ 表示前 $i$ 个单词的长度之和。

接下来，我们设计一个函数 $\mathit{\text{dfs}}(i)$，表示从第 $i$ 个单词开始分隔句子的最小成本。那么答案为 $\mathit{\text{dfs}}(0)$。

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

• 如果从第 $i$ 个单词开始到最后一个单词的长度之和加上单词之间的空格数小于等于 $k$，那么这些单词可以放在最后一行，成本为 $0$。
• 否则，我们枚举下一个开始分隔的单词的位置 $j$，使得从第 $i$ 个单词到第 $j-1$ 个单词的长度之和加上单词之间的空格数小于等于 $k$。那么 $\mathit{\text{dfs}}(j)$ 表示从第 $j$ 个单词开始分隔句子的最小成本，而 $(k-m{)}^2$ 表示将第 $i$ 个单词到第 $j-1$ 个单词放在一行的成本，其中 $m$ 表示从第 $i$ 个单词到第 $j-1$ 个单词的长度之和加上单词之间的空格数。我们枚举所有的 $j$，取最小值即可。

答案即为 $\mathit{\text{dfs}}(0)$。

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

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为单词的个数。

func minimumCost(sentence string, k int) int {
	s := []int{0}
	for _, w := range strings.Split(sentence, " ") {
		s = append(s, s[len(s)-1]+len(w))
	}
	n := len(s) - 1
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if s[n]-s[i]+n-i-1 <= k {
			return 0
		}
		if f[i] != -1 {
			return f[i]
		}
		ans := math.MaxInt32
		for j := i + 1; j < n && s[j]-s[i]+j-i-1 <= k; j++ {
			m := s[j] - s[i] + j - i - 1
			ans = min(ans, dfs(j)+(k-m)*(k-m))
		}
		f[i] = ans
		return ans
	}
	return dfs(0)
}

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

思考

把全部断行枚举一遍是指数级的。句子长度可以到 $5000$，单词很多时，下一行总是从下一个词开始试，递归深度就是单词数。从第 $i$ 个词起的最小代价只依赖更靠后的词。于是用前缀和 $O(1)$ 求出一行的宽度，令 $f[i]$ 为从第 $i$ 个词起的最小代价，剩余单词能放进末行则为 $0$，否则从右往左枚举下一行起点 $j$，加上 $(k-m{)}^2+f[j]$。

用前缀和 $s$ 记录单词长度， $s[i]$ 为前 $i$ 个单词的长度之和， $n$ 为单词个数。设 $f[i]$ 为从第 $i$ 个单词开始排版的最小成本。从 $i=n-1$ 递减到 $0$。若从 $i$ 到末尾的单词长度再加上其间的空格数不超过 $k$，这些词可以放在最后一行， $f[i]=0$。否则枚举下一行的起点 $j$，使第 $i$ 个到第 $j-1$ 个单词连同空格的宽度 $m$ 不超过 $k$，用 $(k-m{)}^2+f[j]$ 更新 $f[i]$。答案为 $f[0]$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为单词的个数。

func minimumCost(sentence string, k int) int {
	s := []int{0}
	for _, w := range strings.Split(sentence, " ") {
		s = append(s, s[len(s)-1]+len(w))
	}
	n := len(s) - 1
	f := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		if s[n]-s[i]+n-i-1 <= k {
			continue
		}
		ans := math.MaxInt32
		for j := i + 1; j < n && s[j]-s[i]+j-i-1 <= k; j++ {
			m := s[j] - s[i] + j - i - 1
			ans = min(ans, f[j]+(k-m)*(k-m))
		}
		f[i] = ans
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

2054. 两个最好的不重叠活动

中等1 种解法

标签：数组、二分查找、动态规划、排序、堆（优先队列）

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，如果你参加这个活动，那么你可以得到价值 valuei 。你 最多 可以参加 两个时间不重叠 活动，使得它们的价值之和 最大 。

请你返回价值之和的 最大值 。

注意，活动的开始时间和结束时间是 包括 在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t ，那么下一个活动必须在 t + 1 或之后的时间开始。

 

示例 1:

输入：events = [[1,3,2],[4,5,2],[2,4,3]]
输出：4
解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

输入：events = [[1,3,2],[4,5,2],[1,5,5]]
输出：5
解释：选择活动 2 ，价值和为 5 。

示例 3：

输入：events = [[1,5,3],[1,5,1],[6,6,5]]
输出：8
解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。

 

提示：

• 2 <= events.length <= 105
• events[i].length == 3
• 1 <= startTimei <= endTimei <= 109
• 1 <= valuei <= 106

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

思考

至多选两个不相交活动，价值最大。 $n\le {10}^5$，枚举对会平方。按开始时间排序后，某个活动之后能接的活动构成后缀，其最大价值可预处理。

$f[i]$ 为从 $i$ 起选一个活动的最大价值。枚举第一个活动，二分第一个开始时间大于其结束时间的下标，加上 $f[idx]$（也可只选一个）。

排序加二分， $O(n\log n)$。

我们可以讲活动按照开始排序，然后预处理出以每个活动为作为开始的最大价值，即 $f[i]$ 表示从第 $i$ 个活动开始，到最后一个活动结束，选择其中一个活动的最大价值。

然后我们枚举每个活动，对于每个活动，我们使用二分查找找到第一个开始时间大于当前活动结束时间的活动，下标记为 $\mathit{\text{idx}}$，那么以当前活动为开始的最大价值就是 $f[\mathit{\text{idx}}]$，加上当前活动的价值，即为以当前活动为第一个活动，最终能获得的最大价值。求最大值即可。

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

func maxTwoEvents(events [][]int) int {
	sort.Slice(events, func(i, j int) bool {
		return events[i][0] < events[j][0]
	})
	n := len(events)
	f := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		f[i] = max(f[i+1], events[i][2])
	}
	ans := 0
	for _, e := range events {
		v := e[2]
		left, right := 0, n
		for left < right {
			mid := (left + right) >> 1
			if events[mid][0] > e[1] {
				right = mid
			} else {
				left = mid + 1
			}
		}
		if left < n {
			v += f[left]
		}
		ans = max(ans, v)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2060. 同源字符串检测

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

原字符串由小写字母组成，可以按下述步骤编码：

• 任意将其 分割 为由若干 非空 子字符串组成的一个 序列 。
• 任意选择序列中的一些元素（也可能不选择），然后将这些元素替换为元素各自的长度（作为一个数字型的字符串）。
• 重新 顺次连接 序列，得到编码后的字符串。

例如，编码 "abcdefghijklmnop" 的一种方法可以描述为：

• 将原字符串分割得到一个序列：["ab", "cdefghijklmn", "o", "p"] 。
• 选出其中第二个和第三个元素并分别替换为它们自身的长度。序列变为 ["ab", "12", "1", "p"] 。
• 重新顺次连接序列中的元素，得到编码后的字符串："ab121p" 。

给你两个编码后的字符串 s1 和 s2 ，由小写英文字母和数字 1-9 组成。如果存在能够同时编码得到 s1 和 s2 原字符串，返回 true ；否则，返回 false。

注意：生成的测试用例满足 s1 和 s2 中连续数字数不超过 3 。

 

示例 1：

输入：s1 = "internationalization", s2 = "i18n"
输出：true
解释："internationalization" 可以作为原字符串
- "internationalization" 
  -> 分割：      ["internationalization"]
  -> 不替换任何元素
  -> 连接：      "internationalization"，得到 s1
- "internationalization"
  -> 分割：      ["i", "nternationalizatio", "n"]
  -> 替换：      ["i", "18",                 "n"]
  -> 连接：      "i18n"，得到 s2

示例 2：

输入：s1 = "l123e", s2 = "44"
输出：true
解释："leetcode" 可以作为原字符串
- "leetcode" 
  -> 分割：       ["l", "e", "et", "cod", "e"]
  -> 替换：       ["l", "1", "2",  "3",   "e"]
  -> 连接：       "l123e"，得到 s1
- "leetcode" 
  -> 分割：       ["leet", "code"]
  -> 替换：       ["4",    "4"]
  -> 连接：       "44"，得到 s2

示例 3：

输入：s1 = "a5b", s2 = "c5b"
输出：false
解释：不存在这样的原字符串
- 编码为 s1 的字符串必须以字母 'a' 开头
- 编码为 s2 的字符串必须以字母 'c' 开头

示例 4：

输入：s1 = "112s", s2 = "g841"
输出：true
解释："gaaaaaaaaaaaas" 可以作为原字符串
- "gaaaaaaaaaaaas"
  -> 分割：       ["g", "aaaaaaaaaaaa", "s"]
  -> 替换：       ["1", "12",           "s"]
  -> 连接：       "112s"，得到 s1
- "gaaaaaaaaaaaas"
  -> 分割：       ["g", "aaaaaaaa", "aaaa", "s"]
  -> 替换：       ["g", "8",        "4",    "1"]
  -> 连接         "g841"，得到 s2

示例 5：

输入：s1 = "ab", s2 = "a2"
输出：false
解释：不存在这样的原字符串
- 编码为 s1 的字符串由两个字母组成
- 编码为 s2 的字符串由三个字母组成

 

提示：

• 1 <= s1.length, s2.length <= 40
• s1 和 s2 仅由数字 1-9 和小写英文字母组成
• s1 和 s2 中连续数字数不超过 3

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：记忆化搜索状态 (i,j,d)，其中 d 是 s1 已处理前缀与 s2 已处理前缀展开长度之差。优先扩展长度较短的一侧；遇到数字时枚举连续数字的各个前缀作为长度，遇到普通字母时抵消另一侧多出的长度。差值为零时可以同步消费相同字符。只有两个字符串都处理完且 d=0 才成功，重复状态直接剪枝。

复杂度：设两个编码串长度为 n、m，差值槽数为 D（源码为 2000）。题目保证连续数字最多三位，因此每个状态只有常数个转移。时间和辅助空间均为 O((n+1)(m+1)D)，递归深度为 O(n+m)，已包含在该空间上界内。

import "unicode"

// github.com/EndlessCheng/codeforces-go
func possiblyEquals(s1, s2 string) bool {
	n, m := len(s1), len(s2)
	const mx, bias = 2000, 1000
	vis := make([][][mx]bool, n+1)
	for i := range vis {
		vis[i] = make([][mx]bool, m+1)
	}
	var dfs func(i, j, d int) bool
	dfs = func(i, j, d int) bool {
		if i == n && j == m {
			return d == 0 // 匹配成功
		}
		if vis[i][j][d+bias] {
			return false
		}
		vis[i][j][d+bias] = true
		// 原始字符串长度相同时，若 s1[i] == s2[j]，则 s1[:i] 和 s2[:j] 均可以向后扩展一个字母
		if d == 0 && i < n && j < m && s1[i] == s2[j] && dfs(i+1, j+1, 0) {
			return true
		}
		if d <= 0 && i < n { // s1[:i] 的原始字符串长度不超过 s2[:j] 的原始字符串长度时，扩展 s1[:i]
			if unicode.IsDigit(rune(s1[i])) { // 数字
				for p, v := i, 0; p < n && unicode.IsDigit(rune(s1[p])); p++ {
					v = v*10 + int(s1[p]&15)
					if dfs(p+1, j, d+v) {
						return true
					}
				}
			} else if d < 0 && dfs(i+1, j, d+1) { // 字符，扩展一位，注意这里需要 d != bias
				return true
			}
		}
		if d >= 0 && j < m { // s2[:j] 的原始字符串长度不超过 s1[:i] 的原始字符串长度时，扩展 s2[:j]
			if unicode.IsDigit(rune(s2[j])) { // 数字
				for q, v := j, 0; q < m && unicode.IsDigit(rune(s2[q])); q++ {
					v = v*10 + int(s2[q]&15)
					if dfs(i, q+1, d-v) {
						return true
					}
				}
			} else if d > 0 && dfs(i, j+1, d-1) { // 字符，扩展一位，注意这里需要 d != bias
				return true
			}
		}
		return false
	}
	return dfs(0, 0, 0)
}

力扣原题 · Doocs 题解来源

2063. 所有子字符串中的元音

中等1 种解法

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

题目、示例与约束

给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。

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

注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。

 

示例 1：

输入：word = "aba"
输出：6
解释：
所有子字符串是："a"、"ab"、"aba"、"b"、"ba" 和 "a" 。
- "b" 中有 0 个元音
- "a"、"ab"、"ba" 和 "a" 每个都有 1 个元音
- "aba" 中有 2 个元音
因此，元音总数 = 0 + 1 + 1 + 1 + 1 + 2 = 6 。

示例 2：

输入：word = "abc"
输出：3
解释：
所有子字符串是："a"、"ab"、"abc"、"b"、"bc" 和 "c" 。
- "a"、"ab" 和 "abc" 每个都有 1 个元音
- "b"、"bc" 和 "c" 每个都有 0 个元音
因此，元音总数 = 1 + 1 + 1 + 0 + 0 + 0 = 3 。

示例 3：

输入：word = "ltcd"
输出：0
解释："ltcd" 的子字符串均不含元音。

示例 4：

输入：word = "noosabasboosa"
输出：237
解释：所有子字符串中共有 237 个元音。

 

提示：

• 1 <= word.length <= 105
• word 由小写英文字母组成

方法一：枚举贡献 · Go 实现

思考

子串个数 $O(n^2)$， $n\le {10}^5$ 不能枚举。每个元音对答案的贡献等于包含它的子串数。下标 $i$ 被 $(i+1)(n-i)$ 个子串覆盖。

只对元音累加该乘积。

我们可以枚举字符串的每个字符 $\mathit{\text{word}}[i]$，如果 $\mathit{\text{word}}[i]$ 是元音字母，那么 $\mathit{\text{word}}[i]$ 一共在 $(i+1)\times (n-i)$ 个子字符串中出现，将这些子字符串的个数累加即可。

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

func countVowels(word string) (ans int64) {
	for i, c := range word {
		if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
			ans += int64((i + 1) * (len(word) - i))
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2086. 喂食仓鼠的最小食物桶数

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的字符串 hamsters ，其中 hamsters[i]  要么是：

• 'H' 表示有一个仓鼠在下标 i ，或者
• '.' 表示下标 i 是空的。

你将要在空的位置上添加一定数量的食物桶来喂养仓鼠。如果仓鼠的左边或右边至少有一个食物桶，就可以喂食它。更正式地说，如果你在位置 i - 1 或者 i + 1 放置一个食物桶，就可以喂养位置为 i 处的仓鼠。

在 空的位置 放置食物桶以喂养所有仓鼠的前提下，请你返回需要的 最少 食物桶数。如果无解请返回 -1 。

 

示例 1：

输入：hamsters = "H..H"
输出：2
解释：
我们可以在下标为 1 和 2 处放食物桶。
可以发现如果我们只放置 1 个食物桶，其中一只仓鼠将得不到喂养。

示例 2：

输入：street = ".H.H."
输出：1
解释：
我们可以在下标为 2 处放置一个食物桶。

示例 3：

输入：street = ".HHH."
输出：-1
解释：
如果我们如图那样在每个空位放置食物桶，下标 2 处的仓鼠将吃不到食物。

 

提示：

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

方法一：贪心 · Go 实现

思考

每只仓鼠须与桶相邻，桶放在空位。从左到右贪心：优先把桶放在仓鼠右侧，这样可能同时喂下一只；右侧无空则用左侧，两侧皆无则无解。

放在右侧时下标多跳一格，避免重复安置。线性扫描。

从左到右遍历字符串，遇到 H 时，优先考虑右边是否有空位，如果有则放置水桶，并且跳过水桶的下一个位置；如果右边没有空位，则考虑左边是否有空位，如果有则放置水桶，否则无解。

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

func minimumBuckets(street string) int {
	ans, n := 0, len(street)
	for i := 0; i < n; i++ {
		if street[i] == 'H' {
			if i+1 < n && street[i+1] == '.' {
				ans++
				i += 2
			} else if i > 0 && street[i-1] == '.' {
				ans++
			} else {
				return -1
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2088. 统计农场中肥沃金字塔的数目

困难1 种解法

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

题目、示例与约束

有一个 矩形网格 状的农场，划分为 m 行 n 列的单元格。每个格子要么是 肥沃的 （用 1 表示），要么是 贫瘠 的（用 0 表示）。网格图以外的所有与格子都视为贫瘠的。

农场中的 金字塔 区域定义如下：

1. 区域内格子数目 大于 1 且所有格子都是 肥沃的 。
2. 金字塔 顶端 是这个金字塔 最上方 的格子。金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ，那么金字塔区域内包含的任一格子 (i, j) 需满足 r <= i <= r + h - 1 且 c - (i - r) <= j <= c + (i - r) 。

一个 倒金字塔 类似定义如下：

1. 区域内格子数目 大于 1 且所有格子都是 肥沃的 。
2. 倒金字塔的 顶端 是这个倒金字塔 最下方 的格子。倒金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ，那么金字塔区域内包含的任一格子 (i, j) 需满足 r - h + 1 <= i <= r 且 c - (r - i) <= j <= c + (r - i) 。

下图展示了部分符合定义和不符合定义的金字塔区域。黑色区域表示肥沃的格子。

给你一个下标从 0 开始且大小为 m x n 的二进制矩阵 grid ，它表示农场，请你返回 grid 中金字塔和倒金字塔的 总数目 。

 

示例 1：

  

输入：grid = [[0,1,1,0],[1,1,1,1]]
输出：2
解释：
2 个可能的金字塔区域分别如上图蓝色和红色区域所示。
这个网格图中没有倒金字塔区域。
所以金字塔区域总数为 2 + 0 = 2 。

示例 2：

  

输入：grid = [[1,1,1],[1,1,1]]
输出：2
解释：
金字塔区域如上图蓝色区域所示，倒金字塔如上图红色区域所示。
所以金字塔区域总数目为 1 + 1 = 2 。

示例 3：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：0
解释：
网格图中没有任何金字塔或倒金字塔区域。

示例 4：

   

输入：grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
输出：13
解释：
有 7 个金字塔区域。上图第二和第三张图中展示了它们中的 3 个。
有 6 个倒金字塔区域。上图中最后一张图展示了它们中的 2 个。
所以金字塔区域总数目为 7 + 6 = 13.

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 105
• grid[i][j] 要么是 0 ，要么是 1 。

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

思考

金字塔由下方三格支撑，高度可递推。 $mn\le {10}^5$，不能枚举每个顶点再验证。 $f[i][j]$ 表示以该格为顶的最大高度（单元格本身高度 $0$ 不算一座）。

自底向上：若为肥沃且非边界，则高度为下方三格高度的最小加一，并把高度累入答案（高度 $h$ 对应 $h$ 座不同大小的塔）。倒金字塔自上而下同样转移，复用数组。

我们定义 $f[i][j]$ 表示以 $(i,j)$ 为顶点的金字塔的最大高度，那么有如下状态转移方程：

$$f[i][j]=\{\begin{array}{ll}0& \mathit{\text{grid}}[i][j]=0\\ min(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+1& \mathit{\text{grid}}[i][j]=1\end{array}$$

因此，我们可以从下往上、从左往右遍历网格，计算出所有的 $f[i][j]$，并累加所有的 $f[i][j]$ 即可得到正金字塔的个数。

接下来，我们考虑倒金字塔的个数。与金字塔类似，我们定义 $g[i][j]$ 表示以 $(i,j)$ 为顶点的倒金字塔的最大高度，那么有如下状态转移方程：

$$g[i][j]=\{\begin{array}{ll}0& \mathit{\text{grid}}[i][j]=0\\ min(g[i-1][j-1],g[i-1][j],g[i-1][j+1])+1& \mathit{\text{grid}}[i][j]=1\end{array}$$

因此，我们可以从上往下、从左往右遍历网格，计算出所有的 $g[i][j]$，并累加所有的 $g[i][j]$ 即可得到倒金字塔的个数。

最后，正金字塔的个数加上倒金字塔的个数即为答案。实际代码中，我们可以只用一个二维数组 $f[i][j]$ 即可。

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

func countPyramids(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	for i := m - 1; i >= 0; i-- {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 {
				f[i][j] = -1
			} else if i == m-1 || j == 0 || j == n-1 {
				f[i][j] = 0
			} else {
				f[i][j] = min(f[i+1][j-1], min(f[i+1][j], f[i+1][j+1])) + 1
				ans += f[i][j]
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 {
				f[i][j] = -1
			} else if i == 0 || j == 0 || j == n-1 {
				f[i][j] = 0
			} else {
				f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i-1][j+1])) + 1
				ans += f[i][j]
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2100. 适合野炊的日子

中等1 种解法

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

题目、示例与约束

你和朋友们准备去野炊。给你一个下标从 0 开始的整数数组 security ，其中 security[i] 是第 i 天的建议出行指数。日子从 0 开始编号。同时给你一个整数 time 。

如果第 i 天满足以下所有条件，我们称它为一个适合野炊的日子：

• 第 i 天前和后都分别至少有 time 天。
• 第 i 天前连续 time 天建议出行指数都是非递增的。
• 第 i 天后连续 time 天建议出行指数都是非递减的。

更正式的，第 i 天是一个适合野炊的日子当且仅当：security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

请你返回一个数组，包含 所有 适合野炊的日子（下标从 0 开始）。返回的日子可以 任意 顺序排列。

 

示例 1：

输入：security = [5,3,3,3,5,6,2], time = 2
输出：[2,3]
解释：
第 2 天，我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。
第 3 天，我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。
没有其他日子符合这个条件，所以日子 2 和 3 是适合野炊的日子。

示例 2：

输入：security = [1,1,1,1,1], time = 0
输出：[0,1,2,3,4]
解释：
因为 time 等于 0 ，所以每一天都是适合野炊的日子，所以返回每一天。

示例 3：

输入：security = [1,2,3,4,5,6], time = 2
输出：[]
解释：
没有任何一天的前 2 天建议出行指数是非递增的。
所以没有适合野炊的日子，返回空数组。

 

提示：

• 1 <= security.length <= 105
• 0 <= security[i], time <= 105

方法一 · Go 实现

思考

若对每个候选日 $i$ 再向左右各扫描 $\mathit{\text{time}}$ 天以验证单调性，则单次检查为 $O(\mathit{\text{time}})$，总时间可达 $O(n\cdot \mathit{\text{time}})$。 $n$ 与 $\mathit{\text{time}}$ 均可到 ${10}^5$，该做法无法通过。

注意到「连续非递增 / 非递减」可以沿数组递推：若 $\mathit{\text{security}}[i]\le \mathit{\text{security}}[i-1]$，则自 $i$ 向左的非递增长度比 $i-1$ 多 $1$，否则清零。向右的非递减长度同理。因此每个位置的左右合法天数均可在一次线性扫描中求出。

为此我们分别维护数组 $\mathit{\text{left}}$、 $\mathit{\text{right}}$，再筛选 $min(\mathit{\text{left}}[i],\mathit{\text{right}}[i])\ge \mathit{\text{time}}$ 的下标；若 $n\le 2\cdot \mathit{\text{time}}$ 则不可能同时具备左右各 $\mathit{\text{time}}$ 天，直接返回空数组。

func goodDaysToRobBank(security []int, time int) []int {
	n := len(security)
	if n <= time*2 {
		return []int{}
	}
	left := make([]int, n)
	right := make([]int, n)
	for i := 1; i < n; i++ {
		if security[i] <= security[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if security[i] <= security[i+1] {
			right[i] = right[i+1] + 1
		}
	}
	var ans []int
	for i := time; i < n-time; i++ {
		if time <= left[i] && time <= right[i] {
			ans = append(ans, i)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2110. 股票平滑下跌阶段的数目

中等1 种解法

标签：数组、数学、双指针、动态规划、滑动窗口

题目、示例与约束

给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。

一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。

请你返回 平滑下降阶段 的数目。

 

示例 1：

输入：prices = [3,2,1,4]
输出：7
解释：总共有 7 个平滑下降阶段：
[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]
注意，仅一天按照定义也是平滑下降阶段。

示例 2：

输入：prices = [8,6,7,7]
输出：4
解释：总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7]
由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。

示例 3：

输入：prices = [1]
输出：1
解释：总共有 1 个平滑下降阶段：[1]

 

提示：

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

方法一：双指针 · Go 实现

思考

平滑下降阶段是一段连续下标，且相邻元素恰好相差 $1$。长度为 $L$ 的阶段包含 $L(L+1)/2$ 个非空子段。若枚举所有子数组再验证，时间为 $O(n^2)$，在 $n\le {10}^5$ 时不可行。

最长平滑段互不重叠、可贪心切分：从左端尽量向右延伸，直到相邻差不再为 $1$，该段的子段数可直接用公式计算。

双指针 $i$、 $j$ 划出每一段，累加三角形数后再从 $j$ 开始下一段。

我们定义一个答案变量 $\mathit{\text{ans}}$，初始值为 $0$。

接下来，我们使用双指针 $i$ 和 $j$，分别指向当前平滑下降阶段的第一天和最后一天的下一天。初始时 $i=0$, $j=0$。

从左到右遍历数组 $\mathit{\text{prices}}$，对于每个位置 $i$，我们将 $j$ 向右移动，直到 $j$ 到达数组末尾或者 $\mathit{\text{prices}}[j-1]-\mathit{\text{prices}}[j]\ne 1$ 为止。此时， $\mathit{\text{cnt}}=j-i$ 即为当前平滑下降阶段的长度，我们累加 $\frac{(1+\mathit{\text{cnt}})\times \mathit{\text{cnt}}}{2}$ 到答案变量 $\mathit{\text{ans}}$ 中。接下来将 $i$ 更新为 $j$，继续遍历。

遍历结束后，返回答案变量 $\mathit{\text{ans}}$ 即可。

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

func getDescentPeriods(prices []int) (ans int64) {
	n := len(prices)
	for i, j := 0, 0; i < n; i = j {
		j = i + 1
		for j < n && prices[j-1]-prices[j] == 1 {
			j++
		}
		cnt := j - i
		ans += int64((1 + cnt) * cnt / 2)
	}
	return
}

力扣原题 · Doocs 题解来源

2140. 解决智力问题

中等3 种解法

标签：数组、动态规划

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得  pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

• 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
  • 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

 

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

 

提示：

• 1 <= questions.length <= 105
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 105

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

思考

每题可选做或不做，做则跳过随后 $\mathit{\text{brainpower}}$ 题。子问题重叠，若对每条路径单独展开则为指数级。 $n\le {10}^5$，需线性转移。

从下标 $i$ 出发的最优分只取决于「做第 $i$ 题后跳到 $i+b+1$」与「跳过到 $i+1$」二者之较大者，可用记忆化搜索。

$\mathit{\text{dfs}}(i)$ 返回该最优值，答案为 $\mathit{\text{dfs}}(0)$。

我们设计一个函数 $\mathit{\text{dfs}}(i)$，表示从第 $i$ 个问题开始解决，能够获得的最高分数。那么答案就是 $\mathit{\text{dfs}}(0)$。

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

• 如果 $i\ge n$，表示已经解决完所有问题，返回 $0$；
• 否则，设第 $i$ 个问题的分数为 $p$，需要跳过的问题数为 $b$，那么 $\mathit{\text{dfs}}(i)=max(p+\mathit{\text{dfs}}(i+b+1),\mathit{\text{dfs}}(i+1))$。

为了避免重复计算，我们可以使用记忆化搜索的方法，用一个数组 $f$ 记录所有已经计算过的 $\mathit{\text{dfs}}(i)$ 的值。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是问题的数量。

func mostPoints(questions [][]int) int64 {
	n := len(questions)
	f := make([]int64, n)
	var dfs func(int) int64
	dfs = func(i int) int64 {
		if i >= n {
			return 0
		}
		if f[i] > 0 {
			return f[i]
		}
		p, b := questions[i][0], questions[i][1]
		f[i] = max(int64(p)+dfs(i+b+1), dfs(i+1))
		return f[i]
	}
	return dfs(0)
}

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

思考

后缀最优只依赖更靠后的下标，同一转移从后往前填表即可。

令 $f[i]$ 为从 $i$ 起的最高分，则 $f[i]=max(f[i+1],p+f[i+b+1])$，越界视为 $0$。

自 $n-1$ 递推到 $0$，返回 $f[0]$。

我们定义 $f[i]$ 表示从第 $i$ 个问题开始解决，能够获得的最高分数。那么答案就是 $f[0]$。

考虑 $f[i]$，第 $i$ 个问题的分数为 $p$，需要跳过的问题数为 $b$。如果我们解决了第 $i$ 个问题，那么接下来我们需要解决 $b$ 个问题，因此 $f[i]=p+f[i+b+1]$。如果我们跳过了第 $i$ 个问题，那么接下来我们从第 $i+1$ 个问题开始解决，因此 $f[i]=f[i+1]$。两者取最大值即可。状态转移方程如下：

$$f[i]=max(p+f[i+b+1],f[i+1])$$

我们从后往前计算 $f$ 的值，最后返回 $f[0]$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是问题的数量。

func mostPoints(questions [][]int) int64 {
	n := len(questions)
	f := make([]int64, n+1)
	for i := n - 1; i >= 0; i-- {
		p := int64(questions[i][0])
		if j := i + questions[i][1] + 1; j <= n {
			p += f[j]
		}
		f[i] = max(f[i+1], p)
	}
	return f[0]
}

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

思考

每题可选做或不做，做则跳过随后 $\mathit{\text{brainpower}}$ 题。枚举这些路径是指数级的，而 $n\le {10}^5$。

从下标 $i$ 出发的最高分只依赖更靠后的 $i+1$ 与 $i+b+1$。记忆化搜索仍会先调用下一题再返回，第一条调用链的深度为 $n$，栈会溢出。

从末尾往前走时，更靠后的状态已经就绪。令 $f[i]=max(f[i+1],p+f[i+b+1])$，下标超过 $n$ 记为 $0$。

我们从 $i=n-1$ 填到 $0$，返回 $f[0]$。

我们定义 $f[i]$ 表示从第 $i$ 个问题开始解决，能够获得的最高分数。那么答案就是 $f[0]$。

考虑 $f[i]$，第 $i$ 个问题的分数为 $p$，需要跳过的问题数为 $b$。如果我们解决了第 $i$ 个问题，那么接下来我们需要解决 $b$ 个问题，因此 $f[i]=p+f[i+b+1]$。如果我们跳过了第 $i$ 个问题，那么接下来我们从第 $i+1$ 个问题开始解决，因此 $f[i]=f[i+1]$。两者取最大值即可。状态转移方程如下：

$$f[i]=max(p+f[i+b+1],f[i+1])$$

我们从后往前计算 $f$ 的值，最后返回 $f[0]$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是问题的数量。

func mostPoints(questions [][]int) int64 {
	n := len(questions)
	f := make([]int64, n+1)
	for i := n - 1; i >= 0; i-- {
		p := int64(questions[i][0])
		if j := i + questions[i][1] + 1; j <= n {
			p += f[j]
		}
		f[i] = max(f[i+1], p)
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

2143. 在两个数组的区间中选取数字 🔒

困难1 种解法

标签：数组、动态规划

题目、示例与约束

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

如果一个区间 [l, r] （包含左右端点，0 <= l <= r < n）满足下列条件，那么这个区间就是 平衡 的：

• 对每个在区间 [l, r] 范围内的 i，你需要选取 nums1[i] 或者 nums2[i]；
• 从 nums1 中选取的数字和与从 nums2 中选取的数字和相等。（如果你没有从某个数组中选取任何数字，那么数字和被视为 0）。

如果两个 平衡 的区间 [l1, r1] 和 [l2, r2] 满足下列条件之一，那么它们就是 不同 的：

• l1 != l2
• r1 != r2
• 两个区间中的数字选取情况不同（也就是说，存在至少一个 i，使得在第一个区间中，nums1[i] 被选中, 而在第二个区间中，nums2[i] 被选中，或者相反的情况）。

请返回 不同 的平衡的区间数目。由于答案可能很大，请返回答案 模 109+7 的结果。

 

示例 1:

输入: nums1 = [1,2,5], nums2 = [2,6,3]
输出: 3
解释: 平衡的区间有:
- [0, 1], 我们选取 nums2[0] 和 nums1[1]。
  从 nums1 中选取的数字和与从 nums2 中选取的数字和相等: 2 = 2.
- [0, 2], 我们选取 nums1[0], nums2[1] 和 nums1[2]。
  从 nums1 中选取的数字和与从 nums2 中选取的数字和相等: 1 + 5 = 6。
- [0, 2], 我们选取 nums1[0], nums1[1] 和 nums2[2]。
  从 nums1 中选取的数字和与从 nums2 中选取的数字和相等: 1 + 2 = 3。
注意第二个区间和第三个区间是不同的。
因为在第二个平衡的区间中，我们选取了 nums2[1]，但是在第三个平衡的区间中，我们选取了 nums1[1]。

示例 2：

输入: nums1 = [0,1], nums2 = [1,0]
输出: 4
解释: 平衡的区间有:
- [0, 0], 我们选取 nums1[0]。
  从 nums1 中选取的数字和与从 nums2 中选取的数字和相等: 0 = 0。
- [1, 1], 我们选取 nums2[1]。
  从 nums1 中选取的数字和与从 nums2 中选取的数字和相等: 0 = 0。
- [0, 1], 我们选取 nums1[0] 和 nums2[1]。
  从 nums1 中选取的数字和与从 nums2 中选取的数字和相等: 0 = 0。
- [0, 1], 我们选取 nums2[0] 和 nums1[1]。
  从 nums1 中选取的数字和与从 nums2 中选取的数字和相等: 1 = 1。

 

提示:

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

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

思考

平衡子数组要求从 $\mathit{\text{nums1}}$ 与 $\mathit{\text{nums2}}$ 对应位置各选一侧后两侧和相等。子数组个数为 $O(n^2)$，若每个都真的枚举选法则为指数级。 $n$ 与元素值都不大，可用和差做状态。

以右端 $i$ 结尾、两侧和之差为 $j$ 的方案数可从 $i-1$ 转移：第 $i$ 位选 $\mathit{\text{nums1}}[i]$ 则差加 $a$，选 $\mathit{\text{nums2}}[i]$ 则差减 $b$；该位也可单独作为新区间的起点。差可能为负，平移 $s_2=\sum \mathit{\text{nums2}}$。

$f[i][j]$ 按上述转移，答案累加 $f[i][s_2]$。

我们定义 $f[i][j]$ 表示以第 $i$ 个元素结尾，且从 $nums1$ 中选取的数字和与从 $nums2$ 中选取的数字和之差为 $j$ 的平衡区间的个数。由于差值可能为负数，因此，我们统一将 $j$ 加上 $s_2=\sum _{k=0}^{n-1}nums2[k]$，这样就可以保证 $j$ 为非负整数。

考虑 $f[i][j]$，我们可以单独将第 $i$ 个元素视为一个区间，那么 $f[i][nums1[i]+s_2]$ 和 $f[i][-nums2[i]+s_2]$ 都会增加 $1$。此外，如果 $i>0$，我们也可以将第 $i$ 个元素添加到前面的某个区间中，我们在 $[0,s_1+s_2]$ 范围内枚举 $j$，如果 $j\ge a$，那么 $f[i][j]$ 会增加 $f[i-1][j-a]$，如果 $j+b\le s_1+s_2$，那么 $f[i][j]$ 会增加 $f[i-1][j+b]$。

答案为 $\sum _{i=0}^{n-1}f[i][s_2]$。

时间复杂度 $O(n\times M)$，空间复杂度 $O(n\times M)$。其中 $n$ 和 $M$ 分别为数组 $nums1$ 的长度以及数字和的最大值。

func countSubranges(nums1 []int, nums2 []int) (ans int) {
	n := len(nums1)
	s1, s2 := sum(nums1), sum(nums2)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, s1+s2+1)
	}
	const mod int = 1e9 + 7
	for i, a := range nums1 {
		b := nums2[i]
		f[i][a+s2]++
		f[i][-b+s2]++
		if i > 0 {
			for j := 0; j <= s1+s2; j++ {
				if j >= a {
					f[i][j] = (f[i][j] + f[i-1][j-a]) % mod
				}
				if j+b <= s1+s2 {
					f[i][j] = (f[i][j] + f[i-1][j+b]) % mod
				}
			}
		}
		ans = (ans + f[i][s2]) % mod
	}
	return
}

func sum(nums []int) (ans int) {
	for _, x := range nums {
		ans += x
	}
	return
}

力扣原题 · Doocs 题解来源

2147. 分隔长廊的方案数

困难3 种解法

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

题目、示例与约束

在一个图书馆的走廊里，有一些座位和装饰植物排成一列。给你一个下标从 0 开始，长度为 n 的字符串 corridor ，它包含字母 'S' 和 'P' ，其中每个 'S' 表示一个座位，每个 'P' 表示一株植物。

在下标 0 的左边和下标 n - 1 的右边 已经 分别各放了一个屏风。你还需要额外放置一些屏风。每一个位置 i - 1 和 i 之间（1 <= i <= n - 1），至多能放一个屏风。

请你将走廊用屏风划分为若干段，且每一段内都 恰好有两个座位 ，而每一段内植物的数目没有要求。可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为 不同 方案。

请你返回划分走廊的方案数。由于答案可能很大，请你返回它对 109 + 7 取余 的结果。如果没有任何方案，请返回 0 。

 

示例 1：

输入：corridor = "SSPPSPS"
输出：3
解释：总共有 3 种不同分隔走廊的方案。
上图中黑色的竖线表示已经放置好的屏风。
上图每种方案中，每一段都恰好有 两个 座位。

示例 2：

输入：corridor = "PPSPSP"
输出：1
解释：只有 1 种分隔走廊的方案，就是不放置任何屏风。
放置任何的屏风都会导致有一段无法恰好有 2 个座位。

示例 3：

输入：corridor = "S"
输出：0
解释：没有任何方案，因为总是有一段无法恰好有 2 个座位。

 

提示：

• n == corridor.length
• 1 <= n <= 105
• corridor[i] 要么是 'S' ，要么是 'P' 。

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

思考

每段恰好两把椅子，屏风插在相邻段之间的植物上。走廊很长，按位置决定是否在「已有两椅」时切开，有重叠子问题。

状态 $(i,k)$ 表示考虑到位置 $i$、当前段已有 $k$ 把椅子的方案数。遇到椅子则 $k$ 加一， $k>2$ 非法； $k=2$ 时可选择切开（ $k$ 归零）或继续。记忆化后状态数为 $O(n)$。

答案为 $\mathit{\text{dfs}}(0,0)$。

我们设计一个函数 $\mathit{\text{dfs}}(i,k)$，表示在走廊的第 $i$ 个位置，已经放置了 $k$ 个屏风的情况下，划分走廊的方案数。那么答案就是 $\mathit{\text{dfs}}(0,0)$。

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

如果 $i\ge \mathit{\text{len}}(\mathit{\text{corridor}})$，表示已经遍历完了走廊，此时如果 $k=2$，说明找到了一种划分走廊的方案，返回 $1$，否则返回 $0$；

否则，我们需要考虑当前位置 $i$ 的情况：

• 如果 $\mathit{\text{corridor}}[i]=\text{’S’}$，表示当前位置是一个座位，我们将 $k$ 加 $1$；
• 如果 $k>2$，表示当前位置放置的屏风数量超过了 $2$，返回 $0$；
• 否则，我们可以选择不放置屏风，即 $\mathit{\text{dfs}}(i+1,k)$；如果 $k=2$，我们还可以选择放置屏风，即 $\mathit{\text{dfs}}(i+1,0)$；我们将这两种情况的结果相加并取模 ${10}^9+7$，即 $\mathit{\text{ans}}=(\mathit{\text{ans}}+\mathit{\text{dfs}}(i+1,k))mod\text{mod}$。

最后，我们返回 $\mathit{\text{dfs}}(0,0)$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是走廊的长度。

func numberOfWays(corridor string) int {
	n := len(corridor)
	f := make([][3]int, n)
	for i := range f {
		f[i] = [3]int{-1, -1, -1}
	}
	const mod = 1e9 + 7
	var dfs func(int, int) int
	dfs = func(i, k int) int {
		if i >= n {
			if k == 2 {
				return 1
			}
			return 0
		}
		if f[i][k] != -1 {
			return f[i][k]
		}
		if corridor[i] == 'S' {
			k++
		}
		if k > 2 {
			return 0
		}
		f[i][k] = dfs(i+1, k)
		if k == 2 {
			f[i][k] = (f[i][k] + dfs(i+1, 0)) % mod
		}
		return f[i][k]
	}
	return dfs(0, 0)
}

方法二：数学 · Go 实现

思考

方法一使用线性额外内存。座椅必须成对，相邻两对之间的植物（含空位）各自独立，乘积即方案数。

扫一遍记下座椅个数与上一座椅位置，每遇到一对的起点就把与上一对终点之间的间隔乘进答案。座椅数为 $0$ 或奇数则无解。

空间降为常数。

我们可以将每两个座位划分为一组。在相邻的两组座位之间，如果前一组的最后一个座位和后一组的第一个座位之间的距离为 $x$，那么就有 $x$ 种放置屏风的方案。

我们遍历走廊，用一个变量 $\mathit{\text{cnt}}$ 记录当前座位数，用一个变量 $\mathit{\text{last}}$ 记录上一个座位的位置。

当遍历到一个座位时，我们将 $\mathit{\text{cnt}}$ 加 $1$，如果 $\mathit{\text{cnt}}$ 大于 $2$ 且 $\mathit{\text{cnt}}$ 为奇数，那么我们就需要在 $\mathit{\text{last}}$ 和当前座位之间放置一个屏风，此时的方案数就是 $\mathit{\text{ans}}\times (i-\mathit{\text{last}})$，其中 $\mathit{\text{ans}}$ 是之前的方案数。然后，我们更新 $\mathit{\text{last}}$ 为当前座位的位置 $i$。

最后，如果 $\mathit{\text{cnt}}$ 大于 $0$ 且 $\mathit{\text{cnt}}$ 为偶数，那么返回 $\mathit{\text{ans}}$，否则返回 $0$。

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

func numberOfWays(corridor string) int {
	const mod int = 1e9 + 7
	ans, cnt, last := 1, 0, 0
	for i, c := range corridor {
		if c == 'S' {
			cnt++
			if cnt > 2 && cnt%2 == 1 {
				ans = ans * (i - last) % mod
			}
			last = i
		}
	}
	if cnt > 0 && cnt%2 == 0 {
		return ans
	}
	return 0
}

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

思考

每段恰好两把椅子，屏风插在相邻段之间的植物上。枚举切开方式是指数级的，而走廊长度可达 ${10}^5$。

从位置 $i$、当前段已有 $k$ 把椅子出发的方案数只依赖位置 $i+1$。按这个递推搜索时仍会先调用 $i+1$ 再返回，调用链深度为 $n$，栈会溢出。

从末尾往前走时，后一位置已经就绪。令 $f[i][k]$ 为该方案数。遇到椅子则计数变为 $k+1$，计数超过 $2$ 记为 $0$；计数为 $2$ 时再加上「新开一段」的选择。

我们从 $i=n-1$ 填到 $0$，边界 $f[n][2]=1$，返回 $f[0][0]$。

令 $f[i][k]$ 表示从走廊第 $i$ 个位置开始划分后缀、且当前段已经有 $k$ 把椅子时的方案数。答案为 $f[0][0]$。

若 $i=n$，走廊已经走完。 $k=2$ 时值为 $1$，否则为 $0$，因此 $f[n][2]=1$。

否则，若 $\mathit{\text{corridor}}[i]$ 是椅子，则新的计数 $nk=k+1$，否则 $nk=k$。若 $nk>2$，当前段已经出现第三把椅子， $f[i][k]=0$。否则可以继续当前段，贡献 $f[i+1][nk]$。当 $nk=2$ 时还可以放下屏风并让下一段从空开始，贡献 $f[i+1][0]$。两部分相加后对 ${10}^9+7$ 取模。

我们从 $i=n-1$ 往前计算到 $0$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是走廊的长度。

func numberOfWays(corridor string) int {
	const mod = 1e9 + 7
	n := len(corridor)
	f := make([][3]int, n+1)
	f[n][2] = 1
	for i := n - 1; i >= 0; i-- {
		for k := 0; k < 3; k++ {
			nk := k
			if corridor[i] == 'S' {
				nk++
			}
			if nk > 2 {
				continue
			}
			f[i][k] = f[i+1][nk]
			if nk == 2 {
				f[i][k] = (f[i][k] + f[i+1][0]) % mod
			}
		}
	}
	return f[0][0]
}

力扣原题 · Doocs 题解来源

2152. 穿过所有点的所需最少直线数量 🔒

中等1 种解法

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

题目、示例与约束

给定一个 points 数组，points[i] = [xi, yi] 表示直角坐标系 X-Y 的一个点。

现在考虑向 X-Y 坐标系中添加 直线，使得每个点 至少 在一条直线上。

返回能够穿过所有点的所需 最少直线 数量。

 

示例 1:

输入: points = [[0,1],[2,3],[4,5],[4,3]]
输出: 2
解释: 所需最少直线数量为 2 ，一种可能的答案是添加:
- 一条穿过点 (0, 1) 和 点(4, 5) 的直线
- 另一条穿过点 (2, 3) 和点 (4, 3) 的直线

示例 2:

输入: points = [[0,2],[-2,-2],[1,4]]
输出: 1
解释: 所需最少直线数量为 1 ，唯一的答案是:
- 一条穿过点 (-2, -2) 和点 (1, 4) 的直线

 

提示:

• 1 <= points.length <= 10
• points[i].length == 2
• -100 <= xi, yi <= 100
• points 中元素都是唯一的

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

思考

用最少直线覆盖至多 $10$ 个点。枚举直线划分是集合划分问题，点数很小，适合对子集做搜索。

状态 $\mathit{\text{state}}$ 表示已覆盖的点集。每次从未覆盖点 $i$ 出发，与 $j$ 确定一条直线，并把共线的其余点一并盖上，递归剩余子集。单点也可单独用一条直线。

记忆化 $dfs(\mathit{\text{state}})$，终点为全集，转移代价加一。共线用叉积判定。

我们可以用一个整数 state 来表示当前已经添加的直线，其中 state 的第 $i$ 位表示第 $i$ 条直线是否已经添加。如果 state 的第 $i$ 位为 $1$，则表示第 $i$ 条直线已经添加，否则表示第 $i$ 条直线还未添加。

接下来，我们设计一个函数 $dfs(state)$，表示当前已经添加的直线为 state 时，至少需要添加多少条直线才能使得每个点至少在一条直线上。那么答案就是 $dfs(0)$。

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

• 如果 state 的所有位都为 $1$，则说明所有直线都已经添加，返回 $0$。
• 否则，我们枚举当前还未添加的点 $i$，接下来枚举 $j$，我们将 $i$ 和 $j$ 的点连成一条直线，此时的状态为 $nxt=state|1<<i|1<<j$，其中 $1<<i$ 表示将第 $i$ 位设置为 $1$， $1<<j$ 表示将第 $j$ 位设置为 $1$。接下来，我们枚举所有 $k$，如果 $i$、 $j$ 和 $k$ 三个点共线，则将 $k$ 的状态设置为 $1$，即 $nxt=nxt|1<<k$。此时，我们可以将 $i$ 和 $j$ 以及 $k$ 这三个点连成一条直线，此时的状态为 $nxt$，此时至少需要添加 $dfs(nxt)$ 条直线，我们取所有情况的最小值，即为 $dfs(state)$ 的值。

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

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

func minimumLines(points [][]int) int {
	check := func(i, j, k int) bool {
		x1, y1 := points[i][0], points[i][1]
		x2, y2 := points[j][0], points[j][1]
		x3, y3 := points[k][0], points[k][1]
		return (x2-x1)*(y3-y1) == (x3-x1)*(y2-y1)
	}
	n := len(points)
	f := make([]int, 1<<n)
	var dfs func(int) int
	dfs = func(state int) int {
		if state == (1<<n)-1 {
			return 0
		}
		if f[state] > 0 {
			return f[state]
		}
		ans := 1 << 30
		for i := 0; i < n; i++ {
			if (state >> i & 1) == 0 {
				for j := i + 1; j < n; j++ {
					nxt := state | 1<<i | 1<<j
					for k := j + 1; k < n; k++ {
						if (nxt>>k&1) == 0 && check(i, j, k) {
							nxt |= 1 << k
						}
					}
					ans = min(ans, dfs(nxt)+1)
				}
				if i == n-1 {
					ans = min(ans, dfs(state|1<<i)+1)
				}
			}
		}
		f[state] = ans
		return ans
	}
	return dfs(0)
}

力扣原题 · Doocs 题解来源

2163. 删除元素后和的最小差值

困难1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。

你可以从 nums 中删除 恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个 相同大小 的部分。

• 前面 n 个元素属于第一部分，它们的和记为 sumfirst 。
• 后面 n 个元素属于第二部分，它们的和记为 sumsecond 。

两部分和的 差值 记为 sumfirst - sumsecond 。

• 比方说，sumfirst = 3 且 sumsecond = 2 ，它们的差值为 1 。
• 再比方，sumfirst = 2 且 sumsecond = 3 ，它们的差值为 -1 。

请你返回删除 n 个元素之后，剩下两部分和的 差值的最小值 是多少。

 

示例 1：

输入：nums = [3,1,2]
输出：-1
解释：nums 有 3 个元素，所以 n = 1 。
所以我们需要从 nums 中删除 1 个元素，并将剩下的元素分成两部分。
- 如果我们删除 nums[0] = 3 ，数组变为 [1,2] 。两部分和的差值为 1 - 2 = -1 。
- 如果我们删除 nums[1] = 1 ，数组变为 [3,2] 。两部分和的差值为 3 - 2 = 1 。
- 如果我们删除 nums[2] = 2 ，数组变为 [3,1] 。两部分和的差值为 3 - 1 = 2 。
两部分和的最小差值为 min(-1,1,2) = -1 。

示例 2：

输入：nums = [7,9,5,8,1,3]
输出：1
解释：n = 2 。所以我们需要删除 2 个元素，并将剩下元素分为 2 部分。
如果我们删除元素 nums[2] = 5 和 nums[3] = 8 ，剩下元素为 [7,9,1,3] 。和的差值为 (7+9) - (1+3) = 12 。
为了得到最小差值，我们应该删除 nums[1] = 9 和 nums[4] = 1 ，剩下的元素为 [7,5,8,3] 。和的差值为 (7+5) - (8+3) = 1 。
观察可知，最优答案为 1 。

 

提示：

• nums.length == 3 * n
• 1 <= n <= 105
• 1 <= nums[i] <= 105

方法一：优先队列（大小根堆）+ 前后缀和 + 枚举分割点 · Go 实现

思考

删去 $n$ 个元素后，前 $n$ 个之和与后 $n$ 个之和的差要最小。等价于选一个分割点，左边保留最小的 $n$ 个，右边保留最大的 $n$ 个。枚举保留集合为组合数，不可行。

用大根堆维护前缀中最小 $n$ 元的和 $\mathit{\text{pre}}[i]$，用小根堆维护后缀中最大 $n$ 元的和 $\mathit{\text{suf}}[i]$。分割点 $i\in [n,2n]$ 处差为 $\mathit{\text{pre}}[i]-\mathit{\text{suf}}[i+1]$。

两边各扫一遍堆，再枚举分割点取最小差。

题目实际上等价于在 $nums$ 中找到一个分割点，将数组分成左右两部分，在前一部分中选取最小的 $n$ 个元素，在后一部分中选取最大的 $n$ 个元素，使得两部分和的差值最小。

我们可以用一个大根堆维护前缀中最小的 $n$ 个元素，用一个小根堆维护后缀中最大的 $n$ 个元素。我们定义 $pre[i]$ 表示在数组 $nums$ 的前 $i$ 个元素中选择最小的 $n$ 个元素的和，定义 $suf[i]$ 表示从数组第 $i$ 个元素到最后一个元素中选择最大的 $n$ 个元素的和。在维护大小根堆的过程中，更新 $pre[i]$ 和 $suf[i]$ 的值。

最后，我们在 $i\in [n,2n]$ 的范围内枚举分割点，计算 $pre[i]-suf[i+1]$ 的值，取最小值即可。

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

func minimumDifference(nums []int) int64 {
	m := len(nums)
	n := m / 3
	s := 0
	pre := make([]int, m+1)
	q1 := hp{}
	for i := 1; i <= n*2; i++ {
		x := nums[i-1]
		s += x
		heap.Push(&q1, -x)
		if q1.Len() > n {
			s -= -heap.Pop(&q1).(int)
		}
		pre[i] = s
	}
	s = 0
	suf := make([]int, m+1)
	q2 := hp{}
	for i := m; i > n; i-- {
		x := nums[i-1]
		s += x
		heap.Push(&q2, x)
		if q2.Len() > n {
			s -= heap.Pop(&q2).(int)
		}
		suf[i] = s
	}
	ans := int64(1e18)
	for i := n; i <= n*2; i++ {
		ans = min(ans, int64(pre[i]-suf[i+1]))
	}
	return ans
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

力扣原题 · Doocs 题解来源

2167. 移除所有载有违禁货物车厢所需的最少时间

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

1. 从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
2. 从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
3. 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。

返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

 

示例 1：

输入：s = "1100101"
输出：5
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 1 次。所用时间是 1 。
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2 + 1 + 2 = 5 。

一种替代方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间也是 2 + 3 = 5 。

5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

示例 2：

输入：s = "0010"
输出：2
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间是 3.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
总时间是 2.

2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

 

提示：

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

方法一 · Go 实现

思考

非法车厢可从左端连续删、从右端连续删，或花 $2$ 单独拆掉。需要三种手段的最小总代价。枚举左右切断点若每次重算中间拆卸则为二次以上。

令 $\mathit{\text{pre}}[i]$ 为处理前缀 $s[:i]$ 的最小代价：遇到 '0' 则等于 $\mathit{\text{pre}}[i-1]$，遇到 '1' 则在「单独拆 $2$」与「整段从左边删掉 $i$」中取小。后缀 $\mathit{\text{suf}}$ 对称。

答案为所有分割 $\mathit{\text{pre}}[i]+\mathit{\text{suf}}[i]$ 的最小值（前缀含 $s[i-1]$，后缀从 $s[i]$ 起）。

func minimumTime(s string) int {
	n := len(s)
	pre := make([]int, n+1)
	suf := make([]int, n+1)
	for i, c := range s {
		pre[i+1] = pre[i]
		if c == '1' {
			pre[i+1] = min(pre[i]+2, i+1)
		}
	}
	for i := n - 1; i >= 0; i-- {
		suf[i] = suf[i+1]
		if s[i] == '1' {
			suf[i] = min(suf[i+1]+2, n-i)
		}
	}
	ans := 0x3f3f3f3f
	for i := 1; i <= n; i++ {
		ans = min(ans, pre[i]+suf[i])
	}
	return ans
}

力扣原题 · Doocs 题解来源

2172. 数组的最大与和

困难1 种解法

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

题目、示例与约束

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。

你需要把所有 n 个整数分到这些篮子中，且每个篮子 至多 有 2 个整数。一种分配方案的 与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和。

• 比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2 中，这个方案的与和为 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 。

请你返回将 nums 中所有数放入 numSlots 个篮子中的最大与和。

 

示例 1：

输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。
最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。

示例 2：

输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。
最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。

 

提示：

• n == nums.length
• 1 <= numSlots <= 9
• 1 <= n <= 2 * numSlots
• 1 <= nums[i] <= 15

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

思考

$k$ 个篮子各能放至多两个数，与和为 $\sum (a\mathrm{\&}\mathit{\text{slot}})$。把每个篮子拆成两个容量为 $1$ 的槽位，槽位编号映射回篮子号。 $k\le 9$，槽位至多 $18$，可用子集 DP。

$f[S]$ 表示已用槽位集合为 $S$ 时的最大与和， $|S|$ 个已放数对应 $\mathit{\text{nums}}$ 的前缀。枚举 $S$ 中最后占用的槽 $j$，从 $S\setminus \{j\}$ 转移并加上 $\mathit{\text{nums}}[|S|-1]\mathrm{\&}(j/2+1)$。

答案为 $f$ 的最大值。

由于每个篮子最多只能放两个数，我们不妨将篮子数乘以 $2$，这样每个篮子最多只能放一个数。

接下来，我们定义 $f[i]$ 表示篮子状态为 $i$ 时的最大与和，其中 $i$ 是一个二进制数，表示每个篮子是否放了数。初始时 $f[0]=0$。

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

我们可以枚举 $i$，记 $i$ 的二进制表示中 $1$ 的个数为 $cnt$。如果 $cnt>n$，那么 $i$ 不是一个合法的状态，我们可以直接跳过。否则，我们可以枚举 $i$ 的二进制表示中的每一位 $j$，如果 $i$ 的第 $j$ 位为 $1$，那么我们可以将第 $(cnt-1)$ 个数 $nums[cnt-1]$ 放入第 $j$ 个篮子中，此时有：

$$f[i]=max\{f[i],f[i\oplus (1<<j)]+(nums[cnt-1]\wedge (j/2+1))\}$$

其中 $\oplus$ 表示异或运算，而 $\wedge$ 表示按位与运算。

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

时间复杂度 $O(4^k\times k\times 2)$，空间复杂度 $O(4^k)$。其中 $k$ 表示篮子的数量，即题目中的 $numSlots$。

func maximumANDSum(nums []int, numSlots int) int {
	n := len(nums)
	m := numSlots << 1
	f := make([]int, 1<<m)
	for i := range f {
		cnt := bits.OnesCount(uint(i))
		if cnt > n {
			continue
		}
		for j := 0; j < m; j++ {
			if i>>j&1 == 1 {
				f[i] = max(f[i], f[i^(1<<j)]+(nums[cnt-1]&(j/2+1)))
			}
		}
	}
	return slices.Max(f)
}

力扣原题 · Doocs 题解来源

2184. 建造坚实的砖墙的方法数 🔒

中等1 种解法

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

题目、示例与约束

给你两个整数 height 与width ，表示你要建造的砖墙的高和宽。再给你一个下标从 0 开始的数组 bricks ，其中第 i 块砖的高度是 1 ，宽度为 bricks[i] 。每种砖的数量都是 无限 的，并且砖 不可以 进行旋转。

墙的每一行必须正好 width 单位长。为了让墙体 坚实 ，除了在首尾的位置，相邻的行砖缝 不能 在同一个位置。

请你返回建造坚实的砖墙的方法数，由于答案可能很大，需要对 109 + 7 取余 。

 

示例 1：

输入：height = 2, width = 3, bricks = [1,2]
输出：2
解释：前两图中的两种方法是建造一座坚实砖墙的唯二的方法。注意，第三幅图所展示的不是坚实的砖墙，因为相邻的行在中间的连接点位置相同。

示例 2：

输入：height = 1, width = 1, bricks = [5]
输出：0
解释：无法建造符合题目要求的砖墙，因为仅有的砖的长度比墙还要长。

 

提示：

• 1 <= height <= 100
• 1 <= width <= 10
• 1 <= bricks.length <= 10
• 1 <= bricks[i] <= 10
• bricks 中所有数字 互不相同

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

思考

墙的每一层是若干砖块拼满宽度，且相邻两层的竖缝不能对齐。层高与砖种有限，先列出一层的所有切分，再决定层与层之间的相容关系。

DFS 枚举砖长组成和为 $\mathit{\text{width}}$ 的序列；两个序列若除两端外存在相同前缀和则不相容。层间转移是在相容排列上的路径计数，可用 DP： $\mathit{\text{dp}}[i][j]$ 表示第 $i$ 层用排列 $j$ 的方案数。

首层每种排列为 $1$，向上累加邻居，最后一层求和取模。

首先通过 DFS 构造出所有合法的排列。然后所有排列进行两两比较，找出每种排列相邻的合法排列，记录在 g 数组中。

然后进行动态规划。

过程是这样的：计算以某种排列结束的所有方案数。

初始化第一排每种排列的方案数为 1；每一排选取某种排列的总方案数为上一排能与自己相邻的排列的方案数之和。

答案为最后一排的方案数之和。

func buildWall(height int, width int, bricks []int) int {
	mod := int(1e9) + 7
	res := [][]int{}
	t := []int{}
	var dfs func(int)
	dfs = func(v int) {
		if v > width {
			return
		}
		if v == width {
			res = append(res, slices.Clone(t))
			return
		}
		for _, x := range bricks {
			t = append(t, x)
			dfs(v + x)
			t = t[:len(t)-1]
		}
	}
	check := func(a, b []int) bool {
		s1, s2 := a[0], b[0]
		i, j := 1, 1
		for i < len(a) && j < len(b) {
			if s1 == s2 {
				return false
			}
			if s1 < s2 {
				s1 += a[i]
				i++
			} else {
				s2 += b[j]
				j++
			}
		}
		return true
	}
	dfs(0)
	n := len(res)
	g := make([][]int, n)
	for i := 0; i < n; i++ {
		if check(res[i], res[i]) {
			g[i] = append(g[i], i)
		}
		for j := i + 1; j < n; j++ {
			if check(res[i], res[j]) {
				g[i] = append(g[i], j)
				g[j] = append(g[j], i)
			}
		}
	}
	dp := make([][]int, height)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	for i := 1; i < height; i++ {
		for j := 0; j < n; j++ {
			for _, k := range g[j] {
				dp[i][j] += dp[i-1][k]
				dp[i][j] %= mod
			}
		}
	}
	ans := 0
	for j := 0; j < n; j++ {
		ans += dp[height-1][j]
		ans %= mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

2188. 完成比赛的最少时间

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [fi, ri] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 fi * ri(x-1) 秒。

• 比方说，如果 fi = 3 且 ri = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 = 6 秒，完成第 3 圈耗时 3 * 22 = 12 秒，依次类推。

同时给你一个整数 changeTime 和一个整数 numLaps 。

比赛总共包含 numLaps 圈，你可以选择 任意 一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 changeTime 秒 换成 任意一种轮胎（也可以换成当前种类的新轮胎）。

请你返回完成比赛需要耗费的 最少 时间。

 

示例 1：

输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
输出：21
解释：
第 1 圈：使用轮胎 0 ，耗时 2 秒。
第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
完成比赛的最少时间为 21 秒。

示例 2：

输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
输出：25
解释：
第 1 圈：使用轮胎 1 ，耗时 2 秒。
第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。
总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
完成比赛的最少时间为 25 秒。

 

提示：

• 1 <= tires.length <= 105
• tires[i].length == 2
• 1 <= fi, changeTime <= 105
• 2 <= ri <= 105
• 1 <= numLaps <= 1000

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

思考

同一轮胎连续使用时第 $i$ 圈耗时按公比增长，一旦超过「换胎再跑一圈」的代价就不应再连用。连用圈数因此有很小的上界（约 $17$）。总圈数到 ${10}^3$，需在「何时换胎」上做决策。

先对每条轮胎预处理连跑 $i$ 圈的最小总耗时 $\mathit{\text{cost}}[i]$。再令 $f[i]$ 为跑完 $i$ 圈的最小耗时，最后一段连跑 $j$ 圈则 $f[i]=f[i-j]+\mathit{\text{cost}}[j]+\mathit{\text{changeTime}}$。

$f[0]=-\mathit{\text{changeTime}}$ 以抵消第一段并不存在的换胎。

我们注意到，连续使用同一个轮胎 $(f,r)$ 跑 $i$ 圈，那么第 $i$ 圈的耗时不应该超过 $changeTime+f$，否则我们可以在第 $i$ 圈的时候换轮胎，这样总耗时会更少。即：

$$f\times r^{i-1}\le changeTime+f$$

我们可以求出满足上式的最大的 $i$，要使得 $i$ 最大，那么 $f$ 和 $r$ 应该尽可能小，根据题目的数据范围，我们取 $f=1$, $r=2$，那么 $2^{i-1}\le changeTime+1$，即 $i\le {\log }_2(changeTime+1)+1$。根据这个结论，以及题目中 $changeTime$ 的数据范围，我们可以知道 $i$ 最大为 $17$。

我们定义 $cost[i]$ 表示使用同一个轮胎跑 $i$ 圈的最小耗时，那么我们可以预处理出 $cost$ 数组，然后使用动态规划求解即可。定义 $f[i]$ 表示跑 $i$ 圈的最小耗时，那么我们可以得到状态转移方程：

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

初始时 $f[0]=-changeTime$，最终答案为 $f[numLaps]$。

时间复杂度 $O((n+numLaps)\times \log T_{max})$，空间复杂度 $O(n+\log T_{max})$，其中 $T_{max}$ 是题目中 $f_i$, $r_i$ 和 $changeTime$ 的最大值。本题中 $\log T_{max}\approx 17$。

func minimumFinishTime(tires [][]int, changeTime int, numLaps int) int {
	const inf = 1 << 30
	cost := [18]int{}
	for i := range cost {
		cost[i] = inf
	}
	for _, e := range tires {
		f, r := e[0], e[1]
		s, t := 0, f
		for i := 1; t <= changeTime+f; i++ {
			s += t
			cost[i] = min(cost[i], s)
			t *= r
		}
	}
	f := make([]int, numLaps+1)
	for i := range f {
		f[i] = inf
	}
	f[0] = -changeTime
	for i := 1; i <= numLaps; i++ {
		for j := 1; j < min(18, i+1); j++ {
			f[i] = min(f[i], f[i-j]+cost[j])
		}
		f[i] += changeTime
	}
	return f[numLaps]
}

力扣原题 · Doocs 题解来源

2189. 建造纸牌屋的方法数 🔒

中等1 种解法

标签：数学、动态规划

题目、示例与约束

给你一个整数 n，代表你拥有牌的数量。一个 纸牌屋 满足以下条件:

• 一个 纸牌屋 由一行或多行 三角形 和水平纸牌组成。
• 三角形 是由两张纸牌相互靠在一起形成的。
• 一张纸牌必须水平放置在一行中 所有相邻 的三角形之间。
• 比第一行高的任何三角形都必须放在前一行的水平纸牌上。
• 每个三角形都被放置在行中 最左边 的可用位置。

返回使用所有 n 张纸牌可以构建的不同纸牌屋的数量。如果存在一行两个纸牌屋包含不同数量的纸牌，那么两个纸牌屋被认为是不同的。

 

示例 1:

输入: n = 16
输出: 2
解释: 有两种有效的纸牌屋摆法。
图中的第三个纸牌屋无效，因为第一行最右边的三角形没有放在水平纸牌的顶部。

Example 2:

输入: n = 2
输出: 1
解释: 这是唯一可行的纸牌屋。

Example 3:

输入: n = 4
输出: 0
解释: 图中的三种纸牌都是无效的。
第一个纸牌屋需要在两个三角形之间放置一张水平纸牌。
第二个纸牌屋使用 5 张纸牌。
第三个纸牌屋使用 2 张纸牌。

 

提示:

• 1 <= n <= 500

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

思考

每层卡片数为 $3k+2$ 且各层张数不同，求把 $n$ 张卡片拆成若干个这样的层的方案数。层的顺序由张数唯一确定（下层必须更宽），故只需选一个子集使其和为 $n$。

按层号 $k$ 从小到大决定取或不取，剩余张数不足则剪枝，恰好用完则计 $1$。这是二维背包，记忆化避免重复。

$\mathit{\text{dfs}}(n,k)$ 为答案入口。

我们注意到，每一层的卡片数量为 $3\times k+2$，并且每一层的卡片数量都不相同。因此，问题可以转化为：整数 $n$ 可以由多少种 $3\times k+2$ 的数相加得到。这是一个经典的背包问题，可以使用记忆化搜索解决。

我们设计一个函数 $\text{dfs}(n,k)$，表示当前剩余卡片数量为 $n$，且当前层为 $k$ 时，可以构建多少不同的纸牌屋。那么答案就是 $\text{dfs}(n,0)$。

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

• 如果 $3\times k+2>n$，那么当前层无法放置任何卡片，返回 $0$；
• 如果 $3\times k+2=n$，那么当前层可以放置卡片，放置完毕后，整个纸牌屋已经构建完毕，返回 $1$；
• 否则，我们可以选择不放置卡片，或者放置卡片。如果选择不放置卡片，那么剩余卡片数量不变，层数增加 $1$，即 $\text{dfs}(n,k+1)$；如果选择放置卡片，那么剩余卡片数量减少 $3\times k+2$，层数增加 $1$，即 $\text{dfs}(n-(3\times k+2),k+1)$。两者相加即为答案。

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

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

func houseOfCards(n int) int {
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n/3+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(n, k int) int
	dfs = func(n, k int) int {
		x := 3*k + 2
		if x > n {
			return 0
		}
		if x == n {
			return 1
		}
		if f[n][k] == -1 {
			f[n][k] = dfs(n-x, k+1) + dfs(n, k+1)
		}
		return f[n][k]
	}
	return dfs(n, 0)
}

力扣原题 · Doocs 题解来源

2209. 用地毯覆盖后的最少白色砖块

困难2 种解法

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

题目、示例与约束

给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

• floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。
• floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少 数目。

 

示例 1：

输入：floor = "10110101", numCarpets = 2, carpetLen = 2
输出：2
解释：
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。

示例 2：

输入：floor = "11111", numCarpets = 2, carpetLen = 3
输出：0
解释：
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。

 

提示：

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

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

思考

有 $m$ 条长度为 $L$ 的地毯，要盖住尽量多的白砖。若枚举每条地毯的起点，方案数为指数级， $n,m\le {10}^3$ 不可行。地毯互不要求重叠方式固定，决策可以按砖块从左到右进行。

定义 $\mathit{\text{dfs}}(i,j)$ 为从下标 $i$ 起、还剩 $j$ 条地毯时最少未被覆盖的白砖。黑砖无需覆盖，直接跳到 $i+1$；没有地毯时，剩余白砖数等于前缀和之差 $s[n]-s[i]$；白砖则可选择不盖（答案加 $1$ 并前进一格）或盖上（跳过 $L$ 格并消耗一条地毯）。

状态数为 $O(nm)$，每个状态常数转移，记忆化后即可在约束内求出 $\mathit{\text{dfs}}(0,m)$。

我们设计一个函数 $\mathit{\text{dfs}}(i,j)$ 表示从下标 $i$ 开始，使用 $j$ 条地毯，最少有多少个白色砖块没有被覆盖。答案即为 $\mathit{\text{dfs}}(0,\mathit{\text{numCarpets}})$。

对于下标 $i$，我们分情况讨论：

• 如果 $i\ge n$，说明已经覆盖完所有砖块，返回 $0$；
• 如果 $\mathit{\text{floor}}[i]=0$，则不需要使用地毯，直接跳过即可，即 $\mathit{\text{dfs}}(i,j)=\mathit{\text{dfs}}(i+1,j)$；
• 如果 $j=0$，那么我们可以直接利用前缀和数组 $s$ 计算出剩余未被覆盖的白色砖块的数目，即 $\mathit{\text{dfs}}(i,j)=s[n]-s[i]$；
• 如果 $\mathit{\text{floor}}[i]=1$，那么我们可以选择使用地毯覆盖，也可以选择不使用地毯覆盖，取两者的最小值即可，即 $\mathit{\text{dfs}}(i,j)=min(\mathit{\text{dfs}}(i+1,j),\mathit{\text{dfs}}(i+\mathit{\text{carpetLen}},j-1))$。

记忆化搜索即可。

时间复杂度 $O(n\times m)$，空间复杂度 $O(n\times m)$。其中 $n$ 和 $m$ 分别为字符串 $\mathit{\text{floor}}$ 的长度和 $\mathit{\text{numCarpets}}$ 的值。

func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
	n := len(floor)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, numCarpets+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	s := make([]int, n+1)
	for i, c := range floor {
		s[i+1] = s[i] + int(c-'0')
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= n {
			return 0
		}
		if j == 0 {
			return s[n] - s[i]
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		if s[i+1] == s[i] {
			return dfs(i+1, j)
		}
		ans := min(1+dfs(i+1, j), dfs(i+carpetLen, j-1))
		f[i][j] = ans
		return ans
	}
	return dfs(0, numCarpets)
}

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

思考

有 $m$ 条长度为 $L$ 的地毯，要让露出的白砖尽量少。枚举每条地毯的起点是指数级的， $n$ 与 $m$ 都能到 $1000$。

从左到右看，黑砖一定先跳到下一格。一整条黑砖从下标 $0$ 走到 $n$，调用链长度就是 $n$。 $n=1000$ 时 Python 会抛出 RecursionError。

跳过黑砖、留下白砖或铺上地毯，读到的都是更大的下标。铺地毯时还会少用一条。

因此从右往左填表。 $f[i][j]$ 是从下标 $i$ 起、还剩 $j$ 条地毯时露出的最少白砖， $f[n][\cdot ]=0$。黑砖复制 $f[i+1][j]$；没有地毯时答案是剩余白砖 $s[n]-s[i]$；白砖取留下它的 $1+f[i+1][j]$ 和铺上地毯的 $f[i+L][j-1]$ 中的较小值。

令 $s[i]$ 为 $\mathit{\text{floor}}$ 前 $i$ 块砖中的白砖个数。定义 $f[i][j]$ 表示从下标 $i$ 开始、还剩 $j$ 条地毯时，最少露出多少块白砖。答案是 $f[0][\mathit{\text{numCarpets}}]$。先令 $f[n][j]=0$，表示砖块已经走完。

按 $i$ 从 $n-1$ 降到 $0$、 $j$ 从 $0$ 到 $m$ 填写：

• 若 $\mathit{\text{floor}}[i]=0$，这一块是黑砖，不消耗地毯， $f[i][j]=f[i+1][j]$。
• 若 $j=0$，没有地毯可用， $f[i][j]=s[n]-s[i]$。
• 否则这一块是白砖。不铺地毯会露出它，代价为 $1+f[i+1][j]$；铺一条长度为 $L$ 的地毯则跳到下标 $i+L$，地毯数变为 $j-1$。当 $i+L\le n$ 时，这一支是 $f[i+L][j-1]$，否则已经越出数组，代价为 $0$。 $f[i][j]$ 取两者的较小值。

时间复杂度 $O(n\times m)$，空间复杂度 $O(n\times m)$。其中 $n$ 和 $m$ 分别为字符串 $\mathit{\text{floor}}$ 的长度和 $\mathit{\text{numCarpets}}$ 的值。

func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
	n := len(floor)
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = s[i]
		if floor[i] == '1' {
			s[i+1]++
		}
	}
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, numCarpets+1)
	}
	for i := n - 1; i >= 0; i-- {
		for j := 0; j <= numCarpets; j++ {
			if floor[i] == '0' {
				f[i][j] = f[i+1][j]
			} else if j == 0 {
				f[i][j] = s[n] - s[i]
			} else {
				cover := 0
				if i+carpetLen <= n {
					cover = f[i+carpetLen][j-1]
				}
				f[i][j] = min(1+f[i+1][j], cover)
			}
		}
	}
	return f[0][numCarpets]
}

力扣原题 · Doocs 题解来源

2218. 从栈中取出 K 个硬币的最大面值和

困难2 种解法

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

题目、示例与约束

一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。

每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里。

给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。

 

示例 1：

输入：piles = [[1,100,3],[7,8,9]], k = 2
输出：101
解释：
上图展示了几种选择 k 个硬币的不同方法。
我们可以得到的最大面值为 101 。

示例 2：

输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
输出：706
解释：
如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。

 

提示：

• n == piles.length
• 1 <= n <= 1000
• 1 <= piles[i][j] <= 105
• 1 <= k <= sum(piles[i].length) <= 2000

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

思考

每堆只能从顶部连续取，总共取 $k$ 枚，价值和尽量大。若对取法做搜索，堆数与 $k$ 均可达千、总硬币数 $2000$，会重复计算同一前缀。各堆之间互相独立，属于分组背包：一堆是一组物品，取前 $h$ 枚对应一件体积为 $h$ 的物品。

令 $f[i][j]$ 为前 $i$ 堆取 $j$ 枚的最大价值。对第 $i$ 堆先做前缀和 $s[h]$，再枚举 $j$ 与 $h$，用 $f[i-1][j-h]+s[h]$ 更新。总转移量与「堆大小之和乘 $k$」同阶，可以通过。

我们定义 $f[i][j]$ 表示从前 $i$ 组中取出 $j$ 个硬币的最大面值和，那么答案为 $f[n][k]$，其中 $n$ 为栈的数量。

对于第 $i$ 组，我们可以选择取前 $0$, $1$, $2$, $\cdots$, $k$ 个硬币。我们可以通过前缀和数组 $s$ 来快速计算出取前 $h$ 个硬币的面值和。

状态转移方程为：

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

其中 $0\le h\le j$，而 $s[h]$ 表示第 $i$ 组中取前 $h$ 个硬币的面值和。

时间复杂度 $O(k\times L)$，空间复杂度 $O(n\times k)$。其中 $L$ 为所有硬币的数量，而 $n$ 为栈的数量。

func maxValueOfCoins(piles [][]int, k int) int {
	n := len(piles)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		nums := piles[i-1]
		s := make([]int, len(nums)+1)
		for j := 1; j <= len(nums); j++ {
			s[j] = s[j-1] + nums[j-1]
		}

		for j := 0; j <= k; j++ {
			for h, w := range s {
				if j < h {
					break
				}
				f[i][j] = max(f[i][j], f[i-1][j-h]+w)
			}
		}
	}
	return f[n][k]
}

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

思考

方法一的转移只依赖上一行的 $f[i-1][\cdot ]$，二维表中同时存放多行并无必要。把 $f$ 压成一维后，必须从大到小枚举容量 $j$，以免同一堆被取两次。

对每一堆仍先算前缀和，再倒序枚举 $j$ 与 $h$ 做同样的 $max$ 更新。时间不变，额外空间降为 $O(k)$。

我们可以发现，对于第 $i$ 组，我们只需要用到 $f[i-1][j]$ 和 $f[i][j-h]$，因此我们可以将二维数组优化为一维数组。

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

func maxValueOfCoins(piles [][]int, k int) int {
	f := make([]int, k+1)
	for _, nums := range piles {
		s := make([]int, len(nums)+1)
		for j := 1; j <= len(nums); j++ {
			s[j] = s[j-1] + nums[j-1]
		}
		for j := k; j >= 0; j-- {
			for h := 0; h < len(s) && h <= j; h++ {
				f[j] = max(f[j], f[j-h]+s[h])
			}
		}
	}
	return f[k]
}

力扣原题 · Doocs 题解来源

2222. 选择建筑的方案数

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：

• s[i] = '0' 表示第 i 栋建筑是一栋办公楼，
• s[i] = '1' 表示第 i 栋建筑是一间餐厅。

作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。

• 比方说，给你 s = "001101" ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 "011" ，有相邻两栋建筑是同一类型，所以 不合 题意。

请你返回可以选择 3 栋建筑的 有效方案数 。

 

示例 1：

输入：s = "001101"
输出：6
解释：
以下下标集合是合法的：
- [0,2,4] ，从 "001101" 得到 "010"
- [0,3,4] ，从 "001101" 得到 "010"
- [1,2,4] ，从 "001101" 得到 "010"
- [1,3,4] ，从 "001101" 得到 "010"
- [2,4,5] ，从 "001101" 得到 "101"
- [3,4,5] ，从 "001101" 得到 "101"
没有别的合法选择，所以总共有 6 种方法。

示例 2：

输入：s = "11100"
输出：0
解释：没有任何符合题意的选择。

 

提示：

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

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

思考

要从 $01$ 串中选三个位置，相邻所选不能同色，即子序列只能是 $010$ 或 $101$。 $n\le {10}^5$，枚举三元组不可行。固定中间那一座楼后，左右必须都是相反颜色，方案数等于左侧相反色个数乘右侧相反色个数。

先统计全串两种颜色的个数作为右侧计数 $r$，再从左扫描：经过 $x$ 前先从 $r$ 中去掉它，把 $l[x\oplus 1]\times r[x\oplus 1]$ 加入答案，再把 $x$ 计入左侧。线性即可。

根据题目描述，我们需要选择 $3$ 栋建筑，且相邻的两栋不能是同一类型。

我们可以枚举中间的建筑，假设为 $x$，那么左右两边的建筑类型只能是 $x\oplus 1$，其中 $\oplus$ 表示异或运算。因此，我们可以使用两个数组 $l$ 和 $r$ 分别记录左右两边的建筑类型的数量，然后枚举中间的建筑，计算答案即可。

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

func numberOfWays(s string) (ans int64) {
	n := len(s)
	l := [2]int{}
	r := [2]int{}
	r[0] = strings.Count(s, "0")
	r[1] = n - r[0]
	for _, c := range s {
		x := int(c - '0')
		r[x]--
		ans += int64(l[x^1] * r[x^1])
		l[x]++
	}
	return
}

力扣原题 · Doocs 题解来源

2262. 字符串的总引力

困难1 种解法

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

题目、示例与约束

字符串的 引力 定义为：字符串中 不同 字符的数量。

• 例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。

给你一个字符串 s ，返回 其所有子字符串的总引力 。

子字符串 定义为：字符串中的一个连续字符序列。

 

示例 1：

输入：s = "abbca"
输出：28
解释："abbca" 的子字符串有：
- 长度为 1 的子字符串："a"、"b"、"b"、"c"、"a" 的引力分别为 1、1、1、1、1，总和为 5 。
- 长度为 2 的子字符串："ab"、"bb"、"bc"、"ca" 的引力分别为 2、1、2、2 ，总和为 7 。
- 长度为 3 的子字符串："abb"、"bbc"、"bca" 的引力分别为 2、2、3 ，总和为 7 。
- 长度为 4 的子字符串："abbc"、"bbca" 的引力分别为 3、3 ，总和为 6 。
- 长度为 5 的子字符串："abbca" 的引力为 3 ，总和为 3 。
引力总和为 5 + 7 + 7 + 6 + 3 = 28 。

示例 2：

输入：s = "code"
输出：20
解释："code" 的子字符串有：
- 长度为 1 的子字符串："c"、"o"、"d"、"e" 的引力分别为 1、1、1、1 ，总和为 4 。
- 长度为 2 的子字符串："co"、"od"、"de" 的引力分别为 2、2、2 ，总和为 6 。
- 长度为 3 的子字符串："cod"、"ode" 的引力分别为 3、3 ，总和为 6 。
- 长度为 4 的子字符串："code" 的引力为 4 ，总和为 4 。
引力总和为 4 + 6 + 6 + 4 = 20 。

 

提示：

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

方法一：枚举 · Go 实现

思考

子串的引力是其中不同字符的个数，要求和。 $n\le {10}^5$，枚举全部子串是平方级。考虑以 $s[i]$ 结尾的子串：新字符 $c$ 会让「上次 $c$ 出现之后」的那些子串各多一个不同字符。

记下每个字母上次出现位置 $pos[c]$（初始 $-1$）。走到 $i$ 时，增量 $t+=i-pos[c]$，再把 $t$ 累入答案。 $t$ 始终等于以当前位置结尾的全部子串引力之和。

我们可以枚举以每个字符 $s[i]$ 结尾的字符串，计算其引力值之和 $t$，最后将所有 $t$ 相加即可。

考虑遍历到 $s[i]$ 时，即把 $s[i]$ 添加到以 $s[i-1]$ 结尾的子字符串的后面，其引力值之和 $t$ 的变化情况：

1. 如果 $s[i]$ 在之前没出现过，那么所有以 $s[i-1]$ 结尾的子字符串的引力值都会增加 $1$，共有 $i$ 个，所以 $t$ 增加 $i$，再加上 $s[i]$ 自身的引力值 $1$，所以 $t$ 一共增加 $i+1$；
2. 如果 $s[i]$ 在之前出现过，不妨记上次出现的的位置为 $j$，那么我们向子字符串 $s[0..i-1]$, $[1..i-1]$, $s[2..i-1]$, $\cdots$, $s[j..i-1]$ 后面添加 $s[i]$，这些子字符串的引力值不会发生变化，因为 $s[i]$ 已经在这些子字符串中出现过了；而子字符串 $s[j+1..i-1]$, $s[j+2..i-1]$, $\cdots$, $s[i-1]$ 的引力值都会增加 $1$，共有 $i-j-1$ 个，所以 $t$ 增加 $i-j-1$，再加上 $s[i]$ 自身的引力值 $1$，所以 $t$ 一共增加 $i-j$。

综上，我们可以用一个数组 $pos$ 记录每个字符上次出现的位置，初始时所有位置都为 $-1$，

接下来，我们遍历字符串，每一次我们更新以当前字符结尾的子字符串的引力值之和 $t=t+i-pos[c]$，其中 $c$ 是当前字符，累加 $t$ 到答案中。然后我们更新 $pos[c]$ 为当前位置 $i$。继续遍历直到字符串结束。

时间复杂度 $O(n)$，空间复杂度 $O(|\mathrm{\Sigma }|)$，其中 $n$ 是字符串 $s$ 的长度；而 $|\mathrm{\Sigma }|$ 是字符集的大小，本题中 $|\mathrm{\Sigma }|=26$。

func appealSum(s string) int64 {
	var ans, t int64
	pos := make([]int, 26)
	for i := range pos {
		pos[i] = -1
	}
	for i, c := range s {
		c -= 'a'
		t += int64(i - pos[c])
		ans += t
		pos[c] = i
	}
	return ans
}

力扣原题 · Doocs 题解来源

2263. 数组变为有序的最小操作次数 🔒

困难1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以：

• 在范围 0 <= i < nums.length 内选出一个下标 i
• 将 nums[i] 的值变为 nums[i] + 1 或 nums[i] - 1

返回将数组 nums 变为 非递减 或 非递增 所需的 最小 操作次数。

 

示例 1：

输入：nums = [3,2,4,5,0]
输出：4
解释：
一种可行的操作顺序，能够将 nums 变为非递增排列：
- nums[1] 加 1 一次，使其变为 3 。
- nums[2] 减 1 一次，使其变为 3 。
- nums[3] 减 1 两次，使其变为 3 。
经过 4 次操作后，nums 变为 [3,3,3,3,0] ，按非递增顺序排列。
注意，也可以用 4 步操作将 nums 变为 [4,4,4,4,0] ，同样满足题目要求。
可以证明最少需要 4 步操作才能将数组变为非递增或非递减排列。

示例 2：

输入：nums = [2,2,3,4]
输出：0
解释：数组已经是按非递减顺序排列了，无需执行任何操作，返回 0 。

示例 3：

输入：nums = [0]
输出：0
解释：数组已经是按非递减顺序排列了，无需执行任何操作，返回 0 。

 

提示：

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

 

进阶：你可以设计并实现时间复杂度为 O(n*log(n)) 的解法吗?

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

思考

每次可将一个元素加一或减一，要使数组变成非递减或非递增，代价之和最小。 $n$ 与值域均为 ${10}^3$，可以把「第 $i$ 位改成 $j$」做成 DP。非递增只要把数组反转后再求非递减。

令 $f[i][j]$ 为前 $i$ 个位置、第 $i$ 个改成 $j$ 的最小代价。 $j$ 必须不小于前一位的终值，因此 $f[i][j]=\underset{k\le j}{min}f[i-1][k]+|j-nums[i-1]|$。内层最小值可以随 $j$ 递增维护。对原数组与反转各算一次取较小。

我们定义 $f[i][j]$ 表示将数组 $nums$ 的前 $i$ 个元素变为非递减序列，且第 $i$ 个元素的值为 $j$ 所需的最小操作次数。由于数组 $nums$ 元素的取值范围为 $[0,1000]$，因此我们可以将 $f$ 数组的第二维定义为 $1001$。

状态转移方程如下：

$$f[i][j]=\underset{0\le k\le j}{min}f[i-1][k]+|j-nums[i-1]|$$

时间复杂度 $O(n\times M)$，空间复杂度 $O(n\times M)$。其中 $n$ 和 $M$ 分别为数组 $nums$ 的长度和数组 $nums$ 元素的取值范围。本题中 $M=1001$。

由于我们定义的是非递减序列的最小操作次数，因此我们可以将数组 $nums$ 翻转，然后求出非递减序列的最小操作次数，也即是非递增序列的最小操作次数。最后取两者的最小值即可。

func convertArray(nums []int) int {
	return min(solve(nums), solve(reverse(nums)))
}

func solve(nums []int) int {
	n := len(nums)
	f := make([][1001]int, n+1)
	for i := 1; i <= n; i++ {
		mi := 1 << 30
		for j := 0; j <= 1000; j++ {
			mi = min(mi, f[i-1][j])
			f[i][j] = mi + abs(nums[i-1]-j)
		}
	}
	ans := 1 << 30
	for _, x := range f[n] {
		ans = min(ans, x)
	}
	return ans
}

func reverse(nums []int) []int {
	for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
	return nums
}

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

力扣原题 · Doocs 题解来源

2266. 统计打字方案数

中等1 种解法

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

题目、示例与约束

Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。

为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。

• 比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母  'k' 。
• 注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。

但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。

• 比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。

给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。

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

 

示例 1：

输入：pressedKeys = "22233"
输出：8
解释：
Alice 可能发出的文字信息包括：
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。
由于总共有 8 种可能的信息，所以我们返回 8 。

示例 2：

输入：pressedKeys = "222222222222222222222222222222222222"
输出：82876089
解释：
总共有 2082876103 种 Alice 可能发出的文字信息。
由于我们需要将答案对 109 + 7 取余，所以我们返回 2082876103 % (109 + 7) = 82876089 。

 

提示：

• 1 <= pressedKeys.length <= 105
• pressedKeys 只包含数字 '2' 到 '9' 。

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

思考

连续相同按键可分成若干长度不超过该键字母数的段，求解码方案数。 $n\le {10}^5$，按整串搜索不可行。不同字符的段互相独立，方案数相乘。一段长度为 $m$ 的相同按键，等价于爬楼梯：普通键一步 $1..3$，键 $7$、 $9$ 一步 $1..4$。

预先打表 $f[i]$、 $g[i]$ 到 ${10}^5$，再按 $\mathit{\text{groupby}}$ 分段相乘取模。

根据题目描述，对于字符串 $\mathit{\text{pressedKeys}}$ 中连续的相同字符，可以将其分为一组，然后分别计算每组的方案数，最后将所有组的方案数相乘即可。

问题的关键在于如何计算每组的方案数。

如果一组字符为 '7' 或 '9'，我们可以分别将该组的末尾 $1$, $2$, $3$, $4$ 个字符视为一个字母，然后将该组字符规模缩小，转化为规模更小的子问题。

同样地，如果一组字符为 '2', '3', '4', '5', '6', '8'，我们可以将该组的末尾 $1$, $2$, $3$ 个字符视为一个字母，然后将该组字符规模缩小，转化为规模更小的子问题。

因此，我们定义 $f[i]$ 表示长度为 $i$ 的连续相同字符，且字符不为 '7' 或 '9' 的方案数，定义 $g[i]$ 表示长度为 $i$ 的连续相同字符，且字符为 '7' 或 '9' 的方案数。

初始时 $f[0]=f[1]=1$, $f[2]=2$, $f[3]=4$, $g[0]=g[1]=1$, $g[2]=2$, $g[3]=4$。

对于 $i\ge 4$，有：

$$\begin{array}{rl}f[i]& =f[i-1]+f[i-2]+f[i-3]\\ g[i]& =g[i-1]+g[i-2]+g[i-3]+g[i-4]\end{array}$$

最后，我们遍历 $\mathit{\text{pressedKeys}}$，将连续相同字符分组，然后计算每组的方案数，最后将所有组的方案数相乘即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $\mathit{\text{pressedKeys}}$ 的长度。

const mod int = 1e9 + 7
const n int = 1e5 + 10

var f = [n]int{1, 1, 2, 4}
var g = f

func init() {
	for i := 4; i < n; i++ {
		f[i] = (f[i-1] + f[i-2] + f[i-3]) % mod
		g[i] = (g[i-1] + g[i-2] + g[i-3] + g[i-4]) % mod
	}
}

func countTexts(pressedKeys string) int {
	ans := 1
	for i, j, n := 0, 0, len(pressedKeys); i < n; i++ {
		c := pressedKeys[i]
		j = i
		for j+1 < n && pressedKeys[j+1] == c {
			j++
		}
		cnt := j - i + 1
		if c == '7' || c == '9' {
			ans = ans * g[cnt] % mod
		} else {
			ans = ans * f[cnt] % mod
		}
		i = j
	}
	return ans
}

力扣原题 · Doocs 题解来源

2267. 检查是否有合法括号字符串路径

困难1 种解法

标签：数组、动态规划、矩阵、括号序列

题目、示例与约束

一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。

• 字符串是 () 。
• 字符串可以表示为 AB（A 连接 B），A 和 B 都是合法括号序列。
• 字符串可以表示为 (A) ，其中 A 是合法括号序列。

给你一个 m x n 的括号网格图矩阵 grid 。网格图中一个 合法括号路径 是满足以下所有条件的一条路径：

• 路径开始于左上角格子 (0, 0) 。
• 路径结束于右下角格子 (m - 1, n - 1) 。
• 路径每次只会向 下 或者向 右 移动。
• 路径经过的格子组成的括号字符串是 合法 的。

如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。

 

示例 1：

输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图展示了两条路径，它们都是合法括号字符串路径。
第一条路径得到的合法字符串是 "()(())" 。
第二条路径得到的合法字符串是 "((()))" 。
注意可能有其他的合法括号字符串路径。

示例 2：

输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] 要么是 '(' ，要么是 ')' 。

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

思考

只向右或向下走，路径括号序列必须合法。 $m,n\le 100$，路径长度固定为 $m+n-1$。长度为奇数、起点是右括号或终点是左括号时必不合法。其余情况若搜索全部路径则指数过多，但合法前缀的平衡 $k$ 有上界：后面剩下的格子数必须还能把 $k$ 降到 $0$。

记忆化 $\mathit{\text{dfs}}(i,j,k)$：先按当前格更新 $k$，若 $k<0$ 或 $k$ 大于剩余步数则剪枝；终点要求 $k=0$。状态数 $O(mn(m+n))$。

我们记矩阵的行数为 $m$，列数为 $n$。

如果 $m+n-1$ 为奇数，或者左上角和右下角的括号不匹配，那么一定不存在合法路径，直接返回 $\text{false}$。

否则，我们设计一个函数 $\mathit{\text{dfs}}(i,j,k)$，表示从 $(i,j)$ 出发，且当前括号的平衡度为 $k$，是否存在合法路径。其中，平衡度 $k$ 的定义为：从 $(0,0)$ 到 $(i,j)$ 的路径中，左括号的个数减去右括号的个数。

如果平衡度 $k$ 小于 $0$ 或者大于 $m+n-i-j$，那么一定不存在合法路径，直接返回 $\text{false}$。如果 $(i,j)$ 正好是右下角的格子，那么只有当 $k=0$ 时才存在合法路径。否则，我们枚举 $(i,j)$ 的下一个格子 $(x,y)$，如果 $(x,y)$ 是合法的格子且 $\mathit{\text{dfs}}(x,y,k)$ 为 $\text{true}$，那么就存在合法路径。

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

func hasValidPath(grid [][]byte) bool {
	m, n := len(grid), len(grid[0])
	if (m+n-1)%2 == 1 || grid[0][0] == ')' || grid[m-1][n-1] == '(' {
		return false
	}
	vis := make([][][]bool, m)
	for i := range vis {
		vis[i] = make([][]bool, n)
		for j := range vis[i] {
			vis[i][j] = make([]bool, m+n)
		}
	}
	dirs := [3]int{1, 0, 1}
	var dfs func(i, j, k int) bool
	dfs = func(i, j, k int) bool {
		if vis[i][j][k] {
			return false
		}
		vis[i][j][k] = true
		if grid[i][j] == '(' {
			k++
		} else {
			k--
		}
		if k < 0 || k > m-i+n-j {
			return false
		}
		if i == m-1 && j == n-1 {
			return k == 0
		}
		for d := 0; d < 2; d++ {
			x, y := i+dirs[d], j+dirs[d+1]
			if x >= 0 && x < m && y >= 0 && y < n && dfs(x, y, k) {
				return true
			}
		}
		return false
	}
	return dfs(0, 0, 0)
}

力扣原题 · Doocs 题解来源

2272. 最大波动的子字符串

困难1 种解法

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

题目、示例与约束

字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。

给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。

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

 

示例 1：

输入：s = "aababbb"
输出：3
解释：
所有可能的波动值和它们对应的子字符串如以下所示：
- 波动值为 0 的子字符串："a" ，"aa" ，"ab" ，"abab" ，"aababb" ，"ba" ，"b" ，"bb" 和 "bbb" 。
- 波动值为 1 的子字符串："aab" ，"aba" ，"abb" ，"aabab" ，"ababb" ，"aababbb" 和 "bab" 。
- 波动值为 2 的子字符串："aaba" ，"ababbb" ，"abbb" 和 "babb" 。
- 波动值为 3 的子字符串 "babbb" 。
所以，最大可能波动值为 3 。

示例 2：

输入：s = "abcde"
输出：0
解释：
s 中没有字母出现超过 1 次，所以 s 中每个子字符串的波动值都是 0 。

 

提示：

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

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

思考

子串的方差是出现最多与最少的字母次数之差。 $n\le {10}^4$，枚举全部子串再统计是平方级偏紧。字母只有 $26$ 个，方差只由一对字母决定，可枚举 $(a,b)$ 后在串上做「 $a$ 为 $+1$、 $b$ 为 $-1$」的最大子段和，且子段必须同时含 $a$ 和 $b$。

$f[0]$ 是以当前为尾、只含 $a$ 的连续段长度； $f[1]$ 是已同时出现过 $a$、 $b$ 的最大差值。遇 $a$ 两者加一，遇 $b$ 则 $f[1]$ 取 $max(f[1],f[0])-1$ 并清空 $f[0]$。 $f[1]$ 初值为负无穷，保证尚未见到 $b$ 时不更新答案。

由于字符集只包含小写字母，我们可以考虑枚举出现次数最多的字符 $a$ 以及出现次数最少的字符 $b$。对于一个子串来说，这两种字符出现的次数之差就是子串的波动值。

具体实现上，我们使用双重循环枚举 $a$ 和 $b$，用 $f[0]$ 记录以当前字符结尾的连续出现字符 $a$ 的个数，用 $f[1]$ 记录以当前字符结尾的，并且包含 $a$ 和 $b$ 的子串的波动值。迭代取 $f[1]$ 的最大值即可。

递推公式如下：

1. 如果当前字符为 $a$，则 $f[0]$ 和 $f[1]$ 都加 $1$；
2. 如果当前字符为 $b$，则 $f[1]=max(f[1]-1,f[0]-1)$，而 $f[0]=0$；
3. 否则，无需考虑。

注意，初始时将 $f[1]$ 赋值为一个负数最大值，可以保证更新答案时是合法的。

时间复杂度 $O(n\times |\mathrm{\Sigma }{|}^2)$，其中 $n$ 是字符串长度，而 $|\mathrm{\Sigma }|$ 是字符集大小。空间复杂度 $O(1)$。

func largestVariance(s string) int {
	ans, n := 0, len(s)
	for a := 'a'; a <= 'z'; a++ {
		for b := 'a'; b <= 'z'; b++ {
			if a == b {
				continue
			}
			f := [2]int{0, -n}
			for _, c := range s {
				if c == a {
					f[0]++
					f[1]++
				} else if c == b {
					f[1] = max(f[1]-1, f[0]-1)
					f[0] = 0
				}
				ans = max(ans, f[1])
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2291. 最大股票收益 🔒

中等2 种解法

标签：数组、动态规划

题目、示例与约束

给你两个下标从 0 开始的数组 present 和 future ，present[i] 和 future[i] 分别代表第 i 支股票现在和将来的价格。每支股票你最多购买 一次 ，你的预算为 budget 。

求最大的收益。

 

示例 1：

输入：present = [5,4,6,2,3], future = [8,5,4,3,5], budget = 10
输出：6
解释：你可以选择购买第 0,3,4 支股票获得最大收益：6 。总开销为：5 + 2 + 3 = 10 , 总收益是: 8 + 3 + 5 - 10 = 6 。

示例 2：

输入：present = [2,2,5], future = [3,4,10], budget = 6
输出：5
解释：你可以选择购买第 2 支股票获得最大收益：5 。总开销为：5 , 总收益是: 10 - 5 = 5 。

示例 3：

输入：present = [3,3,12], future = [0,3,15], budget = 10
输出：0
解释：你无法购买唯一一支正收益股票 2 ，因此你的收益是 0 。

 

提示：

• n == present.length == future.length
• 1 <= n <= 1000
• 0 <= present[i], future[i] <= 100
• 0 <= budget <= 1000

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

思考

每支股票至多买一次，花费为现价，收益为未来价减现价，预算有限。 $n$ 与预算均为 ${10}^3$，是典型的 $0$-$1$ 背包：物品体积为现价，价值为利润（仅当利润为正时才值得买）。

令 $f[i][j]$ 为前 $i$ 支股票、预算 $j$ 的最大利润。不买则继承上一行；买则要求 $j\ge present[i]$ 且未来价更高。答案为 $f[n][\mathit{\text{budget}}]$。

我们定义 $f[i][j]$ 表示前 $i$ 支股票，预算为 $j$ 时的最大收益。那么答案就是 $f[n][\mathit{\text{budget}}]$。

对于第 $i$ 支股票，我们有两种选择：

• 不购买，那么 $f[i][j]=f[i-1][j]$；
• 购买，那么 $f[i][j]=f[i-1][j-\mathit{\text{present}}[i]]+\mathit{\text{future}}[i]-\mathit{\text{present}}[i]$。

最后返回 $f[n][\mathit{\text{budget}}]$ 即可。

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

func maximumProfit(present []int, future []int, budget int) int {
	n := len(present)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, budget+1)
	}
	for i := 1; i <= n; i++ {
		for j := 0; j <= budget; j++ {
			f[i][j] = f[i-1][j]
			if j >= present[i-1] {
				f[i][j] = max(f[i][j], f[i-1][j-present[i-1]]+future[i-1]-present[i-1])
			}
		}
	}
	return f[n][budget]
}

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

思考

方法一的转移只读上一行，二维表可以压成一维。为避免同一支股票被买两次，预算 $j$ 必须从大到小枚举。时间不变，空间降为 $O(\mathit{\text{budget}})$。

我们可以发现，对于每一行，我们只需要用到上一行的值，因此可以将空间复杂度优化到 $O(\text{budget})$。

func maximumProfit(present []int, future []int, budget int) int {
	f := make([]int, budget+1)
	for i, a := range present {
		for j := budget; j >= a; j-- {
			f[j] = max(f[j], f[j-a]+future[i]-a)
		}
	}
	return f[budget]
}

力扣原题 · Doocs 题解来源

2304. 网格中的最小路径代价

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数矩阵 grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ，且满足 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一个单元格。注意： 在最后一行中的单元格不能触发移动。

每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。

grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。

 

示例 1：

输入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
输出：17
解释：最小代价的路径是 5 -> 0 -> 1 。
- 路径途经单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。

示例 2：

输入：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
输出：6
解释：
最小代价的路径是 2 -> 3 。 
- 路径途经单元格值之和 2 + 3 = 5 。 
- 从 2 移动到 3 的代价为 1 。 
路径总代价为 5 + 1 = 6 。

 

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• grid 由从 0 到 m * n - 1 的不同整数组成
• moveCost.length == m * n
• moveCost[i].length == n
• 1 <= moveCost[i][j] <= 100

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

思考

从第一行走到最后一行，每步必须换行。若搜索全部路径，分支约为 $n^{m-1}$。 $m,n\le 50$ 时不可行。

到达 $(i,j)$ 的最小代价只取决于上一行各列的最优值，以及从上一格走到本格的移动花费。为此按行递推：用上一行的 $n$ 个状态更新本行每一列，并采用滚动数组丢弃更早的行。

我们定义 $f[i][j]$ 表示从第一行出发，到达第 $i$ 行第 $j$ 列的最小路径代价。由于每次只能从上一行的某一列移动到当前行的某一列，因此 $f[i][j]$ 的值可以从 $f[i-1][k]$ 转移而来，其中 $k$ 的取值范围为 $[0,n-1]$。因此状态转移方程为：

$$f[i][j]=\underset{0\le k<n}{min}\{f[i-1][k]+\mathit{\text{moveCost}}[grid[i-1][k]][j]+grid[i][j]\}$$

其中 $\mathit{\text{moveCost}}[grid[i-1][k]][j]$ 表示从第 $i-1$ 行第 $k$ 列移动到第 $i$ 行第 $j$ 列的代价。

最终答案即为 $\underset{0\le j<n}{min}\{f[m-1][j]\}$。

由于每次转移只需要用到上一行的状态，因此我们可以使用滚动数组的方式，将空间复杂度优化到 $O(n)$。

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

func minPathCost(grid [][]int, moveCost [][]int) int {
	m, n := len(grid), len(grid[0])
	f := grid[0]
	for i := 1; i < m; i++ {
		g := make([]int, n)
		for j := 0; j < n; j++ {
			g[j] = 1 << 30
			for k := 0; k < n; k++ {
				g[j] = min(g[j], f[k]+moveCost[grid[i-1][k]][j]+grid[i][j])
			}
		}
		f = g
	}
	return slices.Min(f)
}

力扣原题 · Doocs 题解来源