LeetCode Go · 动态规划（8）

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

来源与许可

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

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

1397. 找到所有好字符串

困难1 种解法

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

题目、示例与约束

给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。

好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。

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

 

示例 1：

输入：n = 2, s1 = "aa", s2 = "da", evil = "b"
输出：51 
解释：总共有 25 个以 'a' 开头的好字符串："aa"，"ac"，"ad"，...，"az"。还有 25 个以 'c' 开头的好字符串："ca"，"cc"，"cd"，...，"cz"。最后，还有一个以 'd' 开头的好字符串："da"。

示例 2：

输入：n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
输出：0 
解释：所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 "leet" 开头。所以没有好字符串。

示例 3：

输入：n = 2, s1 = "gx", s2 = "gz", evil = "x"
输出：2

 

提示：

• s1.length == n
• s2.length == n
• s1 <= s2
• 1 <= n <= 500
• 1 <= evil.length <= 50
• 所有字符串都只包含小写英文字母。

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

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

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

思路：先求 evil 的 KMP 前缀表。用记忆化搜索统计不超过上界 s 的合法字符串，状态记录当前位置、末尾匹配 evil 前缀的长度，以及是否仍贴着上界；枚举下一个字母并沿前缀表回退，完整匹配 evil 的分支立即舍弃。只缓存已脱离上界的状态。最终用 calc(s2)-calc(s1)，再在 s1 合法时补回 s1，并取模。

复杂度：设目标长度为 n，evil 长度为 m，字母表大小为 A=26。源码没有预计算字符转移，每次转移的 KMP 回退最坏为 O(m)，因此时间上界为 O(Anm²)，辅助空间为 O(nm)，包含记忆化表和递归栈。

import "strings"

func findGoodStrings(n int, s1 string, s2 string, evil string) int {
	const mod int = 1e9 + 7
	calcMaxMatchLengths := func(s string) []int {
		n := len(s)
		maxMatchLengths := make([]int, n)
		cnt := 0
		for i := 1; i < n; i++ {
			b := s[i]
			for cnt > 0 && s[cnt] != b {
				cnt = maxMatchLengths[cnt-1]
			}
			if s[cnt] == b {
				cnt++
			}
			maxMatchLengths[i] = cnt
		}
		return maxMatchLengths
	}
	maxMatchLengths := calcMaxMatchLengths(evil)

	// <=s 的好字符串的数目
	calc := func(s string) int {
		dp := make([][]int, n)
		for i := range dp {
			dp[i] = make([]int, len(evil))
			for j := range dp[i] {
				dp[i][j] = -1
			}
		}
		var f func(p, match int, isUpper bool) int
		f = func(p, match int, isUpper bool) (cnt int) {
			if match >= len(evil) {
				return
			}
			if p >= n {
				return 1
			}
			dv := &dp[p][match]
			if !isUpper && *dv >= 0 {
				return *dv
			}
			defer func() {
				if !isUpper {
					*dv = cnt
				}
			}()
			up := byte('z')
			if isUpper {
				up = s[p]
			}
			for c := byte('a'); c <= up; c++ {
				m := match
				for m > 0 && evil[m] != c {
					m = maxMatchLengths[m-1]
				}
				if evil[m] == c {
					m++
				}
				cnt = (cnt + f(p+1, m, isUpper && c == up)) % mod
			}
			return
		}
		return f(0, 0, true)
	}
	ans := calc(s2) - calc(s1)
	if !strings.Contains(s1, evil) {
		ans++
	}
	return (ans%mod + mod) % mod
}

力扣原题 · Doocs 题解来源

1402. 做菜顺序

困难1 种解法

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

题目、示例与约束

一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间（包含之前每道菜所花费的时间）乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。

返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。

你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。

 

示例 1：

输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的 like-time 系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。

示例 2：

输入：satisfaction = [4,3,2]
输出：20
解释：可以按照任意顺序做菜 (2*1 + 3*2 + 4*3 = 20)

示例 3：

输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜就可以获得最大的 like-time 系数。

 

提示：

• n == satisfaction.length
• 1 <= n <= 500
• -1000 <= satisfaction[i] <= 1000

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

思考

对每个子集再枚举烹饪顺序， $n\le 500$ 无法承受。满意度可正可负，空菜单的得分为 $0$，因此只需在「按时间系数放大后的加权和」中取最大者。

同一组菜应让满意度高的菜获得更大的时间系数，故最优顺序必为升序烹饪。从高到低依次纳入一道菜时，总得分的增量恰好等于当前已选菜的满意度之和。

将数组降序排列，累加前缀和 $s$，仅当 $s>0$ 时把 $s$ 加入答案；一旦前缀非正，再纳入更小的菜只会降低得分，随即停止。

假如我们只选择一道菜，那么我们应该选择满意度最大的那道菜 $s_0$，并且判断 $s_0$ 是否大于 0，如果 $s_0\le 0$，那么我们就不做菜了，否则我们做这道菜，得到的总满意度为 $s_0$。

假如我们选择两道菜，那么我们应该选择满足度最大的两道菜 $s_0$ 和 $s_1$，满意度为 $s_1+2\times s_0$，此时要保证选择之后的满意度大于选择之前的满意度，即 $s_1+2\times s_0>s_0$，即 只要满足 $s_1+s_0>0$，我们就可以选择这两道菜。

依此类推，我们可以得到一个规律，即我们应该选择满意度最大的 $k$ 道菜，并且保证前 $k$ 道菜的满意度之和大于 $0$。

在实现上，我们可以先对所有菜的满意度进行排序，然后从满意度最大的菜开始选择，每次累加当前这道菜的满意度，如果累加的结果小于等于 $0$，那么我们就不再选择后面的菜了，否则我们就选择这道菜。

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

func maxSatisfaction(satisfaction []int) (ans int) {
	sort.Slice(satisfaction, func(i, j int) bool { return satisfaction[i] > satisfaction[j] })
	s := 0
	for _, x := range satisfaction {
		s += x
		if s <= 0 {
			break
		}
		ans += s
	}
	return
}

力扣原题 · Doocs 题解来源

1406. 石子游戏 III

困难2 种解法

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

题目、示例与约束

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

 

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

 

提示：

• 1 <= stoneValue.length <= 5 * 104
• -1000 <= stoneValue[i] <= 1000

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

思考

双方每次取 $1$～ $3$ 堆，若直接递归所有取法，状态树随 $n\le 5\times {10}^4$ 迅速膨胀，同一后缀会被反复计算。

对当前玩家而言，只需最大化「本轮取走石子之和减去对手在剩余局面上的最优差值」。定义 $dfs(i)$ 为从下标 $i$ 起的最优得分差，枚举取到 $i,i+1,i+2$ 即可。

对 $dfs(i)$ 记忆化后每个起点只计算一次。 $dfs(0)$ 的正负决定 Alice、Bob 或平局。

我们设计一个函数 $dfs(i)$，表示当前玩家在 $[i,n)$ 范围内进行游戏时，可以获得的最大得分差值。如果 $dfs(0)>0$，则表示先手玩家 Alice 可以获胜；如果 $dfs(0)<0$，则表示后手玩家 Bob 可以获胜；否则，表示两人打成平局。

函数 $dfs(i)$ 的执行逻辑如下：

• 如果 $i\ge n$，说明当前没有石子可以拿了，直接返回 $0$ 即可；
• 否则，我们枚举当前玩家拿走的最后一堆石子的下标 $j$，其中 $i\le j<min(i+3,n)$，即当前玩家拿走下标范围 $[i,j]$ 内的所有石子，得分之和为 $\sum _{k=i}^j\mathit{\text{stoneValue}}[k]$，而另一个玩家在下一轮可以获得的得分差值为 $dfs(j+1)$，从而当前玩家可以获得的得分差值为 $\sum _{k=i}^j\mathit{\text{stoneValue}}[k]-dfs(j+1)$。我们要使得当前玩家的得分差值最大，因此可以用 $max$ 函数得到最大得分差值，即：

$$dfs(i)=\underset{i\le j<min(i+3,n)}{max}\{\sum _{k=i}^j\mathit{\text{stoneValue}}[k]-dfs(j+1)\}$$

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

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是石子的堆数。

func stoneGameIII(stoneValue []int) string {
	n := len(stoneValue)
	f := make([]int, n)

	for i := range f {
		f[i] = -1 << 30
	}

	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}

		if f[i] != -1<<30 {
			return f[i]
		}

		ans := -1 << 30
		s := 0

		for j := i; j < i+3 && j < n; j++ {
			s += stoneValue[j]
			ans = max(ans, s-dfs(j+1))
		}

		f[i] = ans
		return ans
	}

	res := dfs(0)

	if res == 0 {
		return "Tie"
	}
	if res > 0 {
		return "Alice"
	}
	return "Bob"
}

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

思考

双方每次取 $1$～ $3$ 堆。枚举整条对局是指数级的，而 $n\le 5\times {10}^4$。

当前玩家要最大化「本轮取走石子之和减去对手在剩余局面上的最优差值」。从下标 $i$ 出发的差值只依赖 $i+1$、 $i+2$ 与 $i+3$ 三个更靠后的起点。

按这个递推搜索时仍会先调用下一堆再返回，调用链深度为 $n$，栈会溢出。

从末尾往前走时，更靠后的差值已经就绪。令 $f[i]$ 为从 $i$ 起的最优得分差，我们从 $i=n-1$ 填到 $0$，再看 $f[0]$ 的正负。

我们定义 $f[i]$ 表示当前玩家在 $[i,n)$ 范围内进行游戏时，可以获得的最大得分差值。如果 $f[0]>0$，则表示先手玩家 Alice 可以获胜；如果 $f[0]<0$，则表示后手玩家 Bob 可以获胜；否则，表示两人打成平局。

$f[i]$ 的计算方式如下：

• 如果 $i\ge n$，说明当前没有石子可以拿了，值为 $0$；
• 否则，我们枚举当前玩家拿走的最后一堆石子的下标 $j$，其中 $i\le j<min(i+3,n)$，即当前玩家拿走下标范围 $[i,j]$ 内的所有石子，得分之和为 $\sum _{k=i}^j\mathit{\text{stoneValue}}[k]$，而另一个玩家在剩余局面上的最优得分差值为 $f[j+1]$，从而当前玩家可以获得的得分差值为 $\sum _{k=i}^j\mathit{\text{stoneValue}}[k]-f[j+1]$。我们要使得当前玩家的得分差值最大，因此可以用 $max$ 函数得到最大得分差值，即：

$$f[i]=\underset{i\le j<min(i+3,n)}{max}\{\sum _{k=i}^j\mathit{\text{stoneValue}}[k]-f[j+1]\}$$

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

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

func stoneGameIII(stoneValue []int) string {
	n := len(stoneValue)
	f := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		ans := -1 << 30
		s := 0
		for j := i; j < i+3 && j < n; j++ {
			s += stoneValue[j]
			ans = max(ans, s-f[j+1])
		}
		f[i] = ans
	}
	res := f[0]
	if res == 0 {
		return "Tie"
	}
	if res > 0 {
		return "Alice"
	}
	return "Bob"
}

力扣原题 · Doocs 题解来源

1411. 给 N x 3 网格图涂色的方案数

困难2 种解法

标签：动态规划、图的着色

题目、示例与约束

你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。

给你网格图的行数 n 。

请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

 

示例 1：

输入：n = 1
输出：12
解释：总共有 12 种可行的方法：

示例 2：

输入：n = 2
输出：54

示例 3：

输入：n = 3
输出：246

示例 4：

输入：n = 7
输出：106494

示例 5：

输入：n = 5000
输出：30228214

 

提示：

• n == grid.length
• grid[i].length == 3
• 1 <= n <= 5000

方法一：递推 · Go 实现

思考

每格 $3$ 色且相邻不同色， $n\le 5000$，直接给整张网格染色是 $3^{3n}$ 量级。一行仅三格，合法染色可按对称性分成两类： $010$ 型（两色）与 $012$ 型（三色）。

统计两类各自能转移到下一行的方案数，得到 $g_0=3f_0+2f_1$、 $g_1=2f_0+2f_1$。第一行两类各 $6$ 种，递推 $n-1$ 步后求和即可。

把每一行所有可能的状态进行分类。根据对称性原理，当一行只有 $3$ 个元素时，所有合法状态分类为 $010$ 型以及 $012$ 型。

• 当状态为 $010$ 型时：下一行可能的状态为 $101$, $102$, $121$, $201$, $202$。这 $5$ 个状态可归纳为 $3$ 个 $010$ 型，以及 $2$ 个 $012$ 型。
• 当状态为 $012$ 型时：下一行可能的状态为 $101$, $120$, $121$, $201$。这 $4$ 个状态可归纳为 $2$ 个 $010$ 型，以及 $2$ 个 $012$ 型。

综上所述，可以得到 $\text{newf0}=3\times f0+2\times f1$, $\text{newf1}=2\times f0+2\times f1$。

时间复杂度 $O(n)$，其中 $n$ 是网格的行数。空间复杂度 $O(1)$。

