LeetCode Go · 动态规划（6）

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

来源与许可

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

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

975. 奇偶跳

困难2 种解法

标签：栈、数组、动态规划、有序集合、排序、单调栈

题目、示例与约束

给定一个整数数组 arr，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。

你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：

• 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 arr[i] <= arr[j]，且 arr[j] 的值尽可能小。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
• 在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 arr[i] >= arr[j]，且 arr[j] 的值尽可能大。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
• （对于某些索引 i，可能无法进行合乎要求的跳跃。）

如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 arr.length - 1），那么该索引就会被认为是好的起始索引。

返回好的起始索引的数量。

 

示例 1：

输入：[10,13,12,14,15]
输出：2
解释： 
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 arr[2] 是 arr[1]，arr[2]，arr[3]，arr[4] 中大于或等于 arr[0] 的最小值），然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

示例 2：

输入：[2,3,1,1,4]
输出：3
解释：
从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：

在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 arr[1] 是（arr[1]，arr[2]，arr[3]，arr[4]）中大于或等于 arr[0] 的最小值。

在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 arr[2] 是（arr[2]，arr[3]，arr[4]）中小于或等于 arr[1] 的最大值。arr[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。

在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 arr[3] 是（arr[3]，arr[4]）中大于或等于 arr[2] 的最小值。

我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。

类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

示例 3：

输入：[5,1,3,4,2]
输出：3
解释： 
我们可以从起始索引 1，2，4 出发到达数组末尾。

 

提示：

1. 1 <= arr.length <= 20000
2. 0 <= arr[i] < 100000

方法一：有序集合 + 记忆化搜索 · Go 实现

思考

奇数跳去右侧不小于当前值的最小者，偶数跳去不大于当前值的最大者，问有多少起点能到终点。从每个位置模拟跳跃会重复经过同一状态。从右往左用有序集合记下已出现的值与下标，即可 $O(\log n)$ 求出下一步 $g[i][0/1]$。能否到达只取决于 $(i,\text{奇偶})$，记忆化搜索即可。

我们先利用有序集合，预处理出每个位置能跳到的位置，记录在数组 $g$ 中，其中 $g[i][1]$ 和 $g[i][0]$ 分别表示当前位置是奇数次跳还是偶数次跳时能跳到的位置。如果不能跳到任何位置，那么 $g[i][1]$ 和 $g[i][0]$ 都为 $-1$。

然后利用记忆化搜索，从每个位置出发，且当前是奇数次跳跃，判断是否能跳到数组末尾，如果能，那么结果加一。

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

func oddEvenJumps(arr []int) (ans int) {
	n := len(arr)
	rbt := redblacktree.NewWithIntComparator()
	f := make([][2]int, n)
	g := make([][2]int, n)
	for i := n - 1; i >= 0; i-- {
		if v, ok := rbt.Ceiling(arr[i]); ok {
			g[i][1] = v.Value.(int)
		} else {
			g[i][1] = -1
		}
		if v, ok := rbt.Floor(arr[i]); ok {
			g[i][0] = v.Value.(int)
		} else {
			g[i][0] = -1
		}
		rbt.Put(arr[i], i)
	}
	var dfs func(int, int) int
	dfs = func(i, k int) int {
		if i == n-1 {
			return 1
		}
		if g[i][k] == -1 {
			return 0
		}
		if f[i][k] != 0 {
			return f[i][k]
		}
		f[i][k] = dfs(g[i][k], k^1)
		return f[i][k]
	}
	for i := 0; i < n; i++ {
		if dfs(i, 1) == 1 {
			ans++
		}
	}
	return
}

方法二：有序集合 + 动态规划 · Go 实现

思考

奇数跳去右侧不小于当前值的最小者，偶数跳去不大于当前值的最大者，问有多少起点能到终点。 $n$ 可以到 $2\times {10}^4$。全部元素相等时，每一步都落到紧邻的下一个下标，调用链长度就是 $n$，会超出默认递归上限。

从右往左扫描时，有序集合里只有更靠右的下标，所以下一步 $g[i][0/1]$ 要么是更大的下标，要么是 $-1$。

能否到达只取决于 $(i,\text{奇偶})$，并且只依赖更靠右的位置。令 $f[i][k]$ 表示从 $i$ 出发、下一次按奇偶 $k$ 跳能否到终点。 $f[n-1]$ 的两格都为真， $i$ 从 $n-2$ 递减到 $0$，有后继就把 $f[i][k]$ 设成后继上相反奇偶的结果。起点统计 $f[i][1]$。

我们先利用有序集合，预处理出每个位置能跳到的位置，记录在数组 $g$ 中，其中 $g[i][1]$ 和 $g[i][0]$ 分别表示当前位置是奇数次跳还是偶数次跳时能跳到的位置。如果不能跳到任何位置，那么 $g[i][1]$ 和 $g[i][0]$ 都为 $-1$。因为集合里只保存更靠右的下标，所以 $g[i][k]$ 要么为 $-1$，要么严格大于 $i$。

令 $f[i][k]$ 表示从下标 $i$ 出发、下一次跳跃的奇偶为 $k$ 时能否到达数组末尾。 $f[n-1][0]$ 与 $f[n-1][1]$ 都为真。 $i$ 从 $n-2$ 递减到 $0$：若 $g[i][k]\ne -1$，则 $f[i][k]=f[g[i][k]][k\oplus 1]$，否则 $f[i][k]$ 为假。右侧状态在填写时已经确定。

统计 $f[i][1]$ 为真的下标个数，即为答案。

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

func oddEvenJumps(arr []int) (ans int) {
	n := len(arr)
	rbt := redblacktree.NewWithIntComparator()
	g := make([][2]int, n)
	for i := n - 1; i >= 0; i-- {
		if v, ok := rbt.Ceiling(arr[i]); ok {
			g[i][1] = v.Value.(int)
		} else {
			g[i][1] = -1
		}
		if v, ok := rbt.Floor(arr[i]); ok {
			g[i][0] = v.Value.(int)
		} else {
			g[i][0] = -1
		}
		rbt.Put(arr[i], i)
	}
	f := make([][2]bool, n)
	f[n-1][0], f[n-1][1] = true, true
	for i := n - 2; i >= 0; i-- {
		for k := 0; k < 2; k++ {
			j := g[i][k]
			if j != -1 {
				f[i][k] = f[j][k^1]
			}
		}
	}
	for i := 0; i < n; i++ {
		if f[i][1] {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

978. 最长湍流子数组

中等1 种解法

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

题目、示例与约束

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：

• 若 i <= k < j ：
  • 当 k 为奇数时， A[k] > A[k+1]，且
  • 当 k 为偶数时，A[k] < A[k+1]；
• 或 若 i <= k < j ：
  • 当 k 为偶数时，A[k] > A[k+1] ，且
  • 当 k 为奇数时， A[k] < A[k+1]。

 

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：

输入：arr = [4,8,12,16]
输出：2

示例 3：

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

 

提示：

• 1 <= arr.length <= 4 * 104
• 0 <= arr[i] <= 109

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

思考

湍流要求相邻比较符号严格交替。枚举子数组再检查为平方级。以位置 $i$ 结尾时只需区分“最后一步上升 / 下降”两种长度，与前一位置的相反状态衔接，相等则重置为 $1$。两个变量滚动即可。

我们定义 $f[i]$ 表示以 $\mathit{\text{nums}}[i]$ 结尾且结尾处于上升状态的最长湍流子数组的长度，定义 $g[i]$ 表示以 $\mathit{\text{nums}}[i]$ 结尾且结尾处于下降状态的最长湍流子数组的长度。初始时 $f[0]=1$, $g[0]=1$。答案为 $max(f[i],g[i])$。

对于 $i>0$，若 $\mathit{\text{nums}}[i]>\mathit{\text{nums}}[i-1]$，则 $f[i]=g[i-1]+1$，否则 $f[i]=1$；若 $\mathit{\text{nums}}[i]<\mathit{\text{nums}}[i-1]$，则 $g[i]=f[i-1]+1$，否则 $g[i]=1$。

由于 $f[i]$ 和 $g[i]$ 只与 $f[i-1]$ 和 $g[i-1]$ 有关，因此可以使用两个变量代替数组。

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

func maxTurbulenceSize(arr []int) int {
	ans, f, g := 1, 1, 1
	for i, x := range arr[1:] {
		ff, gg := 1, 1
		if arr[i] < x {
			ff = g + 1
		}
		if arr[i] > x {
			gg = f + 1
		}
		f, g = ff, gg
		ans = max(ans, max(f, g))
	}
	return ans
}

力扣原题 · Doocs 题解来源

983. 最低票价

中等2 种解法

标签：数组、动态规划

题目、示例与约束

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

• 一张 为期一天 的通行证售价为 costs[0] 美元；
• 一张 为期七天 的通行证售价为 costs[1] 美元；
• 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

 

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

 

提示：

• 1 <= days.length <= 365
• 1 <= days[i] <= 365
• days 按顺序严格递增
• costs.length == 3
• 1 <= costs[i] <= 1000

方法一：记忆化搜索 + 二分查找 · Go 实现

思考

出行日必须被 $1/7/30$ 日票覆盖，求最少花费。在第 $i$ 次出行买哪种票，下一次未覆盖的出行可用二分定位。 $dfs(i)$ 对三种票取最小，出行次数 $\le 365$，记忆化即可。

我们定义一个函数 $\mathit{\text{dfs(i)}}$，表示从第 $i$ 次出行开始到最后一次出行结束所需的最小花费。那么答案为 $\mathit{\text{dfs(0)}}$。

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

• 如果 $i\ge n$，表示所有出行已经结束，返回 $0$；
• 否则，我们需要考虑三种购买方式，分别是购买 $1$ 天通行证、购买 $7$ 天通行证和购买 $30$ 天通行证。我们分别计算这三种购买方式的花费，并且利用二分查找，找到下一次出行的下标 $j$，然后递归调用 $\mathit{\text{dfs(j)}}$，最后返回这三种购买方式的最小花费。

为了避免重复计算，我们使用记忆化搜索，将已经计算过的结果保存起来。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 表示出行的次数。

func mincostTickets(days []int, costs []int) int {
	valid := [3]int{1, 7, 30}
	n := len(days)
	f := make([]int, n)
	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if f[i] > 0 {
			return f[i]
		}
		f[i] = 1 << 30
		for k := 0; k < 3; k++ {
			j := sort.SearchInts(days, days[i]+valid[k])
			f[i] = min(f[i], dfs(j)+costs[k])
		}
		return f[i]
	}
	return dfs(0)
}

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

思考

按出行下标搜索需要二分。也可按日历日递推： $f[i]$ 为到第 $i$ 天的最少花费，非出行日等于 $f[i-1]$，出行日则在三种票的起点取 $min$。日期上界为 $365$。

我们不妨记 $\mathit{\text{days}}$ 数组中的最后一天为 $m$，那么我们可以定义一个长度为 $m+1$ 的数组 $f$，其中 $f[i]$ 表示从第 $1$ 天到第 $i$ 天的最小花费。

我们可以按照 $\mathit{\text{days}}$ 数组中的日期递增的顺序，从第 $1$ 天开始，依次计算 $f[i]$ 的值。如果第 $i$ 天是出行的日期，那么我们可以考虑三种购买方式，分别是购买 $1$ 天通行证、购买 $7$ 天通行证和购买 $30$ 天通行证。我们分别计算这三种购买方式的花费，并且取这三种购买方式的最小花费作为 $f[i]$ 的值。如果第 $i$ 天不是出行的日期，那么 $f[i]=f[i-1]$。

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

时间复杂度 $O(m)$，空间复杂度 $O(m)$。其中 $m$ 表示出行的最后一天。

func mincostTickets(days []int, costs []int) int {
	m := days[len(days)-1]
	f := make([]int, m+1)
	valid := [3]int{1, 7, 30}
	for i, j := 1, 0; i <= m; i++ {
		if i == days[j] {
			f[i] = 1 << 30
			for k, v := range valid {
				c := costs[k]
				f[i] = min(f[i], f[max(0, i-v)]+c)
			}
			j++
		} else {
			f[i] = f[i-1]
		}
	}
	return f[m]
}

力扣原题 · Doocs 题解来源

996. 平方数组的数目

困难1 种解法

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

题目、示例与约束

如果一个数组的任意两个相邻元素之和都是 完全平方数 ，则该数组称为 平方数组 。

给定一个整数数组 nums，返回所有属于 平方数组 的 nums 的排列数量。

如果存在某个索引 i 使得 perm1[i] != perm2[i]，则认为两个排列 perm1 和 perm2 不同。

 

示例 1：

输入：nums = [1,17,8]
输出：2
解释：[1,8,17] 和 [17,8,1] 是有效的排列。

示例 2：

输入：nums = [2,2,2]
输出：1

 

提示：

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

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

思考

排列使每对相邻和为完全平方。 $n\le 12$，可用子集 DP。 $f[S][j]$ 表示用完集合 $S$、止于 $j$ 的方案；仅当 $nums[j]+nums[k]$ 为平方时从 $k$ 转移。相同数字会被不同下标重复计数，最后除以各值频数的阶乘。

注意到，数组 $nums$ 的长度 $n$ 不超过 $12$，因此我们可以用一个二进制数表示当前所选的数字的状态，若第 $i$ 位为 $1$，则表示当前选择了第 $i$ 个数字，否则表示当前没有选择第 $i$ 个数字。

我们定义 $f[i][j]$ 表示当前所选的数字的状态为 $i$，且最后一个数字为 $nums[j]$ 的方案数。那么答案就是 $\sum _{j=0}^{n-1}f[2^n-1][j]$。由于最后求解的是排列数，因此还需要除以每个数字出现的次数的阶乘。

接下来，我们考虑如何进行状态转移。

假设当前所选的数字的状态为 $i$，最后一个数字为 $nums[j]$，那么我们可以枚举 $i$ 的每一位为 $1$ 的数字作为倒数第二个数，不妨设为 $nums[k]$，那么我们只需要判断 $nums[j]+nums[k]$ 是否为完全平方数即可，若是，方案数 $f[i][j]$ 就可以加上 $f[i\oplus 2^j][k]$，其中 $i\oplus 2^j$ 表示将 $i$ 的第 $j$ 位取反，即表示将 $nums[j]$ 从当前所选的数字中去除。

最后，我们还需要除以每个数字出现的次数的阶乘，因为我们在枚举 $i$ 的每一位为 $1$ 的数字时，可能会重复计算某些排列，因此需要除以每个数字出现的次数的阶乘。

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

func numSquarefulPerms(nums []int) (ans int) {
	n := len(nums)
	f := make([][]int, 1<<n)
	for i := range f {
		f[i] = make([]int, n)
	}
	for j := range nums {
		f[1<<j][j] = 1
	}
	for i := 0; i < 1<<n; i++ {
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				for k := 0; k < n; k++ {
					if i>>k&1 == 1 && k != j {
						s := nums[j] + nums[k]
						t := int(math.Sqrt(float64(s)))
						if t*t == s {
							f[i][j] += f[i^(1<<j)][k]
						}
					}
				}
			}
		}
	}
	for j := 0; j < n; j++ {
		ans += f[(1<<n)-1][j]
	}
	g := [13]int{1}
	for i := 1; i < 13; i++ {
		g[i] = g[i-1] * i
	}
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for _, v := range cnt {
		ans /= g[v]
	}
	return
}

力扣原题 · Doocs 题解来源

1000. 合并石头的最低成本

困难1 种解法

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

题目、示例与约束

有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。

每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。

 

示例 1：

输入：stones = [3,2,4,1], K = 2
输出：20
解释：
从 [3, 2, 4, 1] 开始。
合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
合并 [4, 1]，成本为 5，剩下 [5, 5]。
合并 [5, 5]，成本为 10，剩下 [10]。
总成本 20，这是可能的最小值。

示例 2：

输入：stones = [3,2,4,1], K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.

示例 3：

输入：stones = [3,5,1,2,6], K = 3
输出：25
解释：
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
合并 [3, 8, 6]，成本为 17，剩下 [17]。
总成本 25，这是可能的最小值。

 

提示：

• n == stones.length
• 1 <= n <= 30
• 1 <= stones[i] <= 100
• 2 <= k <= 30

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

思考

枚举所有合并顺序可以给出答案，但 $n\le 30$ 时合法划分的数量随区间长度迅速增长，无法在时限内穷尽。任意一次操作只作用于连续 $K$ 堆，因此真正决定代价的是「某一段最终并成若干堆」这一子问题，而同一区间会被许多顺序重复计算。

注意到每次把 $K$ 堆合成一堆，堆数减少 $K-1$，故仅当 $(n-1)mod(K-1)=0$ 时才能并成一堆，否则直接返回 $-1$。可行时，将 $[i,j]$ 并成 $k$ 堆，等价于先把某一前缀并成 $1$ 堆、后缀并成 $k-1$ 堆；若要并成 $1$ 堆，则须先得到 $K$ 堆再付出该区间石子总和。

为此按区间长度递推 $f[i][j][k]$，并用前缀和 $s$ 在 $O(1)$ 内取出区间和。枚举断点 $h$ 时只取左段的 $f[i][h][1]$，与「一次只能合并连续堆」的约束一致，最终答案为 $f[1][n][1]$。

我们不妨记题目中的 $k$ 为 $K$，石头的堆数为 $n$。

定义 $f[i][j][k]$ 表示将区间 $[i,j]$ 中的石头合并成 $k$ 堆的最小成本。初始时 $f[i][i][1]=0$，其他位置的值均为 $\mathrm{\infty }$。

注意到 $k$ 的取值范围为 $[1,K]$，因此我们需要枚举 $k$ 的值。

对于 $f[i][j][k]$，我们可以枚举 $i\le h<j$，将区间 $[i,j]$ 拆分成两个区间 $[i,h]$ 和 $[h+1,j]$，然后将 $[i,h]$ 中的石头合并成 $1$ 堆，将 $[h+1,j]$ 中的石头合并成 $k-1$ 堆，最后将这两堆石头合并成一堆，这样就可以将区间 $[i,j]$ 中的石头合并成 $k$ 堆。因此，我们可以得到状态转移方程：

$$f[i][j][k]=\underset{i\le h<j}{min}\{f[i][h][1]+f[h+1][j][k-1]\}$$

我们将区间 $[i,j]$ 的 $K$ 堆石头合并成一堆，因此 $f[i][j][1]=f[i][j][K]+\sum _{t=i}^{j}stones[t]$，其中 $\sum _{t=i}^{j}stones[t]$ 表示区间 $[i,j]$ 中石头的总数。

最后答案即为 $f[1][n][1]$，其中 $n$ 为石头的堆数。

时间复杂度 $O(n^3\times k)$，空间复杂度 $O(n^2\times k)$。其中 $n$ 为石头的堆数。

func mergeStones(stones []int, K int) int {
	n := len(stones)
	if (n-1)%(K-1) != 0 {
		return -1
	}
	s := make([]int, n+1)
	for i, x := range stones {
		s[i+1] = s[i] + x
	}
	f := make([][][]int, n+1)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, K+1)
			for k := range f[i][j] {
				f[i][j][k] = 1 << 20
			}
		}
	}
	for i := 1; i <= n; i++ {
		f[i][i][1] = 0
	}
	for l := 2; l <= n; l++ {
		for i := 1; i <= n-l+1; i++ {
			j := i + l - 1
			for k := 2; k <= K; k++ {
				for h := i; h < j; h++ {
					f[i][j][k] = min(f[i][j][k], f[i][h][k-1]+f[h+1][j][1])
				}
			}
			f[i][j][1] = f[i][j][K] + s[j] - s[i-1]
		}
	}
	return f[1][n][1]
}