func numOfWays(n int) int {
	mod := int(1e9) + 7
	f0, f1 := 6, 6
	for n > 1 {
		n--
		g0 := (f0*3 + f1*2) % mod
		g1 := (f0*2 + f1*2) % mod
		f0, f1 = g0, g1
	}
	return (f0 + f1) % mod
}

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

思考

方法一依赖人工分类转移系数。列数固定为 $3$，一行至多 $3^3=27$ 种涂色，可把合法行状态显式枚举，再预处理行间是否相邻合法。

$f[i][j]$ 表示第 $i$ 行状态为 $j$ 的方案数，由上一行所有相容状态累加。滚动数组后空间只保留一层，实现不必推导封闭系数。

我们注意到，网格只有 $3$ 列，那么一行中最多有 $3^3=27$ 种不同的涂色方案。

因此，我们定义 $f[i][j]$ 表示前 $i$ 行中，第 $i$ 行的涂色状态为 $j$ 的方案数。状态 $f[i][j]$ 由 $f[i-1][k]$ 转移而来，其中 $k$ 是第 $i-1$ 行的涂色状态，且 $k$ 和 $j$ 满足不同颜色相邻的要求。即：

$$f[i][j]=\sum _{k\in \mathit{\text{valid}}(j)}f[i-1][k]$$

其中 $\mathit{\text{valid}}(j)$ 表示状态 $j$ 的所有合法前驱状态。

最终的答案即为 $f[n][j]$ 的总和，其中 $j$ 是任意合法的状态。

我们注意到 $f[i][j]$ 只和 $f[i-1][k]$ 有关，因此我们可以使用滚动数组优化空间复杂度。

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

func numOfWays(n int) (ans int) {
	f1 := func(x int) bool {
		last := -1
		for i := 0; i < 3; i++ {
			if x%3 == last {
				return false
			}
			last = x % 3
			x /= 3
		}
		return true
	}
	f2 := func(x, y int) bool {
		for i := 0; i < 3; i++ {
			if x%3 == y%3 {
				return false
			}
			x /= 3
			y /= 3
		}
		return true
	}
	m := 27
	valid := map[int]bool{}
	f := make([]int, m)
	for i := 0; i < m; i++ {
		if f1(i) {
			valid[i] = true
			f[i] = 1
		}
	}
	d := map[int][]int{}
	for i := range valid {
		for j := range valid {
			if f2(i, j) {
				d[i] = append(d[i], j)
			}
		}
	}
	const mod int = 1e9 + 7
	for k := 1; k < n; k++ {
		g := make([]int, m)
		for i := range valid {
			for _, j := range d[i] {
				g[i] = (g[i] + f[j]) % mod
			}
		}
		f = g
	}
	for _, x := range f {
		ans = (ans + x) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

1416. 恢复数组

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余 后的结果。

 

示例 1：

输入：s = "1000", k = 10000
输出：1
解释：唯一一种可能的数组方案是 [1000]

示例 2：

输入：s = "1000", k = 10
输出：0
解释：不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s 。

示例 3：

输入：s = "1317", k = 2000
输出：8
解释：可行的数组方案为 [1317]，[131,7]，[13,17]，[1,317]，[13,1,7]，[1,31,7]，[1,3,17]，[1,3,1,7]

示例 4：

输入：s = "2020", k = 30
输出：1
解释：唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案，原因是 2020 > 30 。 [2,020] 也不是可行的数组方案，因为 020 含有前导 0 。

示例 5：

输入：s = "1234567890", k = 90
输出：34

 

提示：

• 1 <= s.length <= 10^5.
• s 只包含数字且不包含前导 0 。
• 1 <= k <= 10^9.

方法一 · Go 实现

思考

将数字串切成若干属于 $[1,k]$ 且无前导零的整数， $n\le {10}^5$，枚举所有切法不可行。 $k\le {10}^9$，从某一位置向后延伸的合法数字长度不超过 $10$。

定义 $f(i)$ 为后缀 $s[i:]$ 的恢复方案数：若 $s[i]{=}^{\prime }{0}^{\prime }$ 则无法开始；否则枚举结束位置 $j$，在数值 $\le k$ 时累加 $f(j+1)$。对 $f(i)$ 记忆化或改写成从右向左的线性 DP。

从右往左计算 $f(i)$， $f(n)=1$。 $s[i]{=}^{\prime }{0}^{\prime }$ 时 $f(i)=0$；否则从下标 $i$ 起向右拼数，数值一旦大于 $k$ 就停止，并把每个合法切点后的 $f(j+1)$ 累加进 $f(i)$。答案是 $f(0)$，对 ${10}^9+7$ 取模。

时间复杂度 $O(n\times d)$，空间复杂度 $O(n)$。其中 $n$ 是 $s$ 的长度， $d$ 是 $k$ 的十进制位数，不超过 $10$。

func numberOfArrays(s string, k int) int {
	const mod = int(1e9 + 7)
	n := len(s)
	f := make([]int, n+1)
	f[n] = 1
	for i := n - 1; i >= 0; i-- {
		if s[i] == '0' {
			continue
		}
		x := 0
		for j := i; j < n; j++ {
			x = x*10 + int(s[j]-'0')
			if x > k {
				break
			}
			f[i] = (f[i] + f[j+1]) % mod
		}
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

1420. 生成数组

困难1 种解法

标签：动态规划、前缀和

题目、示例与约束

给定三个整数 n、m 和 k 。考虑使用下图描述的算法找出正整数数组中最大的元素。

请你构建一个具有以下属性的数组 arr ：

• arr 中包含确切的 n 个整数。
• 1 <= arr[i] <= m 其中 (0 <= i < n) 。
• 将上面提到的算法应用于 arr 之后，search_cost 的值等于 k 。

返回在满足上述条件的情况下构建数组 arr 的 方法数量 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。

 

示例 1：

输入：n = 2, m = 3, k = 1
输出：6
解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

示例 2：

输入：n = 5, m = 2, k = 3
输出：0
解释：没有数组可以满足上述条件

示例 3：

输入：n = 9, m = 1, k = 1
输出：1
解释：唯一可能的数组是 [1, 1, 1, 1, 1, 1, 1, 1, 1]

 

提示：

• 1 <= n <= 50
• 1 <= m <= 100
• 0 <= k <= n

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

思考

搜索代价等于从左到右刷新最大值的次数。 $n\le 50$、 $m\le 100$，枚举全部数组不可行，需按「长度、代价、当前最大值」递推。

第 $i$ 位若不刷新最大值，可在 $[1,j]$ 中任取，方案数为上一层同代价、同最大值乘 $j$；若恰好写入新最大值 $j$，则由更小最大值、代价减一的状态累加。

$k=0$ 不可能。对 $dp[n][k][\cdot ]$ 求和即答案。

假设 $dp[i][c][j]$ 表示长度为 $i$，搜索代价为 $c$，且最大值为 $j$ 的方案数。考虑第 $i$ 个数：

若第 $i$ 个数没有改变搜索代价，说明它不严格大于前 $i-1$ 个数，也就是说， $dp[i][c][j]$ 是从 $dp[i-1][c][j]$ 转移而来，即数组的前 $i-1$ 个数的最大值已经是 $j$，并且第 $i$ 个数没有改变最大值，因此第 $i$ 个数的可选范围是 $[1,..j]$，共有 $j$ 种可选方案。即

$$dp[i][c][j]=dp[i-1][c][j]\times j$$

若第 $i$ 个数改变了搜索代价，说明数组前 $i-1$ 个数的最大值小于 $j$，并且第 $i$ 个数恰好为 $j$。此时 $dp[i][c][j]$ 是从所有 $dp[i-1][c-1][j^{\prime }]$ 转移而来，其中 $j^{\prime }<j$。即

$$dp[i][c][j]=\sum _{j^{\prime }=1}^{j-1}dp[i-1][c-1][j^{\prime }]$$

综上，可得

$$dp[i][c][j]=dp[i-1][c][j]\times j+\sum _{j^{\prime }=1}^{j-1}dp[i-1][c-1][j^{\prime }]$$

答案为

$$\sum _{j=1}^{m}dp[n][k][j]$$

时间复杂度 $O(nk{m}^2)$。

func numOfArrays(n int, m int, k int) int {
	if k == 0 {
		return 0
	}
	mod := int(1e9) + 7
	dp := make([][][]int, n+1)
	for i := range dp {
		dp[i] = make([][]int, k+1)
		for j := range dp[i] {
			dp[i][j] = make([]int, m+1)
		}
	}
	for i := 1; i <= m; i++ {
		dp[1][1][i] = 1
	}
	for i := 2; i <= n; i++ {
		for c := 1; c <= k && c <= i; c++ {
			for j := 1; j <= m; j++ {
				dp[i][c][j] = (dp[i-1][c][j] * j) % mod
				for j0 := 1; j0 < j; j0++ {
					dp[i][c][j] = (dp[i][c][j] + dp[i-1][c-1][j0]) % mod
				}
			}
		}
	}
	ans := 0
	for i := 1; i <= m; i++ {
		ans = (ans + dp[n][k][i]) % mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

1425. 带限制的子序列和

困难1 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

 

示例 1：

输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。

示例 2：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

示例 3：

输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

 

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

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

思考

子序列相邻下标差至多为 $k$，求最大和。 $n\le {10}^5$，若对每个 $i$ 枚举 $[i-k,i-1]$ 的最优 $f$，则达到 $O(nk)$。

$f[i]=\mathit{\text{nums}}[i]+max(0,\underset{i-k\le j<i}{max}f[j])$，即长度为 $k$ 的窗口最大值。单调递减队列按 $f$ 维护下标，队首过期则弹出，转移成为摊还 $O(1)$。

元素可为负，因此允许「不接前缀」而单独从 $i$ 开始。答案取所有 $f[i]$ 的最大者。

我们定义 $f[i]$ 表示以 $\mathit{\text{nums}}[i]$ 结尾的满足条件的子序列的最大和。初始时 $f[i]=0$，答案为 $\underset{0\le i<n}{max}f(i)$。

我们注意到题目需要我们维护滑动窗口的最大值，这就是一个典型的单调队列应用场景。我们可以使用单调队列来优化动态规划的转移。

我们维护一个从队首到队尾单调递减的单调队列 $q$，队列中存储的是下标 $i$，初始时，我们将一个哨兵 $0$ 加入队列中。

我们遍历 $i$ 从 $0$ 到 $n-1$，对于每个 $i$，我们执行以下操作：

• 如果队首元素 $q[0]$ 满足 $i-q[0]>k$，说明队首元素已经不在滑动窗口内，我们需要从队首弹出队首元素；
• 然后，我们计算 $f[i]=max(0,f[q[0]])+\mathit{\text{nums}}[i]$，表示我们将 $\mathit{\text{nums}}[i]$ 加入滑动窗口后的最大子序列和；
• 接下来，我们更新答案 $\mathit{\text{ans}}=max(\mathit{\text{ans}},f[i])$；
• 最后，我们将 $i$ 加入队列尾部，并且保持队列的单调性，即如果 $f[q[\mathit{\text{back}}]]\le f[i]$，我们需要将队尾元素弹出，直到队列为空或者 $f[q[\mathit{\text{back}}]]>f[i]$。

最终答案即为 $\mathit{\text{ans}}$。

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

func constrainedSubsetSum(nums []int, k int) int {
	q := Deque{}
	q.PushFront(0)
	n := len(nums)
	f := make([]int, n)
	ans := nums[0]
	for i, x := range nums {
		for i-q.Front() > k {
			q.PopFront()
		}
		f[i] = max(0, f[q.Front()]) + x
		ans = max(ans, f[i])
		for !q.Empty() && f[q.Back()] <= f[i] {
			q.PopBack()
		}
		q.PushBack(i)
	}
	return ans
}

// template
type Deque struct{ l, r []int }

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

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

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

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

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

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

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

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

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

力扣原题 · Doocs 题解来源

1434. 每个人戴不同帽子的方案数

困难1 种解法

标签：位运算、数组、动态规划、位掩码、二分图、图的匹配、完美匹配

题目、示例与约束

总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。

给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。

由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。

 

示例 1：

输入：hats = [[3,4],[4,5],[5]]
输出：1
解释：给定条件下只有一种方法选择帽子。
第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。

示例 2：

输入：hats = [[3,5,1],[3,5]]
输出：4
解释：总共有 4 种安排帽子的方法：
(3,5)，(5,3)，(1,3) 和 (1,5)

示例 3：

输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
输出：24
解释：每个人都可以从编号为 1 到 4 的帽子中选。
(1,2,3,4) 4 个帽子的排列方案数为 24 。

 

提示：

• n == hats.length
• 1 <= n <= 10
• 1 <= hats[i].length <= 40
• 1 <= hats[i][j] <= 40
• hats[i] 包含一个数字互不相同的整数列表。

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

思考

人只有 $n\le 10$，帽子至多 $40$ 种。若按人分配帽子，每人最多 $40$ 个选择且要互不相同，状态不易压缩。改为枚举帽子，用二进制记录哪些人已戴帽。

$f[i][j]$ 表示考虑前 $i$ 顶帽子、已分配集合为 $j$ 的方案。第 $i$ 顶可不戴，或戴给喜欢它且尚未戴帽的人 $k$。答案为 $f[m][2^n-1]$。

我们注意到 $n$ 不超过 $10$，因此我们考虑使用状态压缩动态规划的方法求解。

我们定义 $f[i][j]$ 表示在前 $i$ 个帽子中，当前被分配的人的状态为 $j$ 时的方案数。其中 $j$ 是一个二进制数，表示当前被分配的人的集合。初始时 $f[0][0]=1$，答案为 $f[m][2^n-1]$，其中 $m$ 是帽子的最大编号，而 $n$ 是人的数量。

考虑 $f[i][j]$，如果第 $i$ 个帽子不分配给任何人，那么 $f[i][j]=f[i-1][j]$；如果第 $i$ 个帽子分配给了喜欢它的人 $k$，那么 $f[i][j]=f[i-1][j\oplus 2^k]$。这里 $\oplus$ 表示异或运算。因此我们可以得到状态转移方程：

$$f[i][j]=f[i-1][j]+\sum _{k\in like[i]}f[i-1][j\oplus 2^k]$$

其中 $like[i]$ 表示喜欢第 $i$ 个帽子的人的集合。

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

时间复杂度 $O(m\times 2^n\times n)$，空间复杂度 $O(m\times 2^n)$。其中 $m$ 是帽子的最大编号，本题中 $m\le 40$；而 $n$ 是人的数量，本题中 $n\le 10$。

func numberWays(hats [][]int) int {
	n := len(hats)
	m := 0
	for _, h := range hats {
		m = max(m, slices.Max(h))
	}
	g := make([][]int, m+1)
	for i, h := range hats {
		for _, v := range h {
			g[v] = append(g[v], i)
		}
	}
	const mod = 1e9 + 7
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, 1<<n)
	}
	f[0][0] = 1
	for i := 1; i <= m; i++ {
		for j := 0; j < 1<<n; j++ {
			f[i][j] = f[i-1][j]
			for _, k := range g[i] {
				if j>>k&1 == 1 {
					f[i][j] = (f[i][j] + f[i-1][j^(1<<k)]) % mod
				}
			}
		}
	}
	return f[m][(1<<n)-1]
}

力扣原题 · Doocs 题解来源

1444. 切披萨的方案数

困难1 种解法

标签：记忆化、数组、动态规划、矩阵、前缀和

题目、示例与约束

给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。

切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。

 

示例 1：

输入：pizza = ["A..","AAA","..."], k = 3
输出：3 
解释：上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。

示例 2：

输入：pizza = ["A..","AA.","..."], k = 3
输出：1

示例 3：

输入：pizza = ["A..","A..","..."], k = 1
输出：1

 

提示：

• 1 <= rows, cols <= 50
• rows == pizza.length
• cols == pizza[i].length
• 1 <= k <= 10
• pizza 只包含字符 'A' 和 '.' 。

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

思考

每次横切或竖切，且切下的部分必须含苹果。 $rows,cols\le 50$， $k\le 10$，枚举切法树会重复计算同一剩余矩形与剩余刀数。

二维前缀和在 $O(1)$ 内判断一块是否含苹果。 $dfs(i,j,k)$ 表示左上角为 $(i,j)$ 的剩余披萨再切 $k$ 刀的方案：枚举合法水平/垂直切线，递归右下块。 $k=0$ 时剩余块有苹果则计 $1$。

我们可以使用二维前缀和来快速计算出每个子矩形中苹果的数量，定义 $s[i][j]$ 表示矩形前 $i$ 行，前 $j$ 列的子矩形中苹果的数量，那么 $s[i][j]$ 可以由 $s[i-1][j]$, $s[i][j-1]$, $s[i-1][j-1]$ 三个子矩形的苹果数量求得，具体的计算方法如下：

$$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+\mathit{\text{int}}(pizza[i-1][j-1]={=}^{\prime }{A}^{\prime })$$

其中 $pizza[i-1][j-1]$ 表示矩形中第 $i$ 行，第 $j$ 列的字符，如果是苹果，则为 $1$，否则为 $0$。

接下来，我们设计一个函数 $dfs(i,j,k)$，表示将矩形 $(i,j,m-1,n-1)$ 切 $k$ 刀，得到 $k+1$ 块披萨的方案数，其中 $(i,j)$ 和 $(m-1,n-1)$ 分别是矩形的左上角和右下角的坐标。函数 $dfs(i,j,k)$ 的计算方法如下：

• 如果 $k=0$，表示没有可以切了，那么我们需要判断矩形中是否有苹果，如果有苹果，则返回 $1$，否则返回 $0$；
• 如果 $k>0$，我们需要枚举最后一刀的切法，如果最后一刀是水平切，那么我们需要枚举切的位置 $x$，其中 $i<x<m$，如果 $s[x][n]-s[i][n]-s[x][j]+s[i][j]>0$，说明切出来的上面一块披萨中有苹果，我们累加 $dfs(x,j,k-1)$ 的值到答案中；如果最后一刀是垂直切，那么我们需要枚举切的位置 $y$，其中 $j<y<n$，如果 $s[m][y]-s[i][y]-s[m][j]+s[i][j]>0$，说明切出来的左边一块披萨中有苹果，我们累加 $dfs(i,y,k-1)$ 的值到答案中。

最终的答案即为 $dfs(0,0,k-1)$ 的值。

为了避免重复计算，我们可以使用记忆化搜索的方法，用一个三维数组 $f$ 来记录 $dfs(i,j,k)$ 的值。当我们需要计算 $dfs(i,j,k)$ 的值时，如果 $f[i][j][k]$ 不为 $-1$，说明我们之前已经计算过了，直接返回 $f[i][j][k]$ 即可，否则我们按照上面的方法计算 $dfs(i,j,k)$ 的值，并将结果保存到 $f[i][j][k]$ 中。

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

相似题目：

• 2312. 卖木头块

func ways(pizza []string, k int) int {
	const mod = 1e9 + 7
	m, n := len(pizza), len(pizza[0])
	f := make([][][]int, m)
	s := make([][]int, m+1)
	for i := range f {
		f[i] = make([][]int, n)
		for j := range f[i] {
			f[i][j] = make([]int, k)
			for h := range f[i][j] {
				f[i][j][h] = -1
			}
		}
	}
	for i := range s {
		s[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1]
			if pizza[i-1][j-1] == 'A' {
				s[i][j]++
			}
		}
	}
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if f[i][j][k] != -1 {
			return f[i][j][k]
		}
		if k == 0 {
			if s[m][n]-s[m][j]-s[i][n]+s[i][j] > 0 {
				return 1
			}
			return 0
		}
		ans := 0
		for x := i + 1; x < m; x++ {
			if s[x][n]-s[x][j]-s[i][n]+s[i][j] > 0 {
				ans = (ans + dfs(x, j, k-1)) % mod
			}
		}
		for y := j + 1; y < n; y++ {
			if s[m][y]-s[m][j]-s[i][y]+s[i][j] > 0 {
				ans = (ans + dfs(i, y, k-1)) % mod
			}
		}
		f[i][j][k] = ans
		return ans
	}
	return dfs(0, 0, k-1)
}

力扣原题 · Doocs 题解来源

1449. 数位成本和为目标值的最大数字

困难1 种解法

标签：数组、动态规划、背包问题、完全背包

题目、示例与约束

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

• 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
• 总成本必须恰好等于 target 。
• 添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0" 。

 

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

示例 2：

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3：

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。

示例 4：

输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"

 

提示：

• cost.length == 9
• 1 <= cost[i] <= 5000
• 1 <= target <= 5000

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

思考

数位 $1$～ $9$ 各有花费，可重复使用，目标和为 $target$。要字典序最大的整数，应先让位数尽量多，同长度再尽量用大数字。

$f[i][j]$ 为使用前 $i$ 种数位、花费恰为 $j$ 的最大位数，完全背包转移；用 $g[i][j]$ 记录是否选取数字 $i$，以便从大到小回溯。无法凑成则返回 0。

我们定义 $f[i][j]$ 表示使用前 $i$ 个数位，花费恰好为 $j$ 的情况下，能够得到的最大位数。初始时， $f[0][0]=0$，其余为 $-\mathrm{\infty }$。

考虑 $f[i][j]$，第 $i$ 个数的花费为 $c=cost[i-1]$，如果 $j<c$，那么我们无法选取第 $i$ 个数位，此时有 $f[i][j]=f[i-1][j]$；否则我们可以选取第 $i$ 个数位，此时有 $f[i][j]=f[i][j-c]+1$。

如果 $f[9][target]<0$，那么说明无法得到满足要求的整数，返回 "0" 即可。

否则，我们需要从 $f[9][target]$ 开始，倒推出每一位的数字。我们可以使用一个数组 $g[i][j]$ 记录 $f[i][j]$ 的上一个状态，从而倒推出每一位的数字。

具体地，在状态转移时，如果 $j<c$，或者 $f[i][j-c]+1<f[i-1][j]$，那么我们不选取第 $i$ 个数位，此时有 $g[i][j]=j$；否则我们选取第 $i$ 个数位，此时有 $g[i][j]=j-c$。

最后，我们定义 $i=9$, $j=target$，从 $g[i][j]$ 开始不断地倒推，如果 $g[i][j]=j$，说明数字 $i$ 没有被选取，我们令 $i=i-1$；否则说明数字 $i$ 被选取，我们令 $j=g[i][j]$，并将数字 $i$ 加入答案中。重复上述操作，直到 $i=0$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别为数组 $cost$ 和 $target$ 的长度。

func largestNumber(cost []int, target int) string {
	const inf = 1 << 30
	f := make([][]int, 10)
	g := make([][]int, 10)
	for i := range f {
		f[i] = make([]int, target+1)
		g[i] = make([]int, target+1)
		for j := range f[i] {
			f[i][j] = -inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= 9; i++ {
		c := cost[i-1]
		for j := 0; j <= target; j++ {
			if j < c || f[i][j-c]+1 < f[i-1][j] {
				f[i][j] = f[i-1][j]
				g[i][j] = j
			} else {
				f[i][j] = f[i][j-c] + 1
				g[i][j] = j - c
			}
		}
	}
	if f[9][target] < 0 {
		return "0"
	}
	ans := []byte{}
	for i, j := 9, target; i > 0; {
		if g[i][j] == j {
			i--
		} else {
			ans = append(ans, '0'+byte(i))
			j = g[i][j]
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1458. 两个子序列的最大点积

困难1 种解法

标签：数组、动态规划、最长公共子序列

题目、示例与约束

给你两个数组 nums1 和 nums2 。

请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

 

示例 1：

输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6]
输出：18
解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。

示例 2：

输入：nums1 = [3,-2], nums2 = [2,-6,7]
输出：21
解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。

示例 3：

输入：nums1 = [-1,-1], nums2 = [1,1]
输出：-1
解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。

 

提示：

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 1000

 

点积：

定义 a = [a1, a2,…, an] 和 b = [b1, b2,…, bn] 的点积为：



这里的 Σ 指示总和符号。

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

思考

子序列须非空，元素可正可负， $m,n\le 500$。若按 LCS 只取正贡献会漏掉「只能选一对负数乘积」的情形。

$f[i][j]$ 表示两数组前缀的最大点积：可丢掉 $nums1[i-1]$ 或 $nums2[j-1]$，也可强制配对，并允许丢弃此前的负前缀（ $max(0,f[i-1][j-1])+x\cdot y$）。初值 $-\mathrm{\infty }$ 保证至少选一对。

我们定义 $f[i][j]$ 表示 $\mathit{\text{nums1}}$ 的前 $i$ 个元素和 $\mathit{\text{nums2}}$ 的前 $j$ 个元素构成的两个子序列的最大点积。初始时 $f[i][j]=-\mathrm{\infty }$。

对于 $f[i][j]$，我们有以下几种情况：

1. 不选 $\mathit{\text{nums1}}[i-1]$ 或者不选 $\mathit{\text{nums2}}[j-1]$，即 $f[i][j]=max(f[i-1][j],f[i][j-1])$；
2. 选 $\mathit{\text{nums1}}[i-1]$ 和 $\mathit{\text{nums2}}[j-1]$，即 $f[i][j]=max(f[i][j],max(0,f[i-1][j-1])+\mathit{\text{nums1}}[i-1]\times \mathit{\text{nums2}}[j-1])$。

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

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是数组 $\mathit{\text{nums1}}$ 和 $\mathit{\text{nums2}}$ 的长度。

func maxDotProduct(nums1 []int, nums2 []int) int {
	m, n := len(nums1), len(nums2)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
		for j := range f[i] {
			f[i][j] = math.MinInt32
		}
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			v := nums1[i-1] * nums2[j-1]
			f[i][j] = max(f[i-1][j], f[i][j-1])
			f[i][j] = max(f[i][j], max(0, f[i-1][j-1])+v)
		}
	}
	return f[m][n]
}

力扣原题 · Doocs 题解来源

1463. 摘樱桃 II

困难2 种解法

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

题目、示例与约束

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

• 从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
• 当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
• 当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
• 两个机器人在任意时刻都不能移动到 grid 外面。
• 两个机器人最后都要到达 grid 最底下一行。

 

示例 1：

输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出：24
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为： 12 + 12 = 24 。

示例 2：

输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出：28
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为： 17 + 11 = 28 。

示例 3：

输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出：22

示例 4：

输入：grid = [[1,1],[1,1]]
输出：4

 

提示：

• rows == grid.length
• cols == grid[i].length
• 2 <= rows, cols <= 70
• 0 <= grid[i][j] <= 100 

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

思考

两个机器人同行向下，各可左/中/右一列。 $rows,cols\le 70$，分别搜索路径会重复计算。同行同步后状态只需「行、两人列号」。

$f[i][j_1][j_2]$ 为两人在第 $i$ 行处于 $j_1,j_2$ 时的最大樱桃；同格只计一次。由上一行九种相邻列转移。答案取最后一行最大值。

我们定义 $f[i][j_1][j_2]$ 表示两个机器人分别在第 $i$ 行的位置 $j_1$ 和 $j_2$ 时能够摘到的最多樱桃数目。初始时 $f[0][0][n-1]=grid[0][0]+grid[0][n-1]$，其余值均为 $-1$。答案为 $\underset{0\le j_1,j_2<n}{max}f[m-1][j_1][j_2]$。

考虑 $f[i][j_1][j_2]$，如果 $j_1\ne j_2$，那么机器人在第 $i$ 行能摘到的樱桃数目为 $grid[i][j_1]+grid[i][j_2]$；如果 $j_1=j_2$，那么机器人在第 $i$ 行能摘到的樱桃数目为 $grid[i][j_1]$。我们可以枚举两个机器人的上一个状态 $f[i-1][y1][y2]$，其中 $y_1,y_2$ 分别是两个机器人在第 $i-1$ 行的位置，那么有 $y_1\in \{j_1-1,j_1,j_1+1\}$ 且 $y_2\in \{j_2-1,j_2,j_2+1\}$。状态转移方程如下：

$$f[i][j_1][j_2]=\underset{y_1\in \{j_1-1,j_1,j_1+1\},y_2\in \{j_2-1,j_2,j_2+1\}}{max}f[i-1][y_1][y_2]+\{\begin{array}{ll}grid[i][j_1]+grid[i][j_2],& j_1\ne j_2\\ grid[i][j_1],& j_1=j_2\end{array}$$

其中 $f[i-1][y_1][y_2]$ 为 $-1$ 时需要忽略。

最终的答案即为 $\underset{0\le j_1,j_2<n}{max}f[m-1][j_1][j_2]$。

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

func cherryPickup(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 j := range f[i] {
			f[i][j] = make([]int, n)
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	f[0][0][n-1] = grid[0][0] + grid[0][n-1]
	for i := 1; i < m; i++ {
		for j1 := 0; j1 < n; j1++ {
			for j2 := 0; j2 < n; j2++ {
				x := grid[i][j1]
				if j1 != j2 {
					x += grid[i][j2]
				}
				for y1 := j1 - 1; y1 <= j1+1; y1++ {
					for y2 := j2 - 1; y2 <= j2+1; y2++ {
						if y1 >= 0 && y1 < n && y2 >= 0 && y2 < n && f[i-1][y1][y2] != -1 {
							f[i][j1][j2] = max(f[i][j1][j2], f[i-1][y1][y2]+x)
						}
					}
				}
			}
		}
	}
	for j1 := 0; j1 < n; j1++ {
		ans = max(ans, slices.Max(f[m-1][j1]))
	}
	return
}

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

思考

方法一的第 $i$ 层只依赖第 $i-1$ 层，用两张 $n\times n$ 表滚动即可，时间不变、空间少一维。

注意到 $f[i][j_1][j_2]$ 的计算只和 $f[i-1][y_1][y_2]$ 有关，因此我们可以使用滚动数组优化空间复杂度，空间复杂度优化后的时间复杂度为 $O(n^2)$。

func cherryPickup(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	f := make([][]int, n)
	g := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		g[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
			g[i][j] = -1
		}
	}
	f[0][n-1] = grid[0][0] + grid[0][n-1]
	for i := 1; i < m; i++ {
		for j1 := 0; j1 < n; j1++ {
			for j2 := 0; j2 < n; j2++ {
				x := grid[i][j1]
				if j1 != j2 {
					x += grid[i][j2]
				}
				for y1 := j1 - 1; y1 <= j1+1; y1++ {
					for y2 := j2 - 1; y2 <= j2+1; y2++ {
						if y1 >= 0 && y1 < n && y2 >= 0 && y2 < n && f[y1][y2] != -1 {
							g[j1][j2] = max(g[j1][j2], f[y1][y2]+x)
						}
					}
				}
			}
		}
		f, g = g, f
	}
	for j1 := 0; j1 < n; j1++ {
		ans = max(ans, slices.Max(f[j1]))
	}
	return
}

力扣原题 · Doocs 题解来源

1467. 两个盒子中球的颜色数相同的概率

困难1 种解法

标签：数组、数学、动态规划、回溯、组合数学、概率与统计

题目、示例与约束

桌面上有 2n 个颜色不完全相同的球，球的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。

所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。

注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例的解释部分）。

请返回「两个盒子中球的颜色数相同」的情况的概率。答案与真实值误差在 10-5 以内，则被视为正确答案

 

示例 1：

输入：balls = [1,1]
输出：1.00000
解释：球平均分配的方式只有两种：
- 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子
- 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子
这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。

示例 2：

输入：balls = [2,1,1]
输出：0.66667
解释：球的列表为 [1, 1, 2, 3]
随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 1/12 ：
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。
这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
概率 = 8/12 = 0.66667

示例 3：

输入：balls = [1,2,1,2]
输出：0.60000
解释：球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
概率 = 108 / 180 = 0.6 。

 

提示：

• 1 <= balls.length <= 8
• 1 <= balls[i] <= 6
• sum(balls) 是偶数

方法一：记忆化搜索 + 组合数学 · Go 实现

思考

共 $2n$ 个球均分，总方案为 $C_{2n}^n$。颜色种数 $\le 8$、每种至多 $6$ 个，可按颜色枚举放进第一盒的个数。

$dfs(i,j,\mathit{\text{diff}})$：处理第 $i$ 色、第一盒还剩 $j$ 个空位、两盒颜色数之差为 $\mathit{\text{diff}}$。全放一侧会改变 $diff$，两边都有则差不变，乘以组合数 $\mathrm{comb}(balls[i],x)$。合法终态除以总方案即概率。

我们知道 $2n$ 个球，平均分到两个盒子中，总共有 $C_{2n}^n$ 种分法。接下来，我们可以求出每种分法中，两个盒子中球的颜色数相同的情况数。最后，将两者相除即可。

我们可以预处理出组合数 $C_n^m$，然后使用记忆化搜索求解。

设计一个函数 $dfs(i,j,diff)$，表示当前从第 $i$ 种球开始，第一个盒子剩余可放置 $j$ 个球，两个盒子中球的颜色数的差为 $diff$ 的方案数。

函数 $dfs(i,j,diff)$ 的执行逻辑如下：

• 如果 $i\ge k$，表示所有球都已经放完，如果 $j=0$ 且 $diff=0$，表示两个盒子中球的颜色数相同，返回 $1$，否则返回 $0$；
• 如果 $j<0$，表示第一个盒子中球的数量超过了 $n$，返回 $0$；
• 如果 $f[i][j][diff]$ 不为 $-1$，表示已经计算过，直接返回 $f[i][j][diff]$；
• 否则，枚举第 $i$ 种球放入第一个盒子中的数量 $x$，则第 $i$ 种球放入第二个盒子中的数量为 $balls[i]-x$，两个盒子中球的颜色数的变化量为 $y$。如果所有球都放入第一个盒子中，那么 $y=1$；如果所有球都放入第二个盒子中，那么 $y=-1$；否则 $y=0$。然后，递归计算 $dfs(i+1,j-x,diff+y)$，并将结果与 $C_{balls[i]}^x$ 相乘，累加到答案中。最后，将答案存入 $f[i][j][diff]$ 中，并返回答案。

时间复杂度 $O(n^2\times k^2)$，空间复杂度 $O(n\times k^2)$。其中 $n$ 和 $k$ 分别是球的总数和颜色的种数。

func getProbability(balls []int) float64 {
	n, mx := 0, 0
	for _, x := range balls {
		n += x
		mx = max(mx, x)
	}
	n >>= 1
	m := max(mx, n<<1)
	c := make([][]int, m+1)
	for i := range c {
		c[i] = make([]int, m+1)
	}
	for i := 0; i <= m; i++ {
		c[i][0] = 1
		for j := 1; j <= i; j++ {
			c[i][j] = c[i-1][j-1] + c[i-1][j]
		}
	}
	k := len(balls)
	f := make([][][]int, k)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, k<<1|1)
			for h := range f[i][j] {
				f[i][j][h] = -1
			}
		}
	}
	var dfs func(int, int, int) int
	dfs = func(i, j, diff int) int {
		if i >= k {
			if j == 0 && diff == k {
				return 1
			}
			return 0
		}
		if j < 0 {
			return 0
		}
		if f[i][j][diff] != -1 {
			return f[i][j][diff]
		}
		ans := 0
		for x := 0; x <= balls[i]; x++ {
			y := 1
			if x != balls[i] {
				if x == 0 {
					y = -1
				} else {
					y = 0
				}
			}
			ans += dfs(i+1, j-x, diff+y) * c[balls[i]][x]
		}
		f[i][j][diff] = ans
		return ans
	}
	return float64(dfs(0, n, k)) / float64(c[n<<1][n])
}

力扣原题 · Doocs 题解来源

1473. 粉刷房子 III

困难1 种解法

标签：数组、动态规划

题目、示例与约束

在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区  [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：

• houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。
• cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。

 

示例 1：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。

示例 2：

输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。

示例 3：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5

示例 4：

输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。

 

提示：

• m == houses.length == cost.length
• n == cost[i].length
• 1 <= m <= 100
• 1 <= n <= 20
• 1 <= target <= m
• 0 <= houses[i] <= n
• 1 <= cost[i][j] <= 10^4

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

思考

要把 $m$ 栋房子涂成恰好 $target$ 个街区，未涂色的房子需付费。房子与颜色都不多，状态取「涂到第 $i$ 栋、当前颜色 $j$、街区数 $k$」。

已涂色则颜色固定、花费为 $0$；未涂色则枚举颜色并加 $cost$。与上一栋同色则街区数不变，异色则加一。取最后一栋各颜色在 $target$ 街区下的最小花费，不可行则为 $-1$。

我们定义 $f[i][j][k]$ 表示将下标 $[0,..i]$ 的房子涂上颜色，最后一个房子的颜色为 $j$，且恰好形成 $k$ 个街区的最小花费。那么答案就是 $f[m-1][j][\mathit{\text{target}}]$，其中 $j$ 的取值范围为 $[1,..n]$。初始时，我们判断下标为 $0$ 的房子是否已经涂色，如果未涂色，那么 $f[0][j][1]=\mathit{\text{cost}}[0][j-1]$，其中 $j\in [1,..n]$。如果已经涂色，那么 $f[0][\mathit{\text{houses}}[0]][1]=0$。其他的 $f[i][j][k]$ 的值都初始化为 $\mathrm{\infty }$。

接下来，我们从下标 $i=1$ 开始遍历，对于每个 $i$，我们判断下标为 $i$ 的房子是否已经涂色：

如果未涂色，那么我们可以将下标为 $i$ 的房子涂成颜色 $j$，我们枚举街区的数量 $k$，其中 $k\in [1,..min(\mathit{\text{target}},i+1)]$，并且枚举下标为 $i$ 的房子的前一个房子的颜色 $j_0$，其中 $j_0\in [1,..n]$，那么我们可以得到状态转移方程：

$$f[i][j][k]=\underset{j_0\in [1,..n]}{min}\{f[i-1][j_0][k-(j\ne j_0)]+\mathit{\text{cost}}[i][j-1]\}$$

如果已经涂色，那么我们可以将下标为 $i$ 的房子涂成颜色 $j$，我们枚举街区的数量 $k$，其中 $k\in [1,..min(\mathit{\text{target}},i+1)]$，并且枚举下标为 $i$ 的房子的前一个房子的颜色 $j_0$，其中 $j_0\in [1,..n]$，那么我们可以得到状态转移方程：

$$f[i][j][k]=\underset{j_0\in [1,..n]}{min}\{f[i-1][j_0][k-(j\ne j_0)]\}$$

最后，我们返回 $f[m-1][j][\mathit{\text{target}}]$，其中 $j\in [1,..n]$，如果所有的 $f[m-1][j][\mathit{\text{target}}]$ 的值都为 $\mathrm{\infty }$，那么返回 $-1$。

时间复杂度 $O(m\times n^2\times \mathit{\text{target}})$，空间复杂度 $O(m\times n\times \mathit{\text{target}})$。其中 $m$, $n$, $\mathit{\text{target}}$ 分别为房子的数量，颜色的数量，街区的数量。

func minCost(houses []int, cost [][]int, m int, n int, target int) int {
	f := make([][][]int, m)
	const inf = 1 << 30
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, target+1)
			for k := range f[i][j] {
				f[i][j][k] = inf
			}
		}
	}
	if houses[0] == 0 {
		for j := 1; j <= n; j++ {
			f[0][j][1] = cost[0][j-1]
		}
	} else {
		f[0][houses[0]][1] = 0
	}
	for i := 1; i < m; i++ {
		if houses[i] == 0 {
			for j := 1; j <= n; j++ {
				for k := 1; k <= target && k <= i+1; k++ {
					for j0 := 1; j0 <= n; j0++ {
						if j == j0 {
							f[i][j][k] = min(f[i][j][k], f[i-1][j][k]+cost[i][j-1])
						} else {
							f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1]+cost[i][j-1])
						}
					}
				}
			}
		} else {
			j := houses[i]
			for k := 1; k <= target && k <= i+1; k++ {
				for j0 := 1; j0 <= n; j0++ {
					if j == j0 {
						f[i][j][k] = min(f[i][j][k], f[i-1][j][k])
					} else {
						f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1])
					}
				}
			}
		}
	}
	ans := inf
	for j := 1; j <= n; j++ {
		ans = min(ans, f[m-1][j][target])
	}
	if ans == inf {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

1477. 找两个和为目标值且不重叠的子数组

中等1 种解法

标签：数组、哈希表、二分查找、动态规划、滑动窗口

题目、示例与约束

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

 

示例 1：

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

示例 2：

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例 3：

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

示例 4：

输入：arr = [5,5,4,4,5], target = 3
输出：-1
解释：我们无法找到和为 3 的子数组。

示例 5：

输入：arr = [3,1,1,1,5,1,2,1], target = 3
输出：3
解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

 

提示：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8

方法一：哈希表 + 前缀和 + 动态规划 · Go 实现

思考

最直接的做法是枚举所有和为 $target$ 的子数组，再两两检查是否重叠并取长度和的最小值。 $n\le {10}^5$，子数组数量达到平方级，无法通过。

选定右段之后，左段必须完全落在它左侧的前缀里，而且我们只关心那段前缀中最短的合法子数组。这要求我们在扫描过程中随时能回答「前缀里的最短合法段」。

数组元素均为正整数，前缀和严格递增，每个前缀和只对应一个位置。因此用哈希表记下前缀和出现的下标后，就能在常数时间定位以当前位置结尾、和为 $target$ 的区间 $[j+1,i]$。

于是从左到右维护 $f[i]$：前 $i$ 个元素中和为 $target$ 的最短子数组长度。每当找到 $[j+1,i]$，就用 $f[j]$ 与当前长度相加更新答案，再令 $f[i]=min(f[i-1],i-j)$。左段始终取自当前段之前，两段自然不重叠。

我们用哈希表 $d$ 记录每个前缀和出现的位置，初始时 $d[0]=0$。

定义 $f[i]$ 表示数组前 $i$ 个元素中，和为 $target$ 的最短子数组的长度。初始时 $f[0]=\mathrm{\infty }$，答案 $ans=\mathrm{\infty }$。下标从 $1$ 开始。

遍历数组 $\mathit{\text{arr}}$。对于当前位置 $i$，先令 $f[i]=f[i-1]$，并累加得到前缀和 $s$。若 $s-\mathit{\text{target}}$ 在哈希表中，记 $j=d[s-\mathit{\text{target}}]$，则区间 $[j+1,i]$ 的和为 $target$，长度为 $i-j$。此时更新 $f[i]=min(f[i],i-j)$，并用左侧最优长度更新答案 $ans=min(ans,f[j]+i-j)$。然后将 $d[s]$ 记为 $i$。

最后，如果 $ans$ 大于数组长度，则返回 $-1$，否则返回 $ans$。

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

func minSumOfLengths(arr []int, target int) int {
	d := map[int]int{0: 0}
	const inf = 1 << 30
	s, n := 0, len(arr)
	f := make([]int, n+1)
	f[0] = inf
	ans := inf
	for i, v := range arr {
		i++
		f[i] = f[i-1]
		s += v
		if j, ok := d[s-target]; ok {
			f[i] = min(f[i], i-j)
			ans = min(ans, f[j]+i-j)
		}
		d[s] = i
	}
	if ans > n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

1478. 安排邮筒

困难1 种解法

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

题目、示例与约束

给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。

请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。

答案保证在 32 位有符号整数范围以内。

 

示例 1：

输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。

示例 2：

输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。

示例 3：

输入：houses = [7,4,6,1], k = 1
输出：8

示例 4：

输入：houses = [3,6,14,10], k = 4
输出：0

 

提示：

• n == houses.length
• 1 <= n <= 100
• 1 <= houses[i] <= 10^4
• 1 <= k <= n
• 数组 houses 中的整数互不相同。

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

思考

$n\le 100$ 个房子、 $k$ 个邮筒。一段连续房子放一个邮筒时，最优位置是中位数，代价为两端向内收缩的递推 $g[i][j]=g[i+1][j-1]+houses[j]-houses[i]$（先排序）。

$f[i][j]$ 为前 $i+1$ 栋安排 $j$ 个邮筒的最小代价，枚举上一个邮筒的分界 $p$，加上 $g[p+1][i]$。

我们定义 $f[i][j]$ 表示前 $i+1$ 栋房子，安排了 $j$ 个邮筒时，每栋房子与离它最近的邮筒之间的距离的最小总和。初始时 $f[i][j]=\mathrm{\infty }$，答案即为 $f[n-1][k]$。

我们可以枚举第 $j-1$ 个邮筒“管辖”的最后一栋房子 $p$，即 $0\le p\le i-1$，那么第 $j$ 个邮筒“管辖”的房子就是 $[p+1,..i]$，我们记 $g[i][j]$ 表示给房子 $[i,..j]$ 安排一个邮筒的最小总和，那么有状态转移方程：

$$f[i][j]=\underset{0\le p\le i-1}{min}\{f[p][j-1]+g[p+1][i]\}$$

其中 $g[i][j]$ 的计算方法如下：

$$g[i][j]=g[i+1][j-1]+\mathit{\text{houses}}[j]-\mathit{\text{houses}}[i]$$

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

func minDistance(houses []int, k int) int {
	sort.Ints(houses)
	n := len(houses)
	g := make([][]int, n)
	f := make([][]int, n)
	const inf = 1 << 30
	for i := range g {
		g[i] = make([]int, n)
		f[i] = make([]int, k+1)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			g[i][j] = g[i+1][j-1] + houses[j] - houses[i]
		}
	}
	for i := 0; i < n; i++ {
		f[i][1] = g[0][i]
		for j := 2; j <= k && j <= i+1; j++ {
			for p := 0; p < i; p++ {
				f[i][j] = min(f[i][j], f[p][j-1]+g[p+1][i])
			}
		}
	}
	return f[n-1][k]
}

力扣原题 · Doocs 题解来源

1493. 删掉一个元素以后全为 1 的最长子数组

中等3 种解法

标签：数组、动态规划、滑动窗口

题目、示例与约束

给你一个二进制数组 nums，你需要从中删除一个元素。

请你返回删除操作后，数组中仅包含 1 的 最长非空子数组 的长度。如果不存在这样的 子数组，请返回 0。

 

示例 1：

输入：nums = [1,1,0,1]
输出：3
解释：删除下标为 2 的元素后，得到 [1,1,1]，其中包含 3 个值为 1 的元素。

示例 2：

输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删除下标为 4 的元素后，得到 [0,1,1,1,1,1,0,1]，其中仅包含 1 的最长子数组为 [1,1,1,1,1]。

示例 3：

输入：nums = [1,1,1]
输出：2
解释：你必须删除一个元素。

 

提示：

• 1 <= nums.length <= 105
• nums[i] 的值为 0 或 1。

方法一：枚举 · Go 实现

思考

必须删恰好一个元素，答案是删去位置两侧连续 $1$ 的长度之和。 $n\le {10}^5$，预处理以 $i$ 结尾、以 $i$ 开头的连续 $1$ 个数，枚举删除下标取最大。

我们可以枚举每个删除的位置 $i$，然后计算左侧和右侧的连续 1 的个数，最后取最大值。

具体地，我们使用两个长度为 $n+1$ 的数组 $left$ 和 $right$，其中 $left[i]$ 表示以 $nums[i-1]$ 结尾的连续 $1$ 的个数，而 $right[i]$ 表示以 $nums[i]$ 开头的连续 $1$ 的个数。

最终答案即为 $\underset{0\le i<n}{max}\{left[i]+right[i+1]\}$。

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

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

方法二：双指针 · Go 实现

思考

方法一用了 $O(n)$ 额外数组。问题等价于最长且至多一个 $0$ 的窗口，删掉这个 $0$（或任意一个 $1$）后的长度。右端扩张、零的个数超过 $1$ 时收缩左端，窗口长度减一即答案。

题目实际上是让我们找出一个最长的子数组，该子数组中最多只包含一个 $0$，删掉该子数组中的其中一个元素后，剩余的长度即为答案。

因此，我们可以用两个指针 $j$ 和 $i$ 分别指向子数组的左右边界，初始时 $j=0$, $i=0$。另外，我们用一个变量 $cnt$ 记录子数组中 $0$ 的个数。

接下来，我们移动右指针 $i$，如果 $nums[i]=0$，则 $cnt$ 加 $1$。当 $cnt>1$ 时，我们需要移动左指针 $j$，直到 $cnt\le 1$。然后，我们更新答案，即 $ans=max(ans,i-j)$。继续移动右指针 $i$，直到 $i$ 到达数组的末尾。

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

func longestSubarray(nums []int) (ans int) {
	cnt, j := 0, 0
	for i, x := range nums {
		cnt += x ^ 1
		for ; cnt > 1; j++ {
			cnt -= nums[j] ^ 1
		}
		ans = max(ans, i-j)
	}
	return
}

方法三：双指针（优化） · Go 实现

思考

方法二在零过多时会把窗口缩短。求的是最大长度，左端每次只需右移一格与右端同步前进，窗口单调不缩，最后长度为 $n-l-1$。

方法二中，我们每次会循环移动左指针，直到 $cnt\le 1$。由于题目求的是最长子数组，意味着我们不需要缩小子数组的长度，因此，如果 $\mathit{\text{cnt}}>1$，我们只移动左指针一次，右指针也继续向右移动。这样可以保证子数组的长度不会减小。

最后，我们返回的答案即为 $n-l-1$，其中 $l$ 为左指针的位置。

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

func longestSubarray(nums []int) int {
	cnt, l := 0, 0
	for _, x := range nums {
		cnt += x ^ 1
		if cnt > 1 {
			cnt -= nums[l] ^ 1
			l++
		}
	}
	return len(nums) - l - 1
}

力扣原题 · Doocs 题解来源

1504. 统计全 1 子矩形

中等2 种解法

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

题目、示例与约束

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

 

示例 1：

输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

 

提示：

• 1 <= m, n <= 150
• mat[i][j] 仅包含 0 或 1

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

思考

统计全 $1$ 子矩阵的个数，若枚举四个边界再检查内部，时间可达 $O(m^2{n}^2\cdot mn)$。即便改为枚举右下角与左上角后用二维前缀和判断，仍是 $O(m^2{n}^2)$。矩阵边长可达 $150$，需要再降一维。

固定右下角 $(i,j)$ 后，子矩阵由向上延伸的高度决定。先对每一行预处理「以该格为右端的连续 $1$ 宽度」 $g[i][j]$，再从 $i$ 向上枚举上边界 $k$，宽度取沿途 $g[k][j]$ 的最小值，每升高一行就累加当前宽度。这样每个右下角用 $O(m)$ 完成统计，总时间 $O(m^{2}n)$。

我们可以枚举矩阵的右下角 $(i,j)$，然后向上枚举矩阵的第一行 $k$，那么每一行以 $(i,j)$ 为右下角的矩阵的宽度就是 $\underset{k\le i}{min}\mathit{\text{g}}[k][j]$，其中 $\mathit{\text{g}}[k][j]$ 表示第 $k$ 行以 $(k,j)$ 为右下角的矩阵的宽度。

因此，我们可以预处理得到二维数组 $g[i][j]$，其中 $g[i][j]$ 表示第 $i$ 行中，从第 $j$ 列向左连续的 $1$ 的个数。

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

func numSubmat(mat [][]int) (ans int) {
	m, n := len(mat), len(mat[0])
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
		for j := range g[i] {
			if mat[i][j] == 1 {
				if j == 0 {
					g[i][j] = 1
				} else {
					g[i][j] = 1 + g[i][j-1]
				}
			}
		}
	}
	for i := range g {
		for j := range g[i] {
			col := 1 << 30
			for k := i; k >= 0 && col > 0; k-- {
				col = min(col, g[k][j])
				ans += col
			}
		}
	}
	return
}