力扣原题 · Doocs 题解来源

1012. 至少有 1 位重复的数字

困难1 种解法

标签：数学、动态规划

题目、示例与约束

给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

 

示例 1：

输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。

示例 2：

输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。

示例 3：

输入：n = 1000
输出：262

 

提示：

• 1 <= n <= 109

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

思考

直接枚举 $[1,n]$ 并检查是否有重复数位， $n\le {10}^9$ 不可行。改统计没有重复数位的个数 $f(n)$，答案即为 $n-f(n)$。

数位逐位填写时，已用过的数字集合决定下一步还能选什么，前导零不应占用集合，且上界受 $n$ 的数位约束。集合大小为 $10$，可用二进制掩码表示。

记忆化 $\mathit{\text{dfs}}(i,\mathit{\text{mask}},\mathit{\text{lead}},\mathit{\text{limit}})$ 按第 $i$ 位枚举合法数字：仍为前导零则掩码不变；否则仅当该位未出现过才继续。终点在非前导零时计 $1$。

题目要求统计 $[1,..n]$ 中至少有一位重复的数字的个数，我们可以换一种思路，用一个函数 $f(n)$ 统计 $[1,..n]$ 中没有重复数字的个数，那么答案就是 $n-f(n)$。

另外，我们可以用一个二进制数来记录数字中出现过的数字，比如数字中出现了 $1$, $2$, $4$，那么对应的二进制数就是 $\underset{―}{1}0\underset{―}{1}\underset{―}{1}0$。

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

基本步骤如下：

我们将数字 $n$ 转为字符串 $s$，接下来，我们设计一个函数 $\mathit{\text{dfs}}(i,\mathit{\text{mask}},\mathit{\text{lead}},\mathit{\text{limit}})$，其中：

• 数字 $i$ 表示当前处理的数字下标，从 $0$ 开始。
• 数字 $\mathit{\text{mask}}$ 表示当前数字中出现过的数字，用二进制数表示。其中 $\mathit{\text{mask}}$ 的二进制的第 $j$ 位为 $1$ 表示数字 $j$ 出现过，为 $0$ 表示数字 $j$ 没有出现过。
• 布尔值 $\mathit{\text{lead}}$ 表示是否只包含前导零。
• 布尔值 $\mathit{\text{limit}}$ 表示当前位置是否受到上界的限制。

函数的执行过程如下：

如果 $i$ 大于等于 $m$，说明我们已经处理完了所有的位数，此时如果 $\mathit{\text{lead}}$ 为真，说明当前的数字是前导零，我们应当返回 $0$；否则，我们应当返回 $1$。

否则，我们计算当前位置的上界 $\mathit{\text{up}}$，如果 $\mathit{\text{limit}}$ 为真，则 $up$ 为 $s[i]$ 对应的数字，否则 $up$ 为 $9$。

然后，我们在 $[0,\mathit{\text{up}}]$ 的范围内枚举当前位置的数字 $j$，如果 $j$ 为 $0$ 且 $\mathit{\text{lead}}$ 为真，我们递归计算 $\mathit{\text{dfs}}(i+1,\mathit{\text{mask}},\text{true},\mathit{\text{limit}}\wedge j=\mathit{\text{up}})$；否则，如果 $\mathit{\text{mask}}$ 的第 $j$ 位为 $0$，我们递归计算 $\mathit{\text{dfs}}(i+1,\mathit{\text{mask}}|2^j,\text{false},\mathit{\text{limit}}\wedge j=\mathit{\text{up}})$。累加所有的结果即为答案。

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

时间复杂度 $O(\log n\times 2^D\times D)$，空间复杂度 $O(\log n\times 2^D)$。其中 $D=10$。

相似题目：

• 233. 数字 1 的个数
• 357. 统计各位数字都不同的数字个数
• 600. 不含连续 1 的非负整数
• 788. 旋转数字
• 902. 最大为 N 的数字组合
• 2376. 统计特殊整数

func numDupDigitsAtMostN(n int) int {
	s := []byte(strconv.Itoa(n))
	m := len(s)
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, 1<<10)
		for j := range f[i] {
			f[i][j] = -1
		}
	}

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

力扣原题 · Doocs 题解来源

1014. 最佳观光组合

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

 

示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

输入：values = [1,2]
输出：2

 

提示：

• 2 <= values.length <= 5 * 104
• 1 <= values[i] <= 1000

方法一：枚举 · Go 实现

思考

枚举所有 $i<j$ 计算 $values[i]+values[j]+i-j$ 为平方级。把式子拆成 $(values[i]+i)+(values[j]-j)$ 后，对固定的 $j$ 只需知道左侧 $values[i]+i$ 的最大值。

从左到右扫 $j$，用一个变量维护截至 $j-1$ 的 $values[i]+i$，即可在常数时间得到当前位置的最优配对，再把 $values[j]+j$ 纳入维护。

这样每个景点只作为右端点看一次、作为左端候选更新一次，线性即可。

我们可以从左到右枚举 $j$，同时维护 $j$ 左侧元素中 $values[i]+i$ 的最大值 $mx$，这样对于每个 $j$，最大得分为 $mx+values[j]-j$。我们取所有位置的最大得分的最大值即为答案。

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

func maxScoreSightseeingPair(values []int) (ans int) {
	mx := 0
	for j, x := range values {
		ans = max(ans, mx+x-j)
		mx = max(mx, x+j)
	}
	return
}

力扣原题 · Doocs 题解来源

1024. 视频拼接

中等1 种解法

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

题目、示例与约束

你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。

甚至可以对这些片段自由地再剪辑：

• 例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

 

示例 1：

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出：3
解释：
选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。

示例 2：

输入：clips = [[0,1],[1,2]], time = 5
输出：-1
解释：
无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

示例 3：

输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
输出：3
解释： 
选取片段 [0,4], [4,7] 和 [6,9] 。

 

提示：

• 1 <= clips.length <= 100
• 0 <= starti <= endi <= 100
• 1 <= time <= 100

方法一：贪心 · Go 实现

思考

区间数量与时间上界均不超过 $100$，枚举子集可以覆盖 $[0,\mathit{\text{time}}]$，但子集数为指数。同一起点只需保留右端最远的片段，问题化成「从当前位置能跳到的最远覆盖」。

这与跳跃游戏相同：记下每个起点的最远终点 $\mathit{\text{last}}[i]$，从左扫描维护当前可达 $\mathit{\text{mx}}$；若 $\mathit{\text{mx}}$ 停在 $i$，则无法前进。每越过上一段的右端 $\mathit{\text{pre}}$ 就增加一段。

一遍扫描得到最少片段数，或在断开时返回 $-1$。

注意到，如果相同起点的子区间有多个，那么选择右端点最大的那个子区间是最优的。

因此，我们可以预处理所有子区间，对于每一个位置 $i$，算出所有以 $i$ 为起点的子区间中，右端点最大的那个位置，记录在数组 $last[i]$ 中。

我们定义变量 mx 表示当前能够到达的最远位置，变量 ans 表示当前需要的最少子区间数，变量 pre 表示上一个被使用的子区间的右端点。

接下来，我们从 $0$ 开始枚举所有位置 $i$，用 $last[i]$ 来更新 mx。如果更新后 $mx=i$，说明无法覆盖下一个位置，因此无法完成任务，返回 $-1$。

同时我们记录上一个被使用的子区间的右端点 pre，如果 $pre=i$，说明需要使用一个新的子区间，因此我们将 ans 加 $1$，并将 pre 更新为 mx。

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

时间复杂度 $O(n+m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别是数组 clips 的长度和 time 的值。

相似题目：

• 45. 跳跃游戏 II
• 55. 跳跃游戏
• 1326. 灌溉花园的最少水龙头数目

func videoStitching(clips [][]int, time int) int {
	last := make([]int, time)
	for _, v := range clips {
		a, b := v[0], v[1]
		if a < time {
			last[a] = max(last[a], b)
		}
	}
	ans, mx, pre := 0, 0, 0
	for i, v := range last {
		mx = max(mx, v)
		if mx <= i {
			return -1
		}
		if pre == i {
			ans++
			pre = mx
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1025. 除数博弈

简单1 种解法

标签：脑筋急转弯、数学、动态规划、博弈、无偏博弈

题目、示例与约束

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：

• 选出任一整数 x，满足 0 < x < n 且 n % x == 0 。
• 用 n - x 替换黑板上的数字 n 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

 

示例 1：

输入：n = 2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

输入：n = 3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

 

提示：

• 1 <= n <= 1000

方法一：数学归纳法 · Go 实现

思考

$n\le 1000$，可用 DP 记录每个剩余值的胜负：存在一种 $x$ 使对手面对必败态则先手胜。观察小值可知奇数先手败、偶数先手胜，随后可用归纳确认。

奇数的真因数仍为奇数，减去后留给对手偶数；偶数总能减 $1$ 留给对手奇数。因此胜负完全由 $n$ 的奇偶决定。

返回 $n$ 为偶数即可，不必再做递推。

• 当 $n=1$，先手败
• 当 $n=2$，先手拿 $1$，剩下 $1$，后手败，先手胜
• 当 $n=3$，先手拿 $1$，剩下 $2$，后手胜，先手败
• 当 $n=4$，先手拿 $1$，剩下 $3$，后手败，先手胜
• ...

猜想，当 $n$ 为奇数时，先手败；当 $n$ 为偶数时，先手胜。

证明：

1. 若 $n=1$ 或 $n=2$，结论成立；
2. 若 $n>2$，假设 $n\le k$ 时，该结论成立，则 $n=k+1$ 时：
   • 若 $k+1$ 为奇数，由于 $x$ 是 $k+1$ 的因数，那么 $x$ 只可能是奇数，因此 $k+1-x$ 为偶数，后手胜，先手败；
   • 若 $k+1$ 为偶数，此时 $x$ 既可以是奇数 $1$，也可以是偶数，若 $x$ 取奇数，那么 $k+1-x$ 为奇数，后手败，先手胜。

综上，当 $n$ 为奇数时，先手败；当 $n$ 为偶数时，先手胜。结论正确。

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

func divisorGame(n int) bool {
	return n%2 == 0
}

力扣原题 · Doocs 题解来源

1027. 最长等差数列

中等1 种解法

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

题目、示例与约束

给定一个整数数组 nums，返回 nums 中最长等差子序列的长度。

注意：

• 子序列 是由另一个数组删除一些（也可以不删除）元素后得到的数组，并且不改变剩余元素之间的相对顺序。
• 如果对于所有 0 <= i < seq.length - 1，seq[i + 1] - seq[i] 的值都相同，则称序列 seq 为等差序列。

 

示例 1：

输入： nums = [3, 6, 9, 12]

输出： 4

解释： 整个数组本身就是一个公差为 3 的等差序列，因此最长等差子序列为 [3, 6, 9, 12]，长度为 4。

示例 2：

输入： nums = [9, 4, 7, 2, 10]

输出： 3

解释： 最长等差子序列为 [4, 7, 10]（下标分别为 1、2、4），公差为 3。不存在长度为 4 的等差子序列。

示例 3：

输入： nums = [20, 1, 15, 3, 10, 5, 8]

输出： 4

解释： 最长等差子序列为 [20, 15, 10, 5]（下标分别为 0、2、4、5），公差为 -5。

 

提示：

• 2 <= nums.length <= 1500
• 0 <= nums[i] <= 500

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

思考

枚举公差再对每个公差求最长子序列， $n\le 1000$ 且值域在 $[0,500]$，公差种类约 ${10}^3$，双重枚举下标即可在时限内完成。子序列不必连续，状态应落在「以某下标结尾、某公差」。

定义 $f[i][j]$ 为以 $i$ 结尾、公差为 $j$ 的最长长度。因公差可负，将 $j$ 平移 $500$ 后落在 $[0,1000]$。转移枚举 $k<i$，用 $f[k][j]+1$ 更新。

每个下标对更新一次，答案取所有 $f[i][j]$ 的最大者。

我们定义 $f[i][j]$ 表示以 $nums[i]$ 结尾且公差为 $j$ 的等差数列的最大长度。初始时 $f[i][j]=1$，即每个元素自身都是一个长度为 $1$ 的等差数列。

由于公差可能为负数，且最大差值为 $500$，因此，我们可以将统一将公差加上 $500$，这样公差的范围就变成了 $[0,1000]$。

考虑 $f[i]$，我们可以枚举 $nums[i]$ 的前一个元素 $nums[k]$，那么公差 $j=nums[i]-nums[k]+500$，此时有 $f[i][j]=max(f[i][j],f[k][j]+1)$，然后我们更新答案 $ans=max(ans,f[i][j])$。

最后返回答案即可。

如果初始时 $f[i][j]=0$，那么我们需要在最后返回答案时加上 $1$。

时间复杂度 $O(n\times (d+n))$，空间复杂度 $O(n\times d)$。其中 $n$ 和 $d$ 分别是数组 $nums$ 的长度以及数组 $nums$ 中元素的最大值与最小值的差值。

func longestArithSeqLength(nums []int) int {
	n := len(nums)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, 1001)
	}
	ans := 0
	for i := 1; i < n; i++ {
		for k := 0; k < i; k++ {
			j := nums[i] - nums[k] + 500
			f[i][j] = max(f[i][j], f[k][j]+1)
			ans = max(ans, f[i][j])
		}
	}
	return ans + 1
}

力扣原题 · Doocs 题解来源

1031. 两个无重叠子数组的最大和

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个无重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。

长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是无重叠。

子数组是数组的一个 连续 部分。

 

示例 1：

输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。

示例 2：

输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

示例 3：

输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。

 

提示：

• 1 <= firstLen, secondLen <= 1000
• 2 <= firstLen + secondLen <= 1000
• firstLen + secondLen <= nums.length <= 1000
• 0 <= nums[i] <= 1000

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

思考

枚举两段的左右端点需要 $O(n^2)$，长度 $n\le 1000$ 偏紧。固定其中一段后，另一段的最优位置只取决于它左侧（或右侧）定长窗口的最大和。

前缀和使任意定长窗口的和可在 $O(1)$ 取出。分「长为 $\mathit{\text{firstLen}}$ 的段在左」与「长为 $\mathit{\text{secondLen}}$ 的段在左」两种情形，扫右段左端点时用变量 $t$ 维护左侧窗口的历史最大和。

两种情形各扫一遍，取较大者。

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

接下来，我们分两种情况枚举：

假设 $firstLen$ 个元素的子数组在 $secondLen$ 个元素的子数组的左边，那么我们可以枚举 $secondLen$ 个元素的子数组的左端点 $i$，用变量 $t$ 维护左边 $firstLen$ 个元素的子数组的最大和，那么答案就是 $t+s[i+secondLen]-s[i]$。枚举完所有的 $i$，就可以得到候选答案。

假设 $secondLen$ 个元素的子数组在 $firstLen$ 个元素的子数组的左边，那么我们可以枚举 $firstLen$ 个元素的子数组的左端点 $i$，用变量 $t$ 维护左边 $secondLen$ 个元素的子数组的最大和，那么答案就是 $t+s[i+firstLen]-s[i]$。枚举完所有的 $i$，就可以得到候选答案。

最后，我们取两种情况下的候选答案的最大值即可。

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

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) (ans int) {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	for i, t := firstLen, 0; i+secondLen-1 < n; i++ {
		t = max(t, s[i]-s[i-firstLen])
		ans = max(ans, t+s[i+secondLen]-s[i])
	}
	for i, t := secondLen, 0; i+firstLen-1 < n; i++ {
		t = max(t, s[i]-s[i-secondLen])
		ans = max(ans, t+s[i+firstLen]-s[i])
	}
	return
}

力扣原题 · Doocs 题解来源

1035. 不相交的线

中等1 种解法

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

题目、示例与约束

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

•  nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

 

示例 1：

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：

输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：

输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

 

提示：

• 1 <= nums1.length, nums2.length <= 500
• 1 <= nums1[i], nums2[j] <= 2000

 

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

思考

连线不能交叉，等价于在两序列中取一组下标严格递增的相等对，即最长公共子序列。 $m,n\le 500$，适合 $O(mn)$ 的二维 DP。

令 $f[i][j]$ 为两序列前缀的最大连线数：末元素相等则来自 $f[i-1][j-1]+1$，否则取少用一侧的较优值。

填完表格后 $f[m][n]$ 即为答案。

我们定义 $f[i][j]$ 表示 $\mathit{\text{nums1}}$ 前 $i$ 个数和 $\mathit{\text{nums2}}$ 前 $j$ 个数的最大连线数。初始时 $f[i][j]=0$，答案即为 $f[m][n]$。

当 $\mathit{\text{nums1}}[i-1]=\mathit{\text{nums2}}[j-1]$ 时，我们可以在 $\mathit{\text{nums1}}$ 的前 $i-1$ 个数和 $\mathit{\text{nums2}}$ 的前 $j-1$ 个数的基础上增加一条连线，此时 $f[i][j]=f[i-1][j-1]+1$。

当 $\mathit{\text{nums1}}[i-1]\ne \mathit{\text{nums2}}[j-1]$ 时，我们要么在 $\mathit{\text{nums1}}$ 的前 $i-1$ 个数和 $\mathit{\text{nums2}}$ 的前 $j$ 个数的基础上求解，要么在 $\mathit{\text{nums1}}$ 的前 $i$ 个数和 $\mathit{\text{nums2}}$ 的前 $j-1$ 个数的基础上求解，取两者的最大值，即 $f[i][j]=max(f[i-1][j],f[i][j-1])$。

最后返回 $f[m][n]$ 即可。

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

func maxUncrossedLines(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 i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if nums1[i-1] == nums2[j-1] {
				f[i][j] = f[i-1][j-1] + 1
			} else {
				f[i][j] = max(f[i-1][j], f[i][j-1])
			}
		}
	}
	return f[m][n]
}