方法二：单调栈 · Go 实现

思考

方法一里，每个右下角仍要从当前行向上扫描 $O(m)$ 行，再把沿途最小宽度累加进去，总时间是 $O(m^2\times n)$。矩阵边长可达 $150$，这一层循环就是剩余的开销。

同一列上，一旦出现更窄的宽度，它上方每一行的贡献都会被这个宽度卡住，没有必要从当前行再逐行重扫。对每一列维护宽度严格递增的单调栈，栈顶就是上方最近的更窄位置：当前行到栈顶之间的最小宽度就是本行的 $g[i][j]$，栈顶及其上方的答案已经算好，直接沿用。每个格子至多入栈一次、出栈一次，向上的扫描就被摊成 $O(1)$。

我们仍先预处理二维数组 $g$，其中 $g[i][j]$ 表示第 $i$ 行从第 $j$ 列向左连续 $1$ 的个数。

然后按列统计。对于第 $j$ 列，从上到下扫描每一行 $i$，并用单调栈保存三元组 $(w,r,c)$：宽度 $w$、所在行 $r$，以及以 $(r,j)$ 为右下角的全 $1$ 子矩阵个数 $c$。栈中的宽度保持严格递增。

处理 $g[i][j]$ 时，弹出所有宽度大于等于当前值的栈顶。若栈为空，则从第 $0$ 行到第 $i$ 行的最小宽度都是 $g[i][j]$，以 $(i,j)$ 为右下角的子矩阵个数为 $g[i][j]\times (i+1)$。否则设栈顶为 $(w,r,c)$，第 $r$ 行及以上的贡献已经记在 $c$ 中，第 $r+1$ 行到第 $i$ 行的最小宽度都是 $g[i][j]$，因此个数为 $c+g[i][j]\times (i-r)$。将该结果累加到答案，并把当前宽度、行号与这个个数压入栈中。

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