力扣原题 · Doocs 题解来源

1039. 多边形三角剖分的最低得分

中等3 种解法

标签：数组、动态规划、多边形、三角剖分

题目、示例与约束

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是按 顺时针顺序 第 i 个顶点的值。

假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。
 

示例 1：

输入：values = [1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：

输入：values = [3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。

示例 3：

输入：values = [1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。

 

提示：

• n == values.length
• 3 <= n <= 50
• 1 <= values[i] <= 100

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

思考

凸多边形的三角剖分方案数是卡特兰数， $n\le 50$ 时不能枚举整棵剖分树。任意剖分都包含一条以边 $(i,j)$ 为底、第三点为 $k$ 的三角形，两侧是规模更小的子多边形。

子问题只依赖端点对 $(i,j)$，用记忆化 $\mathit{\text{dfs}}(i,j)$ 枚举 $k\in (i,j)$，代价为两侧答案加上 $values[i]\cdot values[k]\cdot values[j]$。相邻顶点无法剖分，返回 $0$。

入口为 $\mathit{\text{dfs}}(0,n-1)$。

我们设计一个函数 $\text{dfs}(i,j)$，表示将多边形的顶点 $i$ 到 $j$ 进行三角剖分后的最低分数。那么答案就是 $\text{dfs}(0,n-1)$。

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

如果 $i+1=j$，说明多边形只有两个顶点，无法进行三角剖分，返回 $0$；

否则，我们枚举 $i$ 和 $j$ 之间的一个顶点 $k$，即 $i<k<j$，将多边形的顶点 $i$ 到 $j$ 进行三角剖分，可以分为两个子问题：将多边形的顶点 $i$ 到 $k$ 进行三角剖分，以及将多边形的顶点 $k$ 到 $j$ 进行三角剖分。这两个子问题的最低分数分别为 $\text{dfs}(i,k)$ 和 $\text{dfs}(k,j)$，而顶点 $i$, $j$ 和 $k$ 构成的三角形的分数为 $\text{values}[i]\times \text{values}[k]\times \text{values}[j]$。那么，此次三角剖分的最低分数为 $\text{dfs}(i,k)+\text{dfs}(k,j)+\text{values}[i]\times \text{values}[k]\times \text{values}[j]$，我们取所有可能的最小值，即为 $\text{dfs}(i,j)$ 的值。

为了避免重复计算，我们可以使用记忆化搜索，即使用哈希表或者数组来存储已经计算过的函数值。

最后，我们返回 $\text{dfs}(0,n-1)$ 即可。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为多边形的顶点数。

func minScoreTriangulation(values []int) int {
	n := len(values)
	f := [50][50]int{}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i+1 == j {
			return 0
		}
		if f[i][j] != 0 {
			return f[i][j]
		}
		f[i][j] = 1 << 30
		for k := i + 1; k < j; k++ {
			f[i][j] = min(f[i][j], dfs(i, k)+dfs(k, j)+values[i]*values[k]*values[j])
		}
		return f[i][j]
	}
	return dfs(0, n-1)
}

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

思考

记忆化仍有递归开销，且状态依赖关系是区间包含。同一转移写成自底向上：较短区间先算完，较长区间才能取到子区间的值。

按左端点递减、右端点递增填 $f[i][j]$，枚举 $k$ 的式子与搜索相同，答案为 $f[0][n-1]$。

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

定义 $f[i][j]$ 表示将多边形的顶点 $i$ 到 $j$ 进行三角剖分后的最低分数。初始时 $f[i][j]=0$，答案为 $f[0][n-1]$。

对于 $f[i][j]$（这里要求 $i+1<j$），我们先将 $f[i][j]$ 初始化为 $\mathrm{\infty }$。

我们枚举 $i$ 和 $j$ 之间的一个顶点 $k$，即 $i<k<j$，将多边形的顶点 $i$ 到 $j$ 进行三角剖分，可以分为两个子问题：将多边形的顶点 $i$ 到 $k$ 进行三角剖分，以及将多边形的顶点 $k$ 到 $j$ 进行三角剖分。这两个子问题的最低分数分别为 $f[i][k]$ 和 $f[k][j]$，而顶点 $i$, $j$ 和 $k$ 构成的三角形的分数为 $\text{values}[i]\times \text{values}[k]\times \text{values}[j]$。那么，此次三角剖分的最低分数为 $f[i][k]+f[k][j]+\text{values}[i]\times \text{values}[k]\times \text{values}[j]$，我们取所有可能的最小值，即为 $f[i][j]$ 的值。

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

$$f[i][j]=\{\begin{array}{ll}0,& i+1=j\\ \mathrm{\infty },& i+1<j\\ \underset{i<k<j}{min}\{f[i][k]+f[k][j]+\text{values}[i]\times \text{values}[k]\times \text{values}[j]\},& i+1<j\end{array}$$

注意，在枚举 $i$ 和 $j$ 时，我们可以有两种枚举方式：

1. 从大到小枚举 $i$，从小到大枚举 $j$，这样可以保证在计算状态 $f[i][j]$ 时，状态 $f[i][k]$ 和 $f[k][j]$ 都已经计算过了；
2. 从小到大枚举区间长度 $l$，其中 $3\le l\le n$，然后枚举区间左端点 $i$，那么可以得到右端点 $j=i+l-1$，这样也可以保证在计算较大区间 $f[i][j]$ 时，较小区间 $f[i][k]$ 和 $f[k][j]$ 都已经计算过了。

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

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为多边形的顶点数。

相似题目：

• 1312. 让字符串成为回文串的最少插入次数

func minScoreTriangulation(values []int) int {
	n := len(values)
	f := [50][50]int{}
	for i := n - 3; i >= 0; i-- {
		for j := i + 2; j < n; 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]+values[i]*values[k]*values[j])
			}
		}
	}
	return f[0][n-1]
}

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

思考

方法二按端点嵌套循环，需小心保证子区间已计算。按区间长度 $l$ 从 $3$ 增到 $n$ 枚举，左端 $i$、右端 $j=i+l-1$，则两侧长度更短，自然已经填好。

转移式不变，只是枚举顺序换成「先长度后位置」。

方法二中，我们提到了两种枚举方式。这里我们使用第二种方式，从小到大枚举区间长度 $l$，其中 $3\le l\le n$，然后枚举区间左端点 $i$，那么可以得到右端点 $j=i+l-1$。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为多边形的顶点数。

func minScoreTriangulation(values []int) int {
	n := len(values)
	f := [50][50]int{}
	for l := 3; l <= n; l++ {
		for i := 0; i+l-1 < n; i++ {
			j := i + l - 1
			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]+values[i]*values[k]*values[j])
			}
		}
	}
	return f[0][n-1]
}

力扣原题 · Doocs 题解来源

1043. 分隔数组以得到最大和

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

 

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

示例 2：

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

示例 3：

输入：arr = [1], k = 1
输出：1

 

提示：

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 109
• 1 <= k <= arr.length

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

思考

划分方案数为指数， $n\le 500$、 $k\le n$ 不能枚举全部切法。最后一段长度至多为 $k$，其贡献等于该段最大值乘长度，之前的部分是规模更小的同类问题。

令 $f[i]$ 为前 $i$ 个元素的最大和。从 $i$ 往左枚举最后一段起点 $j$，同时维护段内最大值 $\mathit{\text{mx}}$，用 $f[j-1]+\mathit{\text{mx}}\cdot (i-j+1)$ 更新。

按 $i$ 递增填表，答案为 $f[n]$。

我们定义 $f[i]$ 表示将数组的前 $i$ 个元素分隔成若干个子数组，最终的最大元素和。初始时 $f[i]=0$，答案为 $f[n]$。

我们考虑如何计算 $f[i]$，其中 $i\ge 1$。

对于 $f[i]$，它的最后一个元素是 $arr[i-1]$。由于每个子数组的长度最多为 $k$，并且我们需要求得子数组中的最大值，因此，我们可以从右往左枚举最后一个子数组的第一个元素 $arr[j-1]$，其中 $max(0,i-k)<j\le i$，过程中维护一个变量 $mx$，表示最后一个子数组中的最大值，那么状态转移方程为：

$$f[i]=max\{f[i],f[j-1]+mx\times (i-j+1)\}$$

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

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

func maxSumAfterPartitioning(arr []int, k int) int {
	n := len(arr)
	f := make([]int, n+1)
	for i := 1; i <= n; i++ {
		mx := 0
		for j := i; j > max(0, i-k); j-- {
			mx = max(mx, arr[j-1])
			f[i] = max(f[i], f[j-1]+mx*(i-j+1))
		}
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

1048. 最长字符串链

中等2 种解法

标签：数组、哈希表、双指针、字符串、动态规划、排序

题目、示例与约束

给出一个单词数组 words ，其中每个单词都由小写英文字母组成。

如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。

• 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。

从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
 

示例 1：

输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]

示例 2:

输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

示例 3:

输入：words = ["abcd","dbqca"]
输出：1
解释：字链["abcd"]是最长的字链之一。
["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。

 

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] 仅由小写英文字母组成。

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

思考

词链要求每次只多一个字符， $n\le 1000$、串长 $\le 16$，可按长度排序后做序列 DP。以 $i$ 结尾的最长链，来自某个长度恰少 $1$ 且为前身的 $j$。

双指针判断 $a$ 能否通过插入一个字符得到 $b$。对每个 $i$ 枚举更短的 $j$，满足前身则用 $f[j]+1$ 更新 $f[i]$。

答案为 $f$ 的最大值。

我们先将 $\mathit{\text{words}}$ 按照字符串长度从小到大排序。定义 $f[i]$ 表示以 $\mathit{\text{words}}[i]$ 结尾的最长词链长度，初始时 $f[i]=1$。

对于每个 $i$，我们枚举 $j\in [0,i)$。如果 $\mathit{\text{words}}[j]$ 是 $\mathit{\text{words}}[i]$ 的前身，则更新 $f[i]=max(f[i],f[j]+1)$。判断前身时，两个字符串的长度需相差 $1$，且较短串可由较长串删除恰好一个字符得到。

答案为 $max(f)$。

时间复杂度 $O(n^2\times L)$，空间复杂度 $O(n)$。其中 $n$ 是数组长度，而 $L$ 是字符串的最大长度。

func longestStrChain(words []string) int {
	sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
	n := len(words)
	f := make([]int, n)
	ans := 0
	for i := 0; i < n; i++ {
		f[i] = 1
		for j := 0; j < i; j++ {
			if check(words[j], words[i]) {
				f[i] = max(f[i], f[j]+1)
			}
		}
		ans = max(ans, f[i])
	}
	return ans
}

func check(a, b string) bool {
	if len(a)+1 != len(b) {
		return false
	}
	i := 0
	for j := range b {
		if i < len(a) && a[i] == b[j] {
			i++
		}
	}
	return i == len(a)
}

方法二：动态规划 + 哈希表 · Go 实现

思考

方法一对每个 $i$ 扫描全部更短单词，即使长度差不是 $1$。前身由删去 $w$ 的一个字符唯一确定，至多 $L$ 个候选，可用哈希表按单词取值。

仍按长度排序，对当前 $w$ 枚举删除一位得到的 $p$，用 $f[p]+1$ 更新 $f[w]$。时间降为 $O(n{L}^2)$。

我们同样先将 $\mathit{\text{words}}$ 按长度排序。用哈希表 $f$ 记录每个单词对应的最长词链长度。

对于当前单词 $w$，枚举删除其中一个字符得到的前身 $p$。若 $p$ 已在哈希表中，则可以用 $f[p]+1$ 更新 $f[w]$。

答案为所有 $f[w]$ 的最大值。

时间复杂度 $O(n\times L^2)$，空间复杂度 $O(n\times L)$。

func longestStrChain(words []string) int {
	sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
	f := map[string]int{}
	ans := 0
	for _, w := range words {
		x := 1
		for i := range w {
			pred := w[:i] + w[i+1:]
			x = max(x, f[pred]+1)
		}
		f[w] = x
		ans = max(ans, x)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1049. 最后一块石头的重量 II

中等2 种解法

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

题目、示例与约束

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

 

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]
输出：5

 

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

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

思考

每次粉碎两块石头等价于给它们相反的符号后求和，最终剩余是把石子分成两堆后的差的绝对值。 $n\le 30$ 但总和只有几千，可转化为容量 $\lfloor s/2\rfloor$ 的 $0$-$1$ 背包：一堆尽量接近一半。

$\mathit{\text{dp}}[i][j]$ 表示前 $i$ 块能否（或最大地）凑出不超过 $j$ 的重量。转移选或不选第 $i$ 块。

答案为 $s-2\cdot \mathit{\text{dp}}[n][\lfloor s/2\rfloor ]$。

两个石头的重量越接近，粉碎后的新重量就越小。同样的，两堆石头的重量越接近，它们粉碎后的新重量也越小。

所以本题可以转换为，计算容量为 sum / 2 的背包最多能装多少重量的石头。

定义 dp[i][j] 表示从前 i 个石头中选出若干个，使得所选石头重量之和为不超过 j 的最大重量。

func lastStoneWeightII(stones []int) int {
	s := 0
	for _, v := range stones {
		s += v
	}
	m, n := len(stones), s>>1
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			dp[i][j] = dp[i-1][j]
			if stones[i-1] <= j {
				dp[i][j] = max(dp[i][j], dp[i-1][j-stones[i-1]]+stones[i-1])
			}
		}
	}
	return s - dp[m][n]*2
}

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

思考

二维表中第 $i$ 行只依赖第 $i-1$ 行。滚动到一维数组并从大到小枚举容量，即可避免同一块石头被用两次，空间降为 $O(s)$。

我们注意到 $dp[i][j]$ 只与上一行 $dp[i-1][\cdot ]$ 有关，因此可以去掉第一维，从大到小枚举容量，将空间复杂度优化到 $O(\mathit{\text{sum}})$。

func lastStoneWeightII(stones []int) int {
	s := 0
	for _, v := range stones {
		s += v
	}
	n := s >> 1
	dp := make([]int, n+1)
	for _, v := range stones {
		for j := n; j >= v; j-- {
			dp[j] = max(dp[j], dp[j-v]+v)
		}
	}
	return s - dp[n]*2
}

力扣原题 · Doocs 题解来源

1062. 最长重复子串的长度 🔒

中等1 种解法

标签：字符串、二分查找、动态规划、后缀数组、哈希函数、滚动哈希

题目、示例与约束

给你一个字符串 s，找出并返回 最长重复子串 的长度。如果不存在重复子串，返回 0。

 

示例 1：

输入：s = "abcd"
输出：0
解释：没有重复子串。

示例 2：

输入：s = "abbaba"
输出：2
解释：最长的重复子串为 "ab" 和 "ba"，每个出现 2 次。

示例 3：

输入：s = "aabcaabdaab"
输出：3
解释：最长的重复子串为 "aab"，出现 3 次。

 

提示：

• 1 <= s.length <= 2000
• 字符串 s 仅包含从 'a' 到 'z' 的小写英文字母。

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

思考

最长重复子串可用后缀数组或二分哈希， $n\le 2000$ 时 $O(n^2)$ 的 DP 更直接。以不同位置 $i>j$ 结尾的公共后缀长度，在 $s[i]=s[j]$ 时比以 $i-1,j-1$ 结尾的长度多 $1$。

令 $f[i][j]$ 为该公共后缀长，枚举 $i$ 与 $j<i$，相等则转移并更新全局最大。

答案即最大的 $f[i][j]$。

我们定义 $f[i][j]$ 表示以 $s[i]$ 和 $s[j]$ 结尾的最长重复子串的长度，初始时 $f[i][j]=0$。

我们在 $[1,n)$ 的区间内枚举 $i$，在 $[0,i)$ 的区间内枚举 $j$，如果 $s[i]=s[j]$，那么有：

$$f[i][j]=\{\begin{array}{ll}f[i-1][j-1]+1,& j>0\\ 1,& j=0\end{array}$$

我们求出所有 $f[i][j]$ 的最大值即为答案。

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

相似题目：

• 1044. 最长重复子串 🔒

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

力扣原题 · Doocs 题解来源

1066. 校园自行车分配 II 🔒

中等1 种解法

标签：位运算、数组、动态规划、回溯、位掩码、匈牙利算法、二分图、图的匹配、最小费用流、SSP 算法、网络流

题目、示例与约束

在由 2D 网格表示的校园里有 n 位工人（worker）和 m 辆自行车（bike），n <= m。所有工人和自行车的位置都用网格上的 2D 坐标表示。

我们为每一位工人分配一辆专属自行车，使每个工人与其分配到的自行车之间的 曼哈顿距离 最小化。

返回 每个工人与分配到的自行车之间的曼哈顿距离的最小可能总和 。

p1 和 p2 之间的 曼哈顿距离 为 Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。

 

示例 1：

输入：workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
输出：6
解释：
自行车 0 分配给工人 0，自行车 1 分配给工人 1 。分配得到的曼哈顿距离都是 3, 所以输出为 6 。

示例 2：

输入：workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
输出：4
解释：
先将自行车 0 分配给工人 0，再将自行车 1 分配给工人 1（或工人 2），自行车 2 给工人 2（或工人 1）。如此分配使得曼哈顿距离的总和为 4。

示例 3:

输入：workers = [[0,0],[1,0],[2,0],[3,0],[4,0]], bikes = [[0,999],[1,999],[2,999],[3,999],[4,999]]
输出：4995

 

提示：

• n == workers.length
• m == bikes.length
• 1 <= n <= m <= 10
• workers[i].length == 2
• bikes[i].length == 2
• 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
• 所有的工人和自行车的位置都是 不同 的。

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

思考

工人与自行车至多 $10$ 个，全排列分配为 $m!P(m,n)$，偏大。已分配的自行车集合可用 $m$ 位掩码表示，状态数 $n\cdot 2^m$ 可接受。

$f[i][j]$ 为前 $i$ 个工人使用集合 $j$ 的最小总距离。枚举 $j$ 中为 $1$ 的第 $k$ 辆车，从 $f[i-1][j\oplus 2^k]$ 加上这对曼哈顿距离转移。

答案为第 $n$ 行的最小值。

我们定义 $f[i][j]$ 表示前 $i$ 个工人分配到自行车的状态为 $j$ 时的最小曼哈顿距离总和，其中 $j$ 是一个二进制数，表示自行车的分配情况。初始时 $f[0][0]=0$，其余 $f[0][j]=+\mathrm{\infty }$。

考虑 $f[i][j]$，我们枚举第 $i$ 个工人分配到的自行车的编号 $k$，那么 $f[i][j]$ 可以从 $f[i-1][j\oplus 2^k]$ 转移而来，其中 $\oplus$ 表示异或运算。这是因为 $f[i-1][j\oplus 2^k]$ 表示前 $i-1$ 个工人分配到自行车的状态为 $j\oplus 2^k$ 时的最小曼哈顿距离总和，而第 $i$ 个工人分配到自行车 $k$ 时，其曼哈顿距离为 $|worker[i]-bike[k]|$，其中 $|x|$ 表示 $x$ 的绝对值。因此我们可以列出状态转移方程：

$$f[i][j]=\underset{k=0}{\overset{m-1}{min}}\{f[i-1][j\oplus 2^k]+|worker[i]-bike[k]|\}$$

最终的答案为 $\underset{j=0}{\overset{2^m-1}{min}}\{f[n][j]\}$。

时间复杂度 $O(n\times 2^m\times m)$，空间复杂度 $O(n\times 2^m)$。其中 $n$ 和 $m$ 分别是工人和自行车的数量。

func assignBikes(workers [][]int, bikes [][]int) int {
	n, m := len(workers), len(bikes)
	f := make([][]int, n+1)
	const inf = 1 << 30
	for i := range f {
		f[i] = make([]int, 1<<m)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := 0; j < 1<<m; j++ {
			for k := 0; k < m; k++ {
				if j>>k&1 == 1 {
					d := abs(workers[i-1][0]-bikes[k][0]) + abs(workers[i-1][1]-bikes[k][1])
					f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+d)
				}
			}
		}
	}
	return slices.Min(f[n])
}

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

力扣原题 · Doocs 题解来源

1067. 范围内的数字计数 🔒

困难1 种解法

标签：数学、动态规划

题目、示例与约束

给定一个在 0 到 9 之间的整数 d，和两个正整数 low 和 high 分别作为上下界。返回 d 在 low 和 high 之间的整数中出现的次数，包括边界 low 和 high。

 

示例 1：

输入：d = 1, low = 1, high = 13
输出：6
解释： 
数字 d=1 在 1,10,11,12,13 中出现 6 次。注意 d=1 在数字 11 中出现两次。

示例 2：

输入：d = 3, low = 100, high = 250
输出：35
解释：
数字 d=3 在 103,113,123,130,131,...,238,239,243 出现 35 次。

 

提示：

1. 0 <= d <= 9
2. 1 <= low <= high <= 2×10^8

方法一：数位 DP · Go 实现

思考

$[\mathit{\text{low}},\mathit{\text{high}}]$ 上统计数位 $d$ 的出现次数， $\mathit{\text{high}}\le 2\times {10}^8$，枚举每个数不可行。区间计数化为 $f(\mathit{\text{high}})-f(\mathit{\text{low}}-1)$，其中 $f(n)$ 是 $1..n$ 中 $d$ 出现的次数。

按位填写时记录已出现次数、是否仍为前导零、是否贴上界。前导零不把 $0$ 计入 $d=0$ 的次数。

把 $n$ 拆成数位数组后记忆化 $\mathit{\text{dfs}}(\mathit{\text{pos}},\mathit{\text{cnt}},\mathit{\text{lead}},\mathit{\text{limit}})$。

这道题实际上是求在给定区间 $[l,..r]$ 中，数字中出现 $d$ 的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。

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

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

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

基本步骤如下：

1. 将数字 $n$ 转为 int 数组 $a$，其中 $a[1]$ 为最低位，而 $a[len]$ 为最高位；
2. 根据题目信息，设计函数 $dfs()$，对于本题，我们定义 $dfs(pos,cnt,lead,limit)$，答案为 $dfs(len,0,true,true)$。

其中：