func numSubmat(mat [][]int) (ans int) {
	m, n := len(mat), len(mat[0])
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
		for j := range g[i] {
			if mat[i][j] == 1 {
				if j == 0 {
					g[i][j] = 1
				} else {
					g[i][j] = 1 + g[i][j-1]
				}
			}
		}
	}
	for j := 0; j < n; j++ {
		stk := [][3]int{}
		for i := 0; i < m; i++ {
			cur := g[i][j]
			for len(stk) > 0 && stk[len(stk)-1][0] >= cur {
				stk = stk[:len(stk)-1]
			}
			cnt := cur * (i + 1)
			if len(stk) > 0 {
				cnt = stk[len(stk)-1][2] + cur*(i-stk[len(stk)-1][1])
			}
			ans += cnt
			stk = append(stk, [3]int{cur, i, cnt})
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1510. 石子游戏 IV

困难3 种解法

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

题目、示例与约束

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。

 

示例 1：

输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。

示例 2：

输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。

示例 3：

输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。

示例 4：

输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。

示例 5：

输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。

 

提示：

• 1 <= n <= 10^5

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

思考

双方轮流从 $n$ 个石子中拿走一个平方数，取走最后一枚者胜。 $n\le {10}^5$，若对每个局面展开整棵博弈树，同一剩余量会被反复计算。

局面只由剩余石子数决定：若存在一种取法使对手面对必败态，则当前必胜。记忆化搜索 $dfs(i)$ 表示剩 $i$ 枚时先手是否必胜，枚举 $j^2\le i$ 并查询 $dfs(i-j^2)$ 即可，每个状态至多处理 $O(\sqrt{i})$ 次转移。

我们设计一个函数 $dfs(i)$，表示当前石子堆中有 $i$ 个石子时，当前玩家是否能赢得比赛。如果当前玩家能赢得比赛，则返回 $true$，否则返回 $false$。那么答案即为 $dfs(n)$。

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

• 如果 $i\le 0$，说明当前玩家无法进行任何操作，因此当前玩家输掉比赛，返回 $false$；
• 否则，枚举当前玩家可以拿走的石子数量 $j$，其中 $j$ 为平方数，如果当前玩家拿走 $j$ 个石子后，另一个玩家无法赢得比赛，则当前玩家赢得比赛，返回 $true$。如果枚举完所有的 $j$，都无法满足上述条件，则当前玩家输掉比赛，返回 $false$。

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

时间复杂度 $O(n\times \sqrt{n})$，空间复杂度 $O(n)$。其中 $n$ 为石子堆中石子的数量。

func winnerSquareGame(n int) bool {
	f := make([]int8, n+1)

	var dfs func(int) bool
	dfs = func(i int) bool {
		if i <= 0 {
			return false
		}
		if f[i] != 0 {
			return f[i] == 1
		}
		k := int(math.Sqrt(float64(i)))
		for j := 1; j <= k; j++ {
			if !dfs(i - j*j) {
				f[i] = 1
				return true
			}
		}
		f[i] = -1
		return false
	}

	return dfs(n)
}

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

思考

方法一已经按剩余石子从少到多填好同一张胜负表。下面的 $f[i]$ 与那张表是同一定义。

方法一已经按剩余石子从少到多填好同一张表。定义数组 $f$，其中 $f[i]$ 表示当前石子堆中有 $i$ 个石子时，当前玩家是否能赢得比赛。如果当前玩家能赢得比赛，则 $f[i]$ 为 $true$，否则为 $false$。那么答案即为 $f[n]$。

我们在 $[1,..n]$ 的范围内枚举 $i$，并在 $[1,..i]$ 的范围内枚举 $j$，其中 $j$ 为平方数，如果当前玩家拿走 $j$ 个石子后，另一个玩家无法赢得比赛，则当前玩家赢得比赛，即 $f[i]=true$。如果枚举完所有的 $j$，都无法满足上述条件，则当前玩家输掉比赛，即 $f[i]=false$。因此我们可以得到状态转移方程：

$$f[i]=\{\begin{array}{ll}true,& \mathit{\text{if }}\mathrm{\exists }j\in [1,..i],j^2\le i\mathit{\text{ and }}f[i-j^2]=false\\ false,& \mathit{\text{otherwise}}\end{array}$$

最后，我们返回 $f[n]$ 即可。

时间复杂度 $O(n\times \sqrt{n})$，空间复杂度 $O(n)$。其中 $n$ 为石子堆中石子的数量。

func winnerSquareGame(n int) bool {
	f := make([]bool, n+1)
	for i := 1; i <= n; i++ {
		for j := 1; j <= i/j; j++ {
			if !f[i-j*j] {
				f[i] = true
				break
			}
		}
	}
	return f[n]
}

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

思考

展开整棵博弈树是指数级的。石子数可以到 ${10}^5$，而第一次总是先拿走 $1$ 枚，递归深度就是 $n$。一个局面是否必胜只由剩余石子数决定，并且只依赖更少的石子。于是令 $f[i]$ 表示剩 $i$ 枚时当前玩家是否必胜， $f[0]$ 为必败，按 $i$ 从小到大枚举平方数 $j^2$，只要存在后继 $f[i-j^2]$ 为必败，就把 $f[i]$ 标成必胜。

令 $f[i]$ 表示石子堆中有 $i$ 个石子时，当前玩家是否能赢得比赛。 $f[0]$ 为 $false$，因为无法再取。从 $i=1$ 到 $n$，枚举平方数 $j^2\le i$。若 $f[i-j^2]$ 为 $false$，对手拿到这个局面会输，于是 $f[i]$ 为 $true$，可以停止枚举。若所有平方取法都留给对手必胜局面，则 $f[i]$ 保持 $false$。答案为 $f[n]$。

时间复杂度 $O(n\times \sqrt{n})$，空间复杂度 $O(n)$。其中 $n$ 为石子堆中石子的数量。

func winnerSquareGame(n int) bool {
	f := make([]bool, n+1)
	for i := 1; i <= n; i++ {
		for j := 1; j <= i/j; j++ {
			if !f[i-j*j] {
				f[i] = true
				break
			}
		}
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

1524. 和为奇数的子数组数目

中等1 种解法

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

题目、示例与约束

给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。

由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。

 

示例 1：

输入：arr = [1,3,5]
输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。

示例 2 ：

输入：arr = [2,4,6]
输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。

示例 3：

输入：arr = [1,2,3,4,5,6,7]
输出：16

示例 4：

输入：arr = [100,100,99,99]
输出：4

示例 5：

输入：arr = [7]
输出：1

 

提示：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 100

方法一：前缀和 + 计数器 · Go 实现

思考

统计子数组和为奇数的个数。子数组有 $O(n^2)$ 个， $n\le {10}^5$，直接求和不可行。子数组和的奇偶等于两端前缀和之差的奇偶。

前缀和为奇当且仅当此前偶数前缀的个数可与之配对（奇减偶为奇），偶前缀则与已有奇前缀配对。扫描时维护奇、偶前缀计数，每走一步按当前前缀奇偶累加配对并更新计数，最后对 ${10}^9+7$ 取模。

我们定义一个长度为 $2$ 的数组 $\mathit{\text{cnt}}$ 作为计数器，其中 $\mathit{\text{cnt}}[0]$ 和 $\mathit{\text{cnt}}[1]$ 分别表示前缀和为偶数和奇数的子数组的个数。初始时 $\mathit{\text{cnt}}[0]=1$，而 $\mathit{\text{cnt}}[1]=0$。

接下来，我们维护当前的前缀和 $s$，初始时 $s=0$。

遍历数组 $\mathit{\text{arr}}$，对于遍历到的每个元素 $x$，我们将 $s$ 的值加上 $x$，然后根据 $s$ 的奇偶性，将 $\mathit{\text{cnt}}[s\mathrm{mod}2\oplus 1]$ 的值累加到答案中，然后我们将 $\mathit{\text{cnt}}[s\mathrm{mod}2]$ 的值加 $1$。

遍历结束后，我们即可得到答案。注意答案的取模运算。

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

func numOfSubarrays(arr []int) (ans int) {
	const mod int = 1e9 + 7
	cnt := [2]int{1, 0}
	s := 0
	for _, x := range arr {
		s += x
		ans = (ans + cnt[s&1^1]) % mod
		cnt[s&1]++
	}
	return
}

力扣原题 · Doocs 题解来源

1525. 字符串的好分割数目

中等1 种解法

标签：位运算、哈希表、字符串、动态规划、前缀和

题目、示例与约束

给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 s 中好分割的数目。

 

示例 1：

输入：s = "aacaba"
输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。

示例 2：

输入：s = "abcd"
输出：1
解释：好分割为将字符串分割成 ("ab", "cd") 。

示例 3：

输入：s = "aaaaa"
输出：4
解释：所有分割都是好分割。

示例 4：

输入：s = "acbadbaada"
输出：2

 

提示：

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

方法一：哈希表 · Go 实现

思考

统计使左右两段不同字符种数相等的拆分位置。 $n\le {10}^5$，若对每个切点各扫一遍左右，总时间平方级。

右侧字符种数可由全局计数得到，左侧种数随指针单调增加。从左到右移动切点：把当前字符记入左侧集合，并从右侧计数中减一，计数归零则从右侧表删除。两侧键的个数相等时即可计入答案，一次遍历完成。

我们维护两个哈希表，分别记录左侧出现的字符、右侧的字符以及出现的次数。初始时，左侧的哈希表为空，右侧的哈希表为字符串 $s$ 中所有字符出现的次数。

接下来，我们从左到右遍历字符串 $s$，对于遍历到的字符 $c$，我们将其加入左侧的哈希表，同时将其在右侧的哈希表中的出现次数减一。如果减一后，右侧哈希表中的出现次数为 0，则将其从右侧哈希表中移除。然后，我们判断左侧哈希表中的键值对数量是否与右侧哈希表中的键值对数量相等，如果相等，则将答案加一。

最终，我们返回答案即可。

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

func numSplits(s string) (ans int) {
	cnt := map[rune]int{}
	for _, c := range s {
		cnt[c]++
	}
	vis := map[rune]bool{}
	for _, c := range s {
		vis[c] = true
		cnt[c]--
		if cnt[c] == 0 {
			delete(cnt, c)
		}
		if len(vis) == len(cnt) {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1526. 形成目标数组的子数组最少增加次数

困难1 种解法

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

题目、示例与约束

给你一个整数数组 target 和一个数组 initial ，initial 数组与 target  数组有同样的大小，且一开始全部为 0 。

一次操作中，你可以从 initial 数组中选择 任何 子数组，并将每个值加 1。

返回从 initial 数组构造 target 数组的最少操作次数。

答案保证在 32 位整数以内。

 

示例 1：

输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下标为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。

示例 2：

输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。

示例 3：

输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

示例 4：

输入：target = [1,1,1,1]
输出：1

 

提示：

• 1 <= target.length <= 105
• 1 <= target[i] <= 105
• 输入保证答案在 32 位整数范围内。

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

思考

每次可将一段连续下标同时加一，要把全零数组变成 $target$。 $n$ 与 $target[i]$ 均可达 ${10}^5$，不能按高度一层层模拟。

一次覆盖 $[i,j]$ 的操作，对前缀 $target[0..i]$ 而言，等价于在更短前缀的最优方案上，仅当 $target[i]$ 高于左侧时才多出高度差这么多次。因此 $f[i]=f[i-1]+max(0,target[i]-target[i-1])$，而 $f[0]=target[0]$。递推只用到前一项，压缩成一次相邻差扫描即可。

我们定义 $f[i]$ 表示得到 $target[0,..i]$ 的最少操作次数，初始时 $f[0]=target[0]$。

对于 $target[i]$，如果 $target[i]\le target[i-1]$，则 $f[i]=f[i-1]$；否则 $f[i]=f[i-1]+target[i]-target[i-1]$。

最终答案即为 $f[n-1]$。

我们注意到 $f[i]$ 只与 $f[i-1]$ 有关，因此可以只用一个变量来维护操作次数。

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

相似题目：

• 3229. 使数组等于目标数组所需的最少操作次数

func minNumberOperations(target []int) int {
	f := target[0]
	for i, x := range target[1:] {
		if x > target[i] {
			f += x - target[i]
		}
	}
	return f
}

力扣原题 · Doocs 题解来源

1531. 压缩字符串 II

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。例如，用此方法压缩字符串 "aabccc" ，将 "aa" 替换为 "a2" ，"ccc" 替换为` "c3" 。因此压缩后的字符串变为 "a2bc3" 。

注意，本问题中，压缩时没有在单个字符后附加计数 '1' 。

给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符，以使 s 的行程长度编码长度最小。

请你返回删除最多 k 个字符后，s 行程长度编码的最小长度 。

 

示例 1：

输入：s = "aaabcccd", k = 2
输出：4
解释：在不删除任何内容的情况下，压缩后的字符串是 "a3bc3d" ，长度为 6 。最优的方案是删除 'b' 和 'd'，这样一来，压缩后的字符串为 "a3c3" ，长度是 4 。

示例 2：

输入：s = "aabbaa", k = 2
输出：2
解释：如果删去两个 'b' 字符，那么压缩后的字符串是长度为 2 的 "a4" 。

示例 3：

输入：s = "aaaaaaaaaaa", k = 0
输出：3
解释：由于 k 等于 0 ，不能删去任何字符。压缩后的字符串是 "a11" ，长度为 3 。

 

提示：

• 1 <= s.length <= 100
• 0 <= k <= s.length
• s 仅包含小写英文字母

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

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

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

思路：令 dp[i][k] 表示前 i 个字符恰好删除 k 个后的最短编码长度。处理当前字符时，一种选择是删除它；另一种选择是保留它并向前枚举最后一段，删除其中所有不同字符，把相同字符合成一个连续段。用预先准备的 w 表查询该段的编码长度，与前缀状态合并取最小值。

复杂度：设字符串长度为 n，删除额度为 K。共有 O(n(K+1)) 个状态，每个状态最多向前扫描 n 个字符，时间为 O(n²(K+1))，辅助空间为 O(n(K+1))。

var w = [...]int{1: 1, 100: 4}

func init() {
	for i := 2; i < 10; i++ {
		w[i] = 2
	}
	for i := 10; i < 100; i++ {
		w[i] = 3
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// github.com/EndlessCheng/codeforces-go
func getLengthOfOptimalCompression(s string, K int) (ans int) {
	n := len(s)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, K+1)
		for j := range dp[i] {
			dp[i][j] = 1e9
		}
	}
	dp[0][0] = 0
	for i := range s {
		b := s[i]
		for k := 0; k <= K; k++ {
			if k > 0 { // 决策：删除当前字母
				dp[i+1][k] = min(dp[i+1][k], dp[i][k-1])
			}
			diff, same := 0, 0
			for j := i; j >= 0; j-- {
				if s[j] != b { // 决策：不删除当前字母，从后往前枚举，把和当前字母不同的全删掉
					if diff++; diff > k {
						break
					}
				} else {
					same++
				}
				dp[i+1][k] = min(dp[i+1][k], dp[j][k-diff]+w[same])
			}
		}
	}
	return dp[n][K]
}

力扣原题 · Doocs 题解来源

1537. 最大得分

困难1 种解法

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

题目、示例与约束

你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。

一条 合法路径 定义如下：

• 选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
• 从左到右遍历当前数组。
• 如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。

得分 定义为合法路径中不同数字的和。

请你返回 所有可能 合法路径 中的最大得分。由于答案可能很大，请你将它对 10^9 + 7 取余后返回。

 

示例 1：

输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

示例 2：

输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出：109
解释：最大得分由路径 [1,3,5,100] 得到。

示例 3：

输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径[6,7,8,9,10]得到。

 

提示：

• 1 <= nums1.length, nums2.length <= 105
• 1 <= nums1[i], nums2[i] <= 107
• nums1 和 nums2 都是严格递增的数组。

方法一 · Go 实现

思考

两条递增数组可在相同数值处切换，得分是路径上数值之和（公共值只计一次）。 $n\le {10}^5$，枚举所有切换方案不可行。

公共值把路径切成若干段，两段之间只能走完其中一条。用双指针同步推进：较小的一侧累加到自己的路径和；相等时两边都加上该值并取至此较大的路径和作为新的共同起点。扫完后取两条路径和的较大者。

func maxSum(nums1 []int, nums2 []int) int {
	const mod int = 1e9 + 7
	m, n := len(nums1), len(nums2)
	i, j := 0, 0
	f, g := 0, 0
	for i < m || j < n {
		if i == m {
			g += nums2[j]
			j++
		} else if j == n {
			f += nums1[i]
			i++
		} else if nums1[i] < nums2[j] {
			f += nums1[i]
			i++
		} else if nums1[i] > nums2[j] {
			g += nums2[j]
			j++
		} else {
			f = max(f, g) + nums1[i]
			g = f
			i++
			j++
		}
	}
	return max(f, g) % mod
}

力扣原题 · Doocs 题解来源

1547. 切棍子的最小成本

困难2 种解法

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

题目、示例与约束

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

 

示例 1：

输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：

第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。

示例 2：

输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。

 

提示：

• 2 <= n <= 10^6
• 1 <= cuts.length <= min(n - 1, 100)
• 1 <= cuts[i] <= n - 1
• cuts 数组中的所有整数都 互不相同

方法一：动态规划（区间 DP） · Go 实现

思考

在长度为 $n$ 的木棍上按给定切点切割，每次代价等于当前这段的长度，求最小总代价。 $n$ 可达 ${10}^6$，但切点至多 $100$，应在切点上 DP 而不是在木棍坐标上。

把 $0$ 与 $n$ 并入切点并排序。 $f[i][j]$ 表示切完开区间 $(cuts[i],cuts[j])$ 内全部点的最小代价，最后一刀落在 $cuts[k]$ 时转移为 $f[i][k]+f[k][j]+cuts[j]-cuts[i]$。按区间长度递增填表，保证子区间先算完。

我们可以往切割点数组 $\mathit{\text{cuts}}$ 中添加两个元素，分别是 $0$ 和 $n$，表示棍子的两端。然后我们对 $\mathit{\text{cuts}}$ 数组进行排序，这样我们就可以将整个棍子切割为若干个区间，每个区间都有两个切割点。不妨设此时 $\mathit{\text{cuts}}$ 数组的长度为 $m$。

接下来，我们定义 $\mathit{\text{f}}[i][j]$ 表示切割区间 $[\mathit{\text{cuts}}[i],..\mathit{\text{cuts}}[j]]$ 的最小成本。

如果一个区间只有两个切割点，也就是说，我们无需切割这个区间，那么 $\mathit{\text{f}}[i][j]=0$。

否则，我们枚举区间的长度 $l$，其中 $l$ 等于切割点的数量减去 $1$。然后我们枚举区间的左端点 $i$，右端点 $j$ 可以由 $i+l$ 得到。对于每个区间，我们枚举它的切割点 $k$，其中 $i<k<j$，那么我们可以将区间 $[i,j]$ 切割为 $[i,k]$ 和 $[k,j]$，此时的成本为 $\mathit{\text{f}}[i][k]+\mathit{\text{f}}[k][j]+\mathit{\text{cuts}}[j]-\mathit{\text{cuts}}[i]$，我们取所有可能的 $k$ 中的最小值，即为 $\mathit{\text{f}}[i][j]$ 的值。

最后，我们返回 $\mathit{\text{f}}[0][m-1]$。

时间复杂度 $O(m^3)$，空间复杂度 $O(m^2)$。其中 $m$ 为修改后的 $\mathit{\text{cuts}}$ 数组的长度。

func minCost(n int, cuts []int) int {
	cuts = append(cuts, []int{0, n}...)
	sort.Ints(cuts)
	m := len(cuts)
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, m)
	}
	for l := 2; l < m; l++ {
		for i := 0; i+l < m; i++ {
			j := i + l
			f[i][j] = 1 << 30
			for k := i + 1; k < j; k++ {
				f[i][j] = min(f[i][j], f[i][k]+f[k][j]+cuts[j]-cuts[i])
			}
		}
	}
	return f[0][m-1]
}

方法二：动态规划（另一种枚举方式） · Go 实现

思考

方法一按长度分层枚举，只是为了满足「短区间先于长区间」。同一转移也可以先逆序枚举左端 $i$、再顺序枚举右端 $j$，同样保证 $i<k<j$ 的子状态已算出。渐近复杂度不变，仅枚举次序不同。

我们也可以从大到小枚举 $i$，从小到大枚举 $j$，这样可以保证在计算 $f[i][j]$ 时，状态 $f[i][k]$ 和 $f[k][j]$ 都已经被计算过了，其中 $i<k<j$。

时间复杂度 $O(m^3)$，空间复杂度 $O(m^2)$。其中 $m$ 为修改后的 $\mathit{\text{cuts}}$ 数组的长度。

func minCost(n int, cuts []int) int {
	cuts = append(cuts, []int{0, n}...)
	sort.Ints(cuts)
	m := len(cuts)
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, m)
	}
	for i := m - 1; i >= 0; i-- {
		for j := i + 2; j < m; j++ {
			f[i][j] = 1 << 30
			for k := i + 1; k < j; k++ {
				f[i][j] = min(f[i][j], f[i][k]+f[k][j]+cuts[j]-cuts[i])
			}
		}
	}
	return f[0][m-1]
}

力扣原题 · Doocs 题解来源

1553. 吃掉 N 个橘子的最少天数

困难1 种解法

标签：记忆化、动态规划

题目、示例与约束

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

• 吃掉一个橘子。
• 如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
• 如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。

每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 n 个橘子的最少天数。

 

示例 1：

输入：n = 10
输出：4
解释：你总共有 10 个橘子。
第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。

示例 2：

输入：n = 6
输出：3
解释：你总共有 6 个橘子。
第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。

示例 3：

输入：n = 1
输出：1

示例 4：

输入：n = 56
输出：6

 

提示：

• 1 <= n <= 2*10^9

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

思考

每天可吃 $1$ 个，或在能整除时吃掉一半或三分之二。 $n$ 达 $2\times {10}^9$，按剩余量递推的数组放不下，一路减一更不可行。

最优策略总是先吃掉 $nmod2$ 或 $nmod3$ 个，以便立刻除以 $2$ 或 $3$。因此 $dfs(n)=1+min(nmod2+dfs(\lfloor n/2\rfloor ),nmod3+dfs(\lfloor n/3\rfloor ))$。除法使状态沿 $n$ 迅速下降，记忆化后规模约 $O({\log }^{2}n)$。

根据题目描述，对于每个 $n$，我们可以选择三种方式之一：

1. 将 $n$ 减少 $1$；
2. 如果 $n$ 能被 $2$ 整除，将 $n$ 的值除以 $2$；
3. 如果 $n$ 能被 $3$ 整除，将 $n$ 的值除以 $3$。

因此，问题等价于求解通过上述三种方式，将 $n$ 减少到 $0$ 的最少天数。

我们设计一个函数 $dfs(n)$，表示将 $n$ 减少到 $0$ 的最少天数。函数 $dfs(n)$ 的执行过程如下：

1. 如果 $n<2$，返回 $n$；
2. 否则，我们可以先通过 $nmod2$ 次操作 $1$，将 $n$ 减少到 $2$ 的倍数，然后执行操作 $2$，将 $n$ 减少到 $n/2$；我们也可以先通过 $nmod3$ 次操作 $1$，将 $n$ 减少到 $3$ 的倍数，然后执行操作 $3$，将 $n$ 减少到 $n/3$。我们选择上述两种方式中最少的一种，即 $1+min(nmod2+dfs(n/2),nmod3+dfs(n/3))$。

为了避免重复计算，我们使用记忆化搜索的方法，将已经计算过的 $dfs(n)$ 的值存储在哈希表中。

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

func minDays(n int) int {
	f := map[int]int{0: 0, 1: 1}
	var dfs func(int) int
	dfs = func(n int) int {
		if v, ok := f[n]; ok {
			return v
		}
		res := 1 + min(n%2+dfs(n/2), n%3+dfs(n/3))
		f[n] = res
		return res
	}
	return dfs(n)
}

力扣原题 · Doocs 题解来源

1563. 石子游戏 V

困难1 种解法

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

题目、示例与约束

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

 

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

 

提示：

• 1 <= stoneValue.length <= 500
• 1 <= stoneValue[i] <= 106

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

思考

每次把一段石子分成左右两部分，得分取较小一侧的和，并只在较小（或相等时任选）一侧继续。区间个数 $O(n^2)$，再枚举切点是 $O(n^3)$，石子数通常不超过 $500$，可以接受，但朴素搜索会重复计算同一区间。

令 $dfs(i,j)$ 为区间 $[i,j]$ 上 Alice 的最大得分，用前缀和在 $O(1)$ 内得到左右两段之和。左段更小则只递归左侧，并在 $ans\ge 2\times l$ 时跳过（再搜也不会更优）；右段更小且 $ans\ge 2\times r$ 时可直接结束后续切点。记忆化避免重复区间。

我们先预处理出前缀和数组 $\mathit{\text{s}}$，其中 $\mathit{\text{s}}[i]$ 表示数组 $\mathit{\text{stoneValue}}$ 前 $i$ 个元素的和。

接下来，我们设计一个函数 $\mathit{\text{dfs}}(i,j)$，表示数组 $\mathit{\text{stoneValue}}$ 中下标范围 $[i,j]$ 内的石子，Alice 能够获得的最大分数。那么答案就是 $\mathit{\text{dfs}}(0,n-1)$。

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

• 如果 $i\ge j$，说明只剩下一块石子，Alice 无法进行分割，因此返回 $0$。
• 否则，我们枚举分割点 $k$，即 $i\le k<j$，将数组 $\mathit{\text{stoneValue}}$ 中下标范围 $[i,j]$ 内的石子分割为 $[i,k]$ 和 $[k+1,j]$ 两部分，计算出 $a$ 和 $b$，分别表示两部分的石子总和。然后我们分别计算 $\mathit{\text{dfs}}(i,k)$ 和 $\mathit{\text{dfs}}(k+1,j)$，并更新答案。

注意，如果满足 $a<b$ 并且 $\mathit{\text{ans}}\ge a\times 2$，那么这一次枚举可以跳过；如果满足 $a>b$ 并且 $\mathit{\text{ans}}\ge b\times 2$，那么后续的枚举都可以跳过，直接退出循环。

最后，我们返回答案即可。

为了避免重复计算，我们可以使用记忆化搜索，同时使用剪枝优化枚举的效率。

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

func stoneGameV(stoneValue []int) int {
	n := len(stoneValue)
	s := make([]int, n+1)
	for i, x := range stoneValue {
		s[i+1] = s[i] + x
	}
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i >= j {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans, l, r := 0, 0, s[j+1]-s[i]
		for k := i; k < j; k++ {
			l += stoneValue[k]
			r -= stoneValue[k]
			if l < r {
				if ans > l*2 {
					continue
				}
				ans = max(ans, dfs(i, k)+l)
			} else if l > r {
				if ans > r*2 {
					break
				}
				ans = max(ans, dfs(k+1, j)+r)
			} else {
				ans = max(ans, max(dfs(i, k), dfs(k+1, j))+l)
			}
		}
		f[i][j] = ans
		return ans
	}
	return dfs(0, n-1)
}

力扣原题 · Doocs 题解来源

1567. 乘积为正数的最长子数组长度

中等2 种解法

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

题目、示例与约束

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

 

示例  1：

输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

示例 2：

输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

示例 3：

输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。

 

提示：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

 

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

思考

求乘积为正的最长子数组。 $n\le {10}^5$，枚举两端再求积会溢出且超时。零把数组切开，负号只改变符号，适合按结尾位置记录正、负两种长度。

令 $f[i]$、 $g[i]$ 分别为以 $i$ 结尾的最长正积、负积长度。正数延续原符号；负数把正负对调；零则两长度皆断。答案取所有 $f[i]$ 的最大者。

我们定义两个长度为 $n$ 的数组 $f$ 和 $g$，其中 $f[i]$ 表示以 $\mathit{\text{nums}}[i]$ 结尾的乘积为正数的最长子数组的长度，而 $g[i]$ 表示以 $\mathit{\text{nums}}[i]$ 结尾的乘积为负数的最长子数组的长度。

初始时，如果 $\mathit{\text{nums}}[0]>0$，则 $f[0]=1$，否则 $f[0]=0$；如果 $\mathit{\text{nums}}[0]<0$，则 $g[0]=1$，否则 $g[0]=0$。我们初始化答案 $ans=f[0]$。

接下来，我们从 $i=1$ 开始遍历数组 $\mathit{\text{nums}}$，对于每个 $i$，我们有以下几种情况：

• 如果 $\mathit{\text{nums}}[i]>0$，那么 $f[i]$ 可以由 $f[i-1]$ 转移而来，即 $f[i]=f[i-1]+1$，而 $g[i]$ 的值取决于 $g[i-1]$ 是否为 $0$，如果 $g[i-1]=0$，则 $g[i]=0$，否则 $g[i]=g[i-1]+1$；
• 如果 $\mathit{\text{nums}}[i]<0$，那么 $f[i]$ 的值取决于 $g[i-1]$ 是否为 $0$，如果 $g[i-1]=0$，则 $f[i]=0$，否则 $f[i]=g[i-1]+1$，而 $g[i]$ 可以由 $f[i-1]$ 转移而来，即 $g[i]=f[i-1]+1$。
• 然后，我们更新答案 $ans=max(ans,f[i])$。

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

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

func getMaxLen(nums []int) int {
	n := len(nums)
	f := make([]int, n)
	g := make([]int, n)
	if nums[0] > 0 {
		f[0] = 1
	}
	if nums[0] < 0 {
		g[0] = 1
	}
	ans := f[0]

	for i := 1; i < n; i++ {
		if nums[i] > 0 {
			f[i] = f[i-1] + 1
			if g[i-1] > 0 {
				g[i] = g[i-1] + 1
			} else {
				g[i] = 0
			}
		} else if nums[i] < 0 {
			if g[i-1] > 0 {
				f[i] = g[i-1] + 1
			} else {
				f[i] = 0
			}
			g[i] = f[i-1] + 1
		}
		ans = max(ans, f[i])
	}
	return ans
}

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

思考

每个状态只依赖前一位置的 $f,g$，数组可以压成两个变量。时间仍是线性，额外空间降为常数。

我们发现，对于每个 $i$， $f[i]$ 和 $g[i]$ 的值只与 $f[i-1]$ 和 $g[i-1]$ 有关，因此我们可以使用两个变量 $f$ 和 $g$ 分别记录 $f[i-1]$ 和 $g[i-1]$ 的值，从而将空间复杂度优化至 $O(1)$。

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

func getMaxLen(nums []int) int {
	n := len(nums)
	var f, g int
	if nums[0] > 0 {
		f = 1
	} else if nums[0] < 0 {
		g = 1
	}
	ans := f
	for i := 1; i < n; i++ {
		ff, gg := 0, 0
		if nums[i] > 0 {
			ff = f + 1
			gg = 0
			if g > 0 {
				gg = g + 1
			}
		} else if nums[i] < 0 {
			ff = 0
			if g > 0 {
				ff = g + 1
			}
			gg = f + 1
		}
		f, g = ff, gg
		ans = max(ans, f)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1575. 统计所有可行路径

困难2 种解法

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

题目、示例与约束

给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量

每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足  j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。

请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。

请你返回从 start 到 finish 所有可能路径的数目。

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

 

示例 1：

输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

示例 2：

输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
输出：5
解释：以下为所有可能的路径：
1 -> 0，使用汽油量为 fuel = 1
1 -> 2 -> 0，使用汽油量为 fuel = 5
1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5

示例 3：

输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
输出：0
解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。

 

提示：

• 2 <= locations.length <= 100
• 1 <= locations[i] <= 109
• 所有 locations 中的整数 互不相同 。
• 0 <= start, finish < locations.length
• 1 <= fuel <= 200

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

思考

从 $start$ 出发、油量不超过 $fuel$，统计到达 $finish$ 的路径数，中途可停留。城市数与油量都不大，但路径可反复经过同一城，不能按简单路径枚举。

状态只需当前城市 $i$ 与剩余油量 $k$。若 $k$ 已不够直达终点则无解；否则当前若已在终点先计入一条「到此为止」的路径，再枚举下一城 $j$ 并递归 $k-|locations[i]-locations[j]|$。记忆化后状态数为 $O(n\cdot fuel)$。

我们设计一个函数 $dfs(i,k)$，表示从城市 $i$ 出发，剩余汽油量为 $k$ 时，到达目的地 $finish$ 的路径数。那么答案就是 $dfs(start,fuel)$。

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

• 如果 $k<|locations[i]-locations[finish]|$，那么返回 $0$。
• 如果 $i=finish$，那么答案路径数初始时为 $1$，否则为 $0$。
• 然后，我们遍历所有城市 $j$，如果 $j\ne i$，那么我们可以从城市 $i$ 移动到城市 $j$，此时剩余汽油量为 $k-|locations[i]-locations[j]|$，那么我们可以将答案路径数加上 $dfs(j,k-|locations[i]-locations[j]|)$。
• 最后，我们返回答案路径数。

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

时间复杂度 $O(n^2\times m)$，空间复杂度 $O(n\times m)$。其中 $n$ 和 $m$ 分别是数组 $locations$ 和 $fuel$ 的大小。

func countRoutes(locations []int, start int, finish int, fuel int) int {
	n := len(locations)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, fuel+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	const mod = 1e9 + 7
	var dfs func(int, int) int
	dfs = func(i, k int) (ans int) {
		if k < abs(locations[i]-locations[finish]) {
			return 0
		}
		if f[i][k] != -1 {
			return f[i][k]
		}
		if i == finish {
			ans = 1
		}
		for j, x := range locations {
			if j != i {
				ans = (ans + dfs(j, k-abs(locations[i]-x))) % mod
			}
		}
		f[i][k] = ans
		return
	}
	return dfs(start, fuel)
}

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

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

思考

记忆化按需展开，递归深度受油量限制。同一转移可按剩余油量从小到大填表： $f[i][k]$ 表示从 $i$ 带油 $k$ 走到终点的方案，终点列预置为 $1$，再枚举边权不超过 $k$ 的转移。实现去掉递归，渐近复杂度相同。

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

我们定义 $f[i][k]$ 表示从城市 $i$ 出发，剩余汽油量为 $k$ 时，到达目的地 $finish$ 的路径数。那么答案就是 $f[start][fuel]$。初始时 $f[finish][k]=1$，其余均为 $0$。

接下来，我们从小到大枚举剩余汽油量 $k$，然后枚举所有的城市 $i$，对于每个城市 $i$，我们枚举所有的城市 $j$，如果 $j\ne i$，并且 $|locations[i]-locations[j]|\le k$，那么我们可以从城市 $i$ 移动到城市 $j$，此时剩余汽油量为 $k-|locations[i]-locations[j]|$，那么我们可以将答案路径数加上 $f[j][k-|locations[i]-locations[j]|]$。

最后，我们返回答案路径数 $f[start][fuel]$ 即可。

时间复杂度 $O(n^2\times m)$，空间复杂度 $O(n\times m)$。其中 $n$ 和 $m$ 分别是数组 $locations$ 和 $fuel$ 的大小。

func countRoutes(locations []int, start int, finish int, fuel int) int {
	n := len(locations)
	const mod = 1e9 + 7
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, fuel+1)
	}
	for k := 0; k <= fuel; k++ {
		f[finish][k] = 1
	}
	for k := 0; k <= fuel; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if j != i && abs(locations[i]-locations[j]) <= k {
					f[i][k] = (f[i][k] + f[j][k-abs(locations[i]-locations[j])]) % mod
				}
			}
		}
	}
	return f[start][fuel]
}

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

力扣原题 · Doocs 题解来源

1578. 使绳子变成彩色的最短时间

中等1 种解法

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

题目、示例与约束

Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。

Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个 下标从 0 开始 的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。

返回 Bob 使绳子变成 彩色 需要的 最少时间 。

 

示例 1：

输入：colors = "abaac", neededTime = [1,2,3,4,5]
输出：3
解释：在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。
Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。

示例 2：

输入：colors = "abc", neededTime = [1,2,3]
输出：0
解释：绳子已经是彩色的，Bob 不需要从绳子上移除任何气球。

示例 3：

输入：colors = "aabaa", neededTime = [1,2,3,4,1]
输出：2
解释：Bob 会移除下标 0 和下标 4 处的气球。这两个气球各需要 1 秒来移除。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 1 + 1 = 2 。

 

提示：

• n == colors.length == neededTime.length
• 1 <= n <= 105
• 1 <= neededTime[i] <= 104
• colors 仅由小写英文字母组成

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

思考

相邻同色气球必须删到只剩一个，代价为被删气球的时间。 $n\le {10}^5$，不同颜色互不影响，只需处理每一段连续同色。

双指针划出一段同色区间，累加时间并记下最大值。留下最贵的那一个、删掉其余，代价为总和减最大值。各段独立，从左扫到右即可。

我们可以用双指针指向当前连续相同颜色的气球的首尾，然后计算出当前连续相同颜色的气球的总时间 $s$，以及最大的时间 $mx$。如果当前连续相同颜色的气球个数大于 $1$，那么我们可以贪心地选择保留时间最大的气球，然后移除其它相同颜色的气球，耗时 $s-mx$，累加到答案中。接下来继续遍历，直到遍历完所有气球。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为气球的个数。

func minCost(colors string, neededTime []int) (ans int) {
	n := len(colors)
	for i, j := 0, 0; i < n; i = j {
		j = i
		s, mx := 0, 0
		for j < n && colors[j] == colors[i] {
			s += neededTime[j]
			mx = max(mx, neededTime[j])
			j++
		}
		if j-i > 1 {
			ans += s - mx
		}
	}
	return
}

力扣原题 · Doocs 题解来源