• pos 表示数字的位数，从末位或者第一位开始，一般根据题目的数字构造性质来选择顺序。对于本题，我们选择从高位开始，因此，pos 的初始值为 len；
• cnt 表示当前数字中包含 $d$ 的个数；
• lead 表示当前数字是否有前导零，如果有前导零，则 lead 为 true，否则为 false，初始化为 true；
• limit 表示可填的数字的限制，如果无限制，那么可以选择 $[0,1,..9]$，否则，只能选择 $[0,..a[pos]]$。如果 limit 为 true 且已经取到了能取到的最大值，那么下一个 limit 同样为 true；如果 limit 为 true 但是还没有取到最大值，或者 limit 为 false，那么下一个 limit 为 false。

关于函数的实现细节，可以参考下面的代码。

时间复杂度 $O(\log m+\log n)$。其中 $m$, $n$ 分别为题目中的 low 和 high。

相似题目：

• 233. 数字 1 的个数

func digitsCount(d int, low int, high int) int {
	f := func(n int) int {
		a := make([]int, 11)
		dp := make([][]int, 11)
		for i := range dp {
			dp[i] = make([]int, 11)
			for j := range dp[i] {
				dp[i][j] = -1
			}
		}
		l := 0
		for n > 0 {
			l++
			a[l] = n % 10
			n /= 10
		}

		var dfs func(int, int, bool, bool) int
		dfs = func(pos, cnt int, lead, limit bool) int {
			if pos <= 0 {
				return cnt
			}
			if !lead && !limit && dp[pos][cnt] != -1 {
				return dp[pos][cnt]
			}
			up := 9
			if limit {
				up = a[pos]
			}
			ans := 0
			for i := 0; i <= up; i++ {
				if i == 0 && lead {
					ans += dfs(pos-1, cnt, lead, limit && i == up)
				} else {
					t := cnt
					if d == i {
						t++
					}
					ans += dfs(pos-1, t, false, limit && i == up)
				}
			}
			if !lead && !limit {
				dp[pos][cnt] = ans
			}
			return ans
		}

		return dfs(l, 0, true, true)
	}
	return f(high) - f(low-1)
}

力扣原题 · Doocs 题解来源

1092. 最短公共超序列

困难1 种解法

标签：字符串、动态规划、最长公共子序列

题目、示例与约束

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

 

示例 1：

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

示例 2：

输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"

 

提示：

• 1 <= str1.length, str2.length <= 1000
• str1 和 str2 都由小写英文字母组成。

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

思考

最短公共超序列长度等于 $|s_1|+|s_2|-\mathrm{LCS}$。 $m,n\le 1000$，先求 LCS 表，再沿转移回溯把非公共字符按序插入。

$f[i][j]$ 为两前缀的 LCS 长。从 $(m,n)$ 往回走：若来自上方或左方则输出被丢掉的那个字符；否则输出公共字符并对角后退。

路径是逆序收集的，最后反转。某一侧耗尽时把另一侧剩余字符全部接上。

我们先用动态规划求出两个字符串的最长公共子序列，然后根据最长公共子序列构造出最短公共超序列。

定义 $f[i][j]$ 表示字符串 $str1$ 的前 $i$ 个字符和字符串 $str2$ 的前 $j$ 个字符的最长公共子序列的长度。状态转移方程如下：

$$f[i][j]=\{\begin{array}{ll}0& i=0\mathit{\text{ or }}j=0\\ f[i-1][j-1]+1& str1[i-1]=str2[j-1]\\ max(f[i-1][j],f[i][j-1])& str1[i-1]\ne str2[j-1]\end{array}$$

接下来我们基于 $f[i][j]$ 构造出最短公共超序列。

str1:       a   b   a   c

str2:   c   a   b

ans:    c   a   b   a   c

不妨对照着上面的示例字符串，来看看如何构造出最短公共超序列。

我们用双指针 $i$ 和 $j$ 分别指向字符串 $str1$ 和 $str2$ 的末尾，然后从后往前遍历，每次比较 $str1[i]$ 和 $str2[j]$ 的值：

• 如果 $str1[i]=str2[j]$，则将 $str1[i]$ 或 $str2[j]$ 中的任意一个字符加入到最答案序列的末尾，然后 $i$ 和 $j$ 同时减 $1$；
• 如果 $str1[i]\ne str2[j]$，则将 $f[i][j]$ 与 $f[i-1][j]$ 和 $f[i][j-1]$ 中的最大值进行比较：
  • 如果 $f[i][j]=f[i-1][j]$，则将 $str1[i]$ 加入到答案序列的末尾，然后 $i$ 减 $1$；
  • 如果 $f[i][j]=f[i][j-1]$，则将 $str2[j]$ 加入到答案序列的末尾，然后 $j$ 减 $1$。

重复上述操作，直到 $i=0$ 或 $j=0$，然后将剩余的字符串加入到答案序列的末尾即可。

最后我们将答案序列反转，即可得到最终的答案。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是字符串 $str1$ 和 $str2$ 的长度。

func shortestCommonSupersequence(str1 string, str2 string) string {
	m, n := len(str1), len(str2)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if str1[i-1] == str2[j-1] {
				f[i][j] = f[i-1][j-1] + 1
			} else {
				f[i][j] = max(f[i-1][j], f[i][j-1])
			}
		}
	}
	ans := []byte{}
	i, j := m, n
	for i > 0 || j > 0 {
		if i == 0 {
			j--
			ans = append(ans, str2[j])
		} else if j == 0 {
			i--
			ans = append(ans, str1[i])
		} else {
			if f[i][j] == f[i-1][j] {
				i--
				ans = append(ans, str1[i])
			} else if f[i][j] == f[i][j-1] {
				j--
				ans = append(ans, str2[j])
			} else {
				i, j = i-1, j-1
				ans = append(ans, str1[i])
			}
		}
	}
	for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1105. 填充书架

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。

按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。

• 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。

每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

 

示例 1：

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。

示例 2:

输入: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
输出: 4

 

提示：

• 1 <= books.length <= 1000
• 1 <= thicknessi <= shelfWidth <= 1000
• 1 <= heighti <= 1000

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

思考

每本书可单独开一层，或与前面若干本同层，决策随层划分指数增长。 $n\le 1000$，可用 $O(n^2)$ 动态规划。

令 $f[i]$ 为摆放前 $i$ 本书的最小总高度。最后一层以 $books[i-1]$ 结尾，自后向前扩张同层书籍并累加宽度，一旦超过 $shelfWidth$ 即可停止；层高取这些书的最大高度，再接上 $f[j-1]$。从后往前枚举同时保证宽度单调增加。

我们定义 $f[i]$ 表示前 $i$ 本书摆放的最小高度，初始时 $f[0]=0$，答案为 $f[n]$。

考虑 $f[i]$，最后一本书为 $books[i-1]$，其厚度为 $w$，高度为 $h$。

• 如果这本书单独摆放在新的一层，那么有 $f[i]=f[i-1]+h$；
• 如果这本书可以与前面的最后几本书摆放在同一层，我们从后往前枚举同一层的第一本书 $boos[j-1]$，其中 $j\in [1,i-1]$，将书的厚度累积到 $w$，如果 $w>shelfWidth$，说明此时的 $books[j-1]$ 已经无法与 $books[i-1]$ 摆放在同一层，停止枚举；否则我们更新当前层的最大高度 $h=max(h,books[j-1][1])$，那么此时有 $f[i]=min(f[i],f[j-1]+h)$。

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

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

func minHeightShelves(books [][]int, shelfWidth int) int {
	n := len(books)
	f := make([]int, n+1)
	for i := 1; i <= n; i++ {
		w, h := books[i-1][0], books[i-1][1]
		f[i] = f[i-1] + h
		for j := i - 1; j > 0; j-- {
			w += books[j-1][0]
			if w > shelfWidth {
				break
			}
			h = max(h, books[j-1][1])
			f[i] = min(f[i], f[j-1]+h)
		}
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

1125. 最小的必要团队

困难1 种解法

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

题目、示例与约束

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

• 例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。

请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

 

示例 1：

输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]

示例 2：

输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
输出：[1,2]

 

提示：

• 1 <= req_skills.length <= 16
• 1 <= req_skills[i].length <= 16
• req_skills[i] 由小写英文字母组成
• req_skills 中的所有字符串 互不相同
• 1 <= people.length <= 60
• 0 <= people[i].length <= 16
• 1 <= people[i][j].length <= 16
• people[i][j] 由小写英文字母组成
• people[i] 中的所有字符串 互不相同
• people[i] 中的每个技能是 req_skills 中的技能
• 题目数据保证「必要团队」一定存在

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

思考

技能种数 $m\le 16$，子集可用 $2^m$ 个状态表示；对人的组合枚举则达 $2^n$。把每人掌握的技能压成掩码 $p[j]$，令 $f[i]$ 为覆盖技能集合 $i$ 的最少人数。

对每个已达状态 $i$ 尝试加入第 $j$ 人，转移到 $i\mid p[j]$。另用 $g,h$ 记下最后加入的人与上一状态，从全集沿指针回溯即可还原下标列表。

我们注意到，技能清单 req_skills 的长度不超过 $16$，因此，我们可以用一个长度不超过 $16$ 的二进制数来表示每一种技能是否被掌握。不妨记数组 req_skills 的长度为 $m$，数组 people 的长度为 $n$。

我们先将 req_skills 中的每个技能映射到一个编号，即 $d[s]$ 表示技能 $s$ 的编号。然后，我们遍历 people 中的每个人，将其掌握的技能用二进制数表示，即 $p[i]$ 表示编号为 $i$ 的人掌握的技能。

接下来，我们定义以下三个数组，其中：

• 数组 $f[i]$ 表示掌握技能集合为 $i$ 的最少人数，其中 $i$ 的二进制表示中的每一位为 $1$ 的位置，表示对应的技能被掌握。初始时 $f[0]=0$，其余位置均为无穷大。
• 数组 $g[i]$ 表示掌握技能集合为 $i$ 的最少人数时，最后一个人的编号。
• 数组 $h[i]$ 表示掌握技能集合为 $i$ 的最少人数时，上一个技能集合状态。

我们在 $[0,.{.2}^m-1]$ 的范围内枚举每个技能集合，对于每个技能集合 $i$：

我们枚举 people 中的每个人 $j$，如果 $f[i]+1<f[i|p[j]]$，说明 $f[i|p[j]]$ 可以通过 $f[i]$ 转移得到，此时，我们更新 $f[i|p[j]]$ 为 $f[i]+1$，并将 $g[i|p[j]]$ 更新为 $j$，同时将 $h[i|p[j]]$ 更新为 $i$。即当前技能集合状态为 $i|p[j]$ 时，最后一个人的编号为 $j$，上一个技能集合状态为 $i$。这里符号 $|$ 表示按位或运算。

最后，我们从技能集合 $i=2^m-1$ 开始，找到此时最后一个人的编号 $g[i]$，将其加入答案中，然后将 $i$ 更新为 $h[i]$，不断地向前回溯，直到 $i=0$，即可得到最小的必要团队中的人员编号。

时间复杂度 $O(2^m\times n)$，空间复杂度 $O(2^m)$。其中 $m$ 和 $n$ 分别为 req_skills 和 people 的长度。

func smallestSufficientTeam(req_skills []string, people [][]string) (ans []int) {
	d := map[string]int{}
	for i, s := range req_skills {
		d[s] = i
	}
	m, n := len(req_skills), len(people)
	p := make([]int, n)
	for i, ss := range people {
		for _, s := range ss {
			p[i] |= 1 << d[s]
		}
	}
	const inf = 1 << 30
	f := make([]int, 1<<m)
	g := make([]int, 1<<m)
	h := make([]int, 1<<m)
	for i := range f {
		f[i] = inf
	}
	f[0] = 0
	for i := range f {
		if f[i] == inf {
			continue
		}
		for j := 0; j < n; j++ {
			if f[i]+1 < f[i|p[j]] {
				f[i|p[j]] = f[i] + 1
				g[i|p[j]] = j
				h[i|p[j]] = i
			}
		}
	}
	for i := 1<<m - 1; i != 0; i = h[i] {
		ans = append(ans, g[i])
	}
	return
}

力扣原题 · Doocs 题解来源

1130. 叶值的最小代价生成树

中等2 种解法

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

题目、示例与约束

给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：

• 每个节点都有 0 个或是 2 个子节点。
• 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。
• 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。

在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。

如果一个节点有 0 个子节点，那么该节点为叶节点。

 

示例 1：

输入：arr = [6,2,4]
输出：32
解释：有两种可能的树，第一种的非叶节点的总和为 36 ，第二种非叶节点的总和为 32 。 

示例 2：

输入：arr = [4,11]
输出：44

 

提示：

• 2 <= arr.length <= 40
• 1 <= arr[i] <= 15
• 答案保证是一个 32 位带符号整数，即小于 231 。

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

思考

中序叶序列固定，树形由切分位置决定。枚举所有切分的递归若不记忆会重复计算同一区间。

$dfs(i,j)$ 返回区间 $[i,j]$ 的最小非叶代价与叶最大值；枚举切点 $k$，左右代价加上两侧叶最大值之积。区间数 $O(n^2)$、切点 $O(n)$，记忆化后为 $O(n^3)$。

根据题目描述，数组 $arr$ 中的值与树的中序遍历中每个叶节点的值一一对应，我们可以将数组划分为左右两个非空子数组，分别对应树的左右子树，递归地求解每个子树的所有非叶节点的值的最小可能总和。

我们设计一个函数 $dfs(i,j)$，表示数组 $arr$ 中下标范围 $[i,j]$ 内的所有非叶节点的值的最小可能总和，那么答案就是 $dfs(0,n-1)$，其中 $n$ 为数组 $arr$ 的长度。

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

• 如果 $i=j$，说明数组 $arr[i..j]$ 中只有一个元素，没有非叶节点，因此 $dfs(i,j)=0$。
• 否则，我们枚举 $k\in [i,j-1]$，将数组 $arr$ 划分为两个子数组 $arr[i\cdots k]$ 和 $arr[k+1\cdots j]$，对于每个 $k$，我们递归计算 $dfs(i,k)$ 和 $dfs(k+1,j)$，其中 $dfs(i,k)$ 表示数组 $arr$ 中下标范围 $[i,k]$ 内的所有非叶节点的值的最小可能总和，而 $dfs(k+1,j)$ 表示数组 $arr$ 中下标范围 $[k+1,j]$ 内的所有非叶节点的值的最小可能总和，那么 $dfs(i,j)=\underset{i\le k<j}{min}\{dfs(i,k)+dfs(k+1,j)+\underset{i\le t\le k}{max}\{arr[t]\}\underset{k<t\le j}{max}\{arr[t]\}\}$。

综上所述，我们可以得到：

$$dfs(i,j)=\{\begin{array}{ll}0,& \mathit{\text{if }}i=j\\ \underset{i\le k<j}{min}\{dfs(i,k)+dfs(k+1,j)+\underset{i\le t\le k}{max}\{arr[t]\}\underset{k<t\le j}{max}\{arr[t]\}\},& \mathit{\text{if }}i<j\end{array}$$

上述递归过程中，我们可以使用记忆化搜索的方法，避免重复计算。另外，我们还可以使用数组 $g$ 记录数组 $arr$ 中下标范围 $[i,j]$ 内的所有叶节点的最大值，那么 $dfs(i,j)$ 的计算过程可以优化为：

$$dfs(i,j)=\{\begin{array}{ll}0,& \mathit{\text{if }}i=j\\ \underset{i\le k<j}{min}\{dfs(i,k)+dfs(k+1,j)+g[i][k]\cdot g[k+1][j]\},& \mathit{\text{if }}i<j\end{array}$$

最后，我们返回 $dfs(0,n-1)$ 即可。

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

func mctFromLeafValues(arr []int) int {
	n := len(arr)
	f := make([][]int, n)
	g := make([][]int, n)
	for i := range g {
		f[i] = make([]int, n)
		g[i] = make([]int, n)
		g[i][i] = arr[i]
		for j := i + 1; j < n; j++ {
			g[i][j] = max(g[i][j-1], arr[j])
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i == j {
			return 0
		}
		if f[i][j] > 0 {
			return f[i][j]
		}
		f[i][j] = 1 << 30
		for k := i; k < j; k++ {
			f[i][j] = min(f[i][j], dfs(i, k)+dfs(k+1, j)+g[i][k]*g[k+1][j])
		}
		return f[i][j]
	}
	return dfs(0, n-1)
}

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

思考

方法一的递归栈与哈希缓存可改成区间 DP。先预处理 $g[i][j]$ 为区间最大叶，再按区间长度递推 $f[i][j]$，转移式与记忆化相同，避免递归开销。

我们可以将方法一中的记忆化搜索改为动态规划的方式进行求解。

定义 $f[i][j]$ 表示数组 $arr$ 中下标范围 $[i,j]$ 内的所有非叶节点的值的最小可能总和，而 $g[i][j]$ 表示数组 $arr$ 中下标范围 $[i,j]$ 内的所有叶节点的最大值，那么状态转移方程为：

$$f[i][j]=\{\begin{array}{ll}0,& \mathit{\text{if }}i=j\\ \underset{i\le k<j}{min}\{f[i][k]+f[k+1][j]+g[i][k]\cdot g[k+1][j]\},& \mathit{\text{if }}i<j\end{array}$$

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

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

func mctFromLeafValues(arr []int) int {
	n := len(arr)
	f := make([][]int, n)
	g := make([][]int, n)
	for i := range g {
		f[i] = make([]int, n)
		g[i] = make([]int, n)
	}
	for i := n - 1; i >= 0; i-- {
		g[i][i] = arr[i]
		for j := i + 1; j < n; j++ {
			g[i][j] = max(g[i][j-1], arr[j])
			f[i][j] = 1 << 30
			for k := i; k < j; k++ {
				f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+g[i][k]*g[k+1][j])
			}
		}
	}
	return f[0][n-1]
}

力扣原题 · Doocs 题解来源

1137. 第 N 个泰波那契数

简单2 种解法

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

题目、示例与约束

泰波那契序列 T_n 定义如下： 

T₀ = 0, T₁ = 1, T₂ = 1, 且在 n >= 0 的条件下 T_n+3 = T_n + T_n+1 + T_n+2

给你整数 n，请返回第 n 个泰波那契数 T_n 的值。

 

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

 

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

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

思考

泰波那契由三项递推定义， $n\le 37$ 时线性递推足够。用三个变量滚动保存最近三项，循环 $n$ 次后返回第一项，空间为常数。

根据题目中给出的递推式，我们可以使用动态规划求解。

我们定义三个变量 $a$, $b$, $c$，分别表示 $T_{n-3}$, $T_{n-2}$, $T_{n-1}$，初始值分别为 $0$, $1$, $1$。

然后从 $n$ 减小到 $0$，每次更新 $a$, $b$, $c$ 的值，直到 $n$ 为 $0$ 时，答案即为 $a$。

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

func tribonacci(n int) int {
	a, b, c := 0, 1, 1
	for i := 0; i < n; i++ {
		a, b, c = b, c, a+b+c
	}
	return a
}

方法二：矩阵快速幂加速递推 · Go 实现

思考

方法一为 $O(n)$。将递推写成 $1\times 3$ 状态乘 $3\times 3$ 转移矩阵后，可用快速幂在 $O(\log n)$ 次矩阵乘法得到 $T_n$，适合 $n$ 更大的情形。

我们设 $Tib(n)$ 表示一个 $1\times 3$ 的矩阵 $\left[\begin{array}{ccc}{T}_n& T_{n-1}& T_{n-2}\end{array}\right]$，其中 $T_n$, $T_{n-1}$ 和 $T_{n-2}$ 分别表示第 $n$ 个、第 $n-1$ 个和第 $n-2$ 个泰波那契数。

我们希望根据 $Tib(n-1)=\left[\begin{array}{ccc}{T}_{n-1}& T_{n-2}& T_{n-3}\end{array}\right]$ 推出 $Tib(n)$。也即是说，我们需要一个矩阵 $base$，使得 $Tib(n-1)\times base=Tib(n)$，即：

$$\left[\begin{array}{ccc}{T}_{n-1}& T_{n-2}& T_{n-3}\end{array}\right]\times base=\left[\begin{array}{ccc}{T}_n& T_{n-1}& T_{n-2}\end{array}\right]$$

由于 $T_n=T_{n-1}+T_{n-2}+T_{n-3}$，所以矩阵 $base$ 为：

$$\left[\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\end{array}\right]$$

我们定义初始矩阵 $res=\left[\begin{array}{ccc}1& 1& 0\end{array}\right]$，那么 $T_n$ 等于 $res$ 乘以 $bas{e}^{n-3}$ 的结果矩阵中所有元素之和。使用矩阵快速幂求解即可。

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

func tribonacci(n int) (ans int) {
	if n == 0 {
		return 0
	}
	if n < 3 {
		return 1
	}
	a := [][]int{{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}
	res := pow(a, n-3)
	for _, x := range res[0] {
		ans += x
	}
	return
}

func mul(a, b [][]int) [][]int {
	m, n := len(a), len(b[0])
	c := make([][]int, m)
	for i := range c {
		c[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < len(b); k++ {
				c[i][j] += a[i][k] * b[k][j]
			}
		}
	}
	return c
}

func pow(a [][]int, n int) [][]int {
	res := [][]int{{1, 1, 0}}
	for n > 0 {
		if n&1 == 1 {
			res = mul(res, a)
		}
		a = mul(a, a)
		n >>= 1
	}
	return res
}

力扣原题 · Doocs 题解来源

1139. 最大的以 1 为边界的正方形

中等1 种解法

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

题目、示例与约束

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] 为 0 或 1

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

思考

判断边长为 $k$ 的正方形四边是否全为 $1$，若每次再扫边则立方之上还要乘 $k$。从每个格子预处理向下、向右连续 $1$ 的长度后，四条边是否够长均可 $O(1)$ 判定。

从大到小枚举 $k$ 再枚举左上角，第一次成立即得最大面积，避免继续检查更小正方形。

我们可以使用前缀和的方法预处理出每个位置向下和向右的连续 $1$ 的个数，记为 down[i][j] 和 right[i][j]。

然后我们枚举正方形的边长 $k$，从最大的边长开始枚举，然后枚举正方形的左上角位置 $(i,j)$，如果满足条件，即可返回 $k^2$。

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

func largest1BorderedSquare(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	down := make([][]int, m)
	right := make([][]int, m)
	for i := range down {
		down[i] = make([]int, n)
		right[i] = make([]int, n)
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if grid[i][j] == 1 {
				down[i][j], right[i][j] = 1, 1
				if i+1 < m {
					down[i][j] += down[i+1][j]
				}
				if j+1 < n {
					right[i][j] += right[i][j+1]
				}
			}
		}
	}
	for k := min(m, n); k > 0; k-- {
		for i := 0; i <= m-k; i++ {
			for j := 0; j <= n-k; j++ {
				if down[i][j] >= k && right[i][j] >= k && right[i+k-1][j] >= k && down[i][j+k-1] >= k {
					return k * k
				}
			}
		}
	}
	return 0
}

力扣原题 · Doocs 题解来源

1140. 石子游戏 II

中等1 种解法

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

题目、示例与约束

Alice 和 Bob 继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

Alice 和 Bob 轮流进行，Alice 先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设 Alice 和 Bob 都发挥出最佳水平，返回 Alice 可以得到的最大数量的石头。

 

示例 1：

输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始 Alice 取了一堆，Bob 取了两堆，然后 Alice 再取两堆。Alice 可以得到 2 + 4 + 4 = 10 堆。
如果 Alice 一开始拿走了两堆，那么 Bob 可以拿走剩下的三堆。在这种情况下，Alice 得到 2 + 7 = 9 堆。返回 10，因为它更大。

示例 2:

输入：piles = [1,2,3,4,5,100]
输出：104

 

提示：

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

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

思考

双方轮流从剩余前缀取 $1..2M$ 堆，状态为起点下标与当前 $M$。直接搜索重复子问题很多。前缀和给出「从 $i$ 到末尾的石子总和」，当前人得到的是该总和减去对手在新状态的最优。

若 $2M$ 已覆盖剩余堆，则一次取完；否则枚举取堆数并记忆化。爱丽丝从 $(0,1)$ 出发。

由于玩家每次可以拿走前 $X$ 堆的所有石子，也就是说能拿走一个区间的石子，因此，我们可以先预处理出一个长度为 $n+1$ 的前缀和数组 $s$，其中 $s[i]$ 表示数组 piles 的前 $i$ 个元素的和。

然后我们设计一个函数 $dfs(i,m)$，表示当前轮到的人可以从数组 piles 的下标 $i$ 开始拿，且当前的 $M$ 为 $m$ 时，当前轮到的人能够拿到的最大石子数。初始时爱丽丝从下标 $0$ 开始，且 $M=1$，所以我们需要求的答案为 $dfs(0,1)$。

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

• 如果当前轮到的人可以拿走剩下的所有石子，能够拿到的最大石子数为 $s[n]-s[i]$；
• 否则，当前轮到的人可以拿走剩下的前 $x$ 堆的所有石子，其中 $1\le x\le 2m$，能够拿到的最大石子数为 $s[n]-s[i]-dfs(i+x,max(m,x))$。也即是说，当前轮的人能够拿到的石子数为当前剩下的所有石子数减去下一轮对手能够拿到的石子数。我们需要枚举所有的 $x$，取其中的最大值作为函数 $dfs(i,m)$ 的返回值。

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

最后，我们返回将 $dfs(0,1)$ 作为答案返回即可。

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

func stoneGameII(piles []int) int {
	n := len(piles)
	s := make([]int, n+1)
	f := make([][]int, n+1)
	for i, x := range piles {
		s[i+1] = s[i] + x
		f[i] = make([]int, n+1)
	}
	var dfs func(i, m int) int
	dfs = func(i, m int) int {
		if m*2 >= n-i {
			return s[n] - s[i]
		}
		if f[i][m] > 0 {
			return f[i][m]
		}
		f[i][m] = 0
		for x := 1; x <= m<<1; x++ {
			f[i][m] = max(f[i][m], s[n]-s[i]-dfs(i+x, max(m, x)))
		}
		return f[i][m]
	}
	return dfs(0, 1)
}

力扣原题 · Doocs 题解来源

1143. 最长公共子序列

中等1 种解法

标签：字符串、动态规划、最长公共子序列

题目、示例与约束

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

 

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

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

思考

公共子序列不必连续，枚举所有子序列再匹配代价过高。 $f[i][j]$ 表示两串前缀的 LCS 长度：末字符相同则由 $f[i-1][j-1]$ 加一，否则取少用一侧字符的较大值。按前缀长度递推，每个格子只依赖更短前缀。

我们定义 $f[i][j]$ 表示 $text1$ 的前 $i$ 个字符和 $text2$ 的前 $j$ 个字符的最长公共子序列的长度。那么答案为 $f[m][n]$，其中 $m$ 和 $n$ 分别为 $text1$ 和 $text2$ 的长度。

如果 $text1$ 的第 $i$ 个字符和 $text2$ 的第 $j$ 个字符相同，则 $f[i][j]=f[i-1][j-1]+1$；如果 $text1$ 的第 $i$ 个字符和 $text2$ 的第 $j$ 个字符不同，则 $f[i][j]=max(f[i-1][j],f[i][j-1])$。即状态转移方程为：

$$f[i][j]=\{\begin{array}{ll}f[i-1][j-1]+1,& text1[i-1]=text2[j-1]\\ max(f[i-1][j],f[i][j-1]),& text1[i-1]\ne text2[j-1]\end{array}$$

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

func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				f[i][j] = f[i-1][j-1] + 1
			} else {
				f[i][j] = max(f[i-1][j], f[i][j-1])
			}
		}
	}
	return f[m][n]
}

力扣原题 · Doocs 题解来源

1147. 段式回文

困难2 种解法

标签：贪心、双指针、字符串、动态规划、哈希函数、滚动哈希

题目、示例与约束

你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:

• subtexti 是 非空 字符串
• 所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text )
• 对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立

返回k可能最大值。

 

示例 1：

输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2：

输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

示例 3：

输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)"。

 

提示：

• 1 <= text.length <= 1000
• text 仅由小写英文字符组成

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

思考

段式回文要求左右段文字相等。为使段数最多，应尽量切出最短的一对相等前后缀：更长的一对总可以再拆。双指针从两端增长长度 $k$，一旦 text[i:i+k] 与右端对应串相等就切下并各进 $2$，中间剩一段则再加 $1$。

我们可以从字符串的两端开始，寻找长度最短的、相同且不重叠的前后缀：

• 如果找不到这样的前后缀，那么整个字符串作为一个段式回文，答案加 $1$；
• 如果找到了这样的前后缀，那么这个前后缀作为一个段式回文，答案加 $2$，然后继续寻找剩下的字符串的前后缀。

以上贪心策略的证明如下：

假设有一个前后缀 $A_1$ 和 $A_2$ 满足条件，又有一个前后缀 $B_1$ 和 $B_4$ 满足条件，由于 $A_1=A_2$，且 $B_1=B_4$，那么有 $B_3=B_1=B_4=B_2$，并且 $C_1=C_2$，因此，如果我们贪心地将 $B_1$ 和 $B_4$ 分割出来，那么剩下的 $C_1$ 和 $C_2$，以及 $B_2$ 和 $B_3$ 也能成功分割。因此我们应该贪心地选择长度最短的相同前后缀进行分割，这样剩余的字符串中，将可能分割出更多的段式回文串。

<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1100-1199/1147.Longest Chunked Palindrome Decomposition/images/demo.png&quot; style="width: 300px;" /></p>

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

func longestDecomposition(text string) (ans int) {
	for i, j := 0, len(text)-1; i <= j; {
		ok := false
		for k := 1; i+k-1 < j-k+1; k++ {
			if text[i:i+k] == text[j-k+1:j+1] {
				ans += 2
				i += k
				j -= k
				ok = true
				break
			}
		}
		if !ok {
			ans++
			break
		}
	}
	return
}

方法二：字符串哈希 · Go 实现

思考

方法一每次用切片比较，最坏 $O(n^2)$。预计算前缀哈希后，等长子串的相等性可 $O(1)$ 判定，贪心切分策略不变，比较不再扫字符。

字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 $0$。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。

因此，在方法一的基础上，我们可以使用字符串哈希的方法，在 $O(1)$ 时间内比较两个字符串是否相等。

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

func longestDecomposition(text string) (ans int) {
	n := len(text)
	base := 131
	h := make([]int, n+10)
	p := make([]int, n+10)
	p[0] = 1
	for i, c := range text {
		t := int(c-'a') + 1
		p[i+1] = p[i] * base
		h[i+1] = h[i]*base + t
	}
	get := func(l, r int) int {
		return h[r] - h[l-1]*p[r-l+1]
	}

	for i, j := 0, n-1; i <= j; {
		ok := false
		for k := 1; i+k-1 < j-k+1; k++ {
			if get(i+1, i+k) == get(j-k+2, j+1) {
				ans += 2
				i += k
				j -= k
				ok = true
				break
			}
		}
		if !ok {
			ans++
			break
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1155. 掷骰子等于目标和的方法数

中等2 种解法

标签：动态规划

题目、示例与约束

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kn 种方式），使得骰子面朝上的数字总和等于 target。

由于答案可能很大，你需要对 109 + 7 取模。

 

示例 1：

输入：n = 1, k = 6, target = 3
输出：1
解释：你掷了一个有 6 个面的骰子。
得到总和为 3 的结果的方式只有一种。

示例 2：

输入：n = 2, k = 6, target = 7
输出：6
解释：你掷了两个骰子，每个骰子有 6 个面。
有 6 种方式得到总和为 7 的结果: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1。

示例 3：

输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须对 109 + 7 取模。

 

提示：

• 1 <= n, k <= 30
• 1 <= target <= 1000

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

思考

$n$ 个 $k$ 面骰子组成 $target$，枚举每个骰子朝向为 $k^n$。令 $f[i][j]$ 为 $i$ 个骰子组成 $j$ 的方案数，第 $i$ 个骰子点数 $h$ 时由 $f[i-1][j-h]$ 转移。空骰子组成 $0$ 为 $1$ 种，取模防止溢出。

我们定义 $f[i][j]$ 表示使用 $i$ 个骰子，和为 $j$ 的方案数。那么我们可以得到状态转移方程：

$$f[i][j]=\sum _{h=1}^{min(j,k)}f[i-1][j-h]$$

其中 $h$ 表示第 $i$ 个骰子的点数。

初始时 $f[0][0]=1$，最终的答案即为 $f[n][target]$。

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

func numRollsToTarget(n int, k int, target int) int {
	const mod int = 1e9 + 7
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, target+1)
	}
	f[0][0] = 1
	for i := 1; i <= n; i++ {
		for j := 1; j <= min(target, i*k); j++ {
			for h := 1; h <= min(j, k); h++ {
				f[i][j] = (f[i][j] + f[i-1][j-h]) % mod
			}
		}
	}
	return f[n][target]
}

方法二：动态规划（滚动数组） · Go 实现

思考

方法一的 $f[i]$ 只依赖 $f[i-1]$。用两个一维数组滚动，空间从 $O(n\times target)$ 降为 $O(target)$，转移不变。

$f[i][j]$ 只与上一行有关，用两个一维数组 $f$、 $g$ 滚动即可，空间复杂度降为 $O(target)$。

func numRollsToTarget(n int, k int, target int) int {
	const mod int = 1e9 + 7
	f := make([]int, target+1)
	f[0] = 1
	for i := 1; i <= n; i++ {
		g := make([]int, target+1)
		for j := 1; j <= min(target, i*k); j++ {
			for h := 1; h <= min(j, k); h++ {
				g[j] = (g[j] + f[j-h]) % mod
			}
		}
		f = g
	}
	return f[target]
}

力扣原题 · Doocs 题解来源

1162. 地图分析

中等1 种解法

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

题目、示例与约束

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

 

示例 1：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

 

提示：

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

方法一：BFS · Go 实现

思考

所求是海洋格到最近陆地的距离的最大值。对每个海洋分别 BFS 会重复访问。把全部陆地同时入队做多源 BFS，每扩散一层距离加一，最后一层海洋被染上的步数即最远距。全是陆地或全是海洋时不存在答案，返回 $-1$。

我们可以将所有陆地单元格加入队列 $q$ 中，如果队列为空，或者队列中元素个数等于网格中的单元格个数，则说明网格中只有陆地或者海洋，返回 $-1$。

否则，我们从陆地单元格开始进行广度优先搜索。定义初始步数 $ans=-1$。

在每一轮搜索中，我们将队列中的所有单元格向四个方向扩散，若单元格是海洋单元格，则将其标记为陆地单元格，并加入队列。在一轮扩散完成后，我们将步数加 $1$。重复这一过程，直到队列为空。

最后，我们返回步数 $ans$。

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

func maxDistance(grid [][]int) int {
	n := len(grid)
	q := [][2]int{}
	for i, row := range grid {
		for j, v := range row {
			if v == 1 {
				q = append(q, [2]int{i, j})
			}
		}
	}
	ans := -1
	if len(q) == 0 || len(q) == n*n {
		return ans
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		for i := len(q); i > 0; i-- {
			p := q[0]
			q = q[1:]
			for k := 0; k < 4; k++ {
				x, y := p[0]+dirs[k], p[1]+dirs[k+1]
				if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 {
					grid[x][y] = 1
					q = append(q, [2]int{x, y})
				}
			}
		}
		ans++
	}
	return ans
}

力扣原题 · Doocs 题解来源