LeetCode Go · 动态规划（7）

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

来源与许可

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

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

1182. 与目标颜色间的最短距离 🔒

中等1 种解法

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

题目、示例与约束

给你一个数组 colors，里面有  1、2、 3 三种颜色。

我们需要在 colors 上进行一些查询操作 queries，其中每个待查项都由两个整数 i 和 c 组成。

现在请你帮忙设计一个算法，查找从索引 i 到具有目标颜色 c 的元素之间的最短距离。

如果不存在解决方案，请返回 -1。

 

示例 1：

输入：colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
输出：[3,0,3]
解释： 
距离索引 1 最近的颜色 3 位于索引 4（距离为 3）。
距离索引 2 最近的颜色 2 就是它自己（距离为 0）。
距离索引 6 最近的颜色 1 位于索引 3（距离为 3）。

示例 2：

输入：colors = [1,2], queries = [[0,3]]
输出：[-1]
解释：colors 中没有颜色 3。

 

提示：

• 1 <= colors.length <= 5*10^4
• 1 <= colors[i] <= 3
• 1 <= queries.length <= 5*10^4
• queries[i].length == 2
• 0 <= queries[i][0] < colors.length
• 1 <= queries[i][1] <= 3

方法一：预处理 · Go 实现

思考

每次查询若从 $i$ 向两侧找颜色 $c$，总时间与查询次数、数组长度之积成正比。颜色只有三种，可预处理每个位置左侧、右侧最近的 $1/2/3$ 下标，查询时取两侧距离的较小值；哨兵 $\pm \mathrm{\infty }$ 使缺失颜色自然大于 $n$。

我们可以预处理出每个位置到左边最近的颜色 $1$,$2$,$3$ 的距离，以及每个位置到右边最近的颜色 $1$,$2$,$3$ 的距离，记录在数组 $left$ 和 $right$ 中。初始时 $left[0][0]=left[0][1]=left[0][2]=-\mathrm{\infty }$，而 $right[n][0]=right[n][1]=right[n][2]=\mathrm{\infty }$，其中 $n$ 是数组 $colors$ 的长度。

然后对于每个查询 $(i,c)$，最小距离就是 $d=min(i-left[i+1][c-1],right[i][c-1][i]-i)$，如果 $d>n$，则不存在解决方案，此次查询的答案为 $-1$。

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

func shortestDistanceColor(colors []int, queries [][]int) (ans []int) {
	n := len(colors)
	const inf = 1 << 30
	right := make([][3]int, n+1)
	left := make([][3]int, n+1)
	right[n] = [3]int{inf, inf, inf}
	left[0] = [3]int{-inf, -inf, -inf}
	for i := n - 1; i >= 0; i-- {
		for j := 0; j < 3; j++ {
			right[i][j] = right[i+1][j]
		}
		right[i][colors[i]-1] = i
	}
	for i := 1; i <= n; i++ {
		for j := 0; j < 3; j++ {
			left[i][j] = left[i-1][j]
		}
		left[i][colors[i-1]-1] = i - 1
	}
	for _, q := range queries {
		i, c := q[0], q[1]-1
		d := min(i-left[i+1][c], right[i][c]-i)
		if d > n {
			d = -1
		}
		ans = append(ans, d)
	}
	return
}

力扣原题 · Doocs 题解来源

1186. 删除一次得到子数组最大和

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组 不能为空。

 

示例 1：

输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。

示例 2：

输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。

示例 3：

输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

 

提示：

• 1 <= arr.length <= 105
• -104 <= arr[i] <= 104

方法一：预处理 + 枚举 · Go 实现

思考

子数组至多删一个元素。Kadane 给出以某端为界的最大子段和；不删时答案即这些值的最大。删 $arr[i]$ 时，左侧以 $i-1$ 结尾的最大段与右侧以 $i+1$ 开头的最大段相加。两端预处理 $left$、 $right$ 后枚举删除点即可，两端元素无法作为「中间删除」。

我们可以先预处理出数组 $\mathit{\text{arr}}$ 以每个元素结尾和开头的最大子数组和，分别存入数组 $\mathit{\text{left}}$ 和 $\mathit{\text{right}}$ 中。

如果我们不删除任何元素，那么最大子数组和就是 $\mathit{\text{left}}[i]$ 或 $\mathit{\text{right}}[i]$ 中的最大值；如果我们删除一个元素，我们可以枚举 $[1..n-2]$ 中的每个位置 $i$，计算 $\mathit{\text{left}}[i-1]+\mathit{\text{right}}[i+1]$ 的值，取最大值即可。

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

func maximumSum(arr []int) int {
	n := len(arr)
	left := make([]int, n)
	right := make([]int, n)
	for i, s := 0, 0; i < n; i++ {
		s = max(s, 0) + arr[i]
		left[i] = s
	}
	for i, s := n-1, 0; i >= 0; i-- {
		s = max(s, 0) + arr[i]
		right[i] = s
	}
	ans := slices.Max(left)
	for i := 1; i < n-1; i++ {
		ans = max(ans, left[i-1]+right[i+1])
	}
	return ans
}

力扣原题 · Doocs 题解来源

1187. 使数组严格递增

困难1 种解法

标签：数组、二分查找、动态规划、排序、最长上升子序列

题目、示例与约束

给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

如果无法让 arr1 严格递增，请返回 -1。

 

示例 1：

输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

示例 2：

输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。

示例 3：

输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。

 

提示：

• 1 <= arr1.length, arr2.length <= 2000
• 0 <= arr1[i], arr2[i] <= 10^9

 

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

思考

每次替换须使用 $arr2$ 中的值，求最少替换次数。对 $arr1$ 每个位置枚举替换值代价过高。令 $f[i]$ 为前缀变为严格递增且位置 $i$ 不替换的最少次数；若需把 $i$ 前连续 $k$ 个位置换成 $arr2$ 中恰小于 $arr[i]$ 的 $k$ 个数，则由 $f[i-k-1]+k$ 转移。 $arr2$ 排序去重后可用二分定位，首尾哨兵保证最后一位不替换。

我们定义 $f[i]$ 表示将 $arr1[0,..,i]$ 转换为严格递增数组，且 $arr1[i]$ 不替换的最小操作数。因此，我们在 $arr1$ 设置首尾两个哨兵 $-\mathrm{\infty }$ 和 $\mathrm{\infty }$。最后一个数一定是不替换，因此 $f[n-1]$ 即为答案。我们初始化 $f[0]=0$，其余 $f[i]=\mathrm{\infty }$。

接下来我们对数组 $arr2$ 进行排序并去重，方便进行二分查找。

对于 $i=1,..,n-1$，我们考虑 $arr1[i-1]$ 是否替换。如果 $arr1[i-1]<arr1[i]$，那么 $f[i]$ 可以从 $f[i-1]$ 转移而来，即 $f[i]=f[i-1]$。然后，我们考虑 $arr[i-1]$ 替换的情况，显然 $arr[i-1]$ 应该替换成一个尽可能大的、且比 $arr[i]$ 小的数字，我们在数组 $arr2$ 中进行二分查找，找到第一个大于等于 $arr[i]$ 的下标 $j$。然后我们在 $k\in [1,min(i-1,j)]$ 的范围内枚举替换的个数，如果满足 $arr[i-k-1]<arr2[j-k]$，那么 $f[i]$ 可以从 $f[i-k-1]$ 转移而来，即 $f[i]=min(f[i],f[i-k-1]+k)$。

最后，如果 $f[n-1]\ge \mathrm{\infty }$，说明无法转换为严格递增数组，返回 $-1$，否则返回 $f[n-1]$。

时间复杂度 $O(n\times (\log m+min(m,n)))$，空间复杂度 $O(n)$。其中 $n$ 为 $arr1$ 的长度。

func makeArrayIncreasing(arr1 []int, arr2 []int) int {
	sort.Ints(arr2)
	m := 0
	for _, x := range arr2 {
		if m == 0 || x != arr2[m-1] {
			arr2[m] = x
			m++
		}
	}
	arr2 = arr2[:m]
	const inf = 1 << 30
	arr1 = append([]int{-inf}, arr1...)
	arr1 = append(arr1, inf)
	n := len(arr1)
	f := make([]int, n)
	for i := range f {
		f[i] = inf
	}
	f[0] = 0
	for i := 1; i < n; i++ {
		if arr1[i-1] < arr1[i] {
			f[i] = f[i-1]
		}
		j := sort.SearchInts(arr2, arr1[i])
		for k := 1; k <= min(i-1, j); k++ {
			if arr1[i-k-1] < arr2[j-k] {
				f[i] = min(f[i], f[i-k-1]+k)
			}
		}
	}
	if f[n-1] >= inf {
		return -1
	}
	return f[n-1]
}

力扣原题 · Doocs 题解来源

1191. K 次串联后最大子数组之和

中等1 种解法

标签：数组、动态规划

题目、示例与约束

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回结果对 109 + 7 取 模。

 

示例 1：

输入：arr = [1,2], k = 3
输出：9

示例 2：

输入：arr = [1,-2,1], k = 5
输出：2

示例 3：

输入：arr = [-1,-2], k = 7
输出：0

 

提示：

• 1 <= arr.length <= 105
• 1 <= k <= 105
• -104 <= arr[i] <= 104

方法一：前缀和 + 分类讨论 · Go 实现

思考

数组重复 $k$ 次后的最大子段和，子段至多跨过整段重复。先在单份上做 Kadane 得 $mxSub$，并记录最大前缀、最小前缀（从而得最大后缀）。 $k=1$ 时即为 $mxSub$；否则还可取「前缀+后缀」，若总和为正还可再加中间 $k-2$ 个整段。 $k$ 可达 ${10}^5$，不能真正拼接。

我们记数组 $arr$ 所有元素之和为 $s$，最大前缀和为 $mxPre$，最小前缀和为 $miPre$，最大子数组和为 $mxSub$。

遍历数组 $arr$，对于每个元素 $x$，我们更新 $s=s+x$, $mxPre=max(mxPre,s)$, $miPre=min(miPre,s)$, $mxSub=max(mxSub,s-miPre)$。

接下来，我们考虑 $k$ 的取值情况：

• 当 $k=1$ 时，答案为 $mxSub$。
• 当 $k\ge 2$ 时，如果最大子数组横跨两个 $arr$，那么答案为 $mxPre+mxSuf$，其中 $mxSuf=s-miPre$。
• 当 $k\ge 2$ 且 $s>0$ 时，如果最大子数组横跨三个 $arr$，那么答案为 $(k-2)\times s+mxPre+mxSuf$。

最后，我们返回答案对 ${10}^9+7$ 取模的结果。

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

func kConcatenationMaxSum(arr []int, k int) int {
	var s, mxPre, miPre, mxSub int
	for _, x := range arr {
		s += x
		mxPre = max(mxPre, s)
		miPre = min(miPre, s)
		mxSub = max(mxSub, s-miPre)
	}
	const mod = 1e9 + 7
	ans := mxSub
	if k == 1 {
		return ans % mod
	}
	mxSuf := s - miPre
	ans = max(ans, mxSuf+mxPre)
	if s > 0 {
		ans = max(ans, mxSuf+(k-2)*s+mxPre)
	}
	return ans % mod
}

力扣原题 · Doocs 题解来源

1216. 验证回文串 III 🔒

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给出一个字符串 s 和一个整数 k，若这个字符串是一个「k 回文 」，则返回 true 。

如果可以通过从字符串中删去最多 k 个字符将其转换为回文，那么这个字符串就是一个「k 回文 」。

 

示例 1：

输入：s = "abcdeca", k = 2
输出：true
解释：删去字符 “b” 和 “e”。

示例 2:

输入：s = "abbababa", k = 1
输出：true

 

提示：

• 1 <= s.length <= 1000
• s 中只含有小写英文字母
• 1 <= k <= s.length

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

思考

枚举删除哪 $k$ 个字符后再判回文， $n\le 1000$ 时组合数过大。删至多 $k$ 个后能成回文，等价于最长回文子序列长度至少为 $n-k$。

区间 DP： $f[i][j]$ 为 $s[i..j]$ 的 LPS。两端相等则内缩加 $2$，否则取去掉一端后的较大值。一旦 $f[i][j]+k\ge n$ 即可提前返回。

按区间长度从短到长（实现上外层 $i$ 递减）填表，使转移所需的更短区间已经算完。

题目要求删去最多 $k$ 个字符，使得剩余的字符串是回文串。可以转换为求最长回文子序列的问题。

我们定义 $f[i][j]$ 表示字符串 $s$ 中下标范围 $[i,j]$ 内的最长回文子序列的长度。初始时 $f[i][i]=1$，即每个单独的字符都是一个回文子序列。

当 $s[i]=s[j]$ 时，有 $f[i][j]=f[i+1][j-1]+2$，即去掉 $s[i]$ 和 $s[j]$ 后，剩余的字符串的最长回文子序列长度加 $2$。

当 $s[i]\ne s[j]$ 时，有 $f[i][j]=max(f[i+1][j],f[i][j-1])$，即去掉 $s[i]$ 或 $s[j]$ 后，剩余的字符串的最长回文子序列长度。

然后是否存在 $f[i][j]+k\ge n$，如果存在，说明可以通过删去 $k$ 个字符，使得剩余的字符串是回文串。

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

func isValidPalindrome(s string, k int) bool {
	n := len(s)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		f[i][i] = 1
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				f[i][j] = f[i+1][j-1] + 2
			} else {
				f[i][j] = max(f[i+1][j], f[i][j-1])
			}
			if f[i][j]+k >= n {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

1218. 最长定差子序列

中等1 种解法

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

题目、示例与约束

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

 

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

 

提示：

• 1 <= arr.length <= 105
• -104 <= arr[i], difference <= 104

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

思考

子序列需保持原相对顺序且公差固定为 $difference$。 $n\le {10}^5$，枚举子集不可行。以 $x$ 结尾的最长长度只依赖以 $x-difference$ 结尾的长度，且该前驱若存在必已在此前出现。

从左到右扫描，令 $f[x]=f[x-difference]+1$。哈希表按值索引前驱，一遍得到所有结尾处的最长长度，取最大即可。

我们可以使用哈希表 $f$ 来存储以 $x$ 结尾的最长等差子序列的长度。

遍历数组 $\mathit{\text{arr}}$，对于每个元素 $x$，我们更新 $f[x]$ 为 $f[x-\mathit{\text{difference}}]+1$。

遍历结束后，我们返回 $f$ 中的最大值作为答案返回即可。

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

func longestSubsequence(arr []int, difference int) (ans int) {
	f := map[int]int{}
	for _, x := range arr {
		f[x] = f[x-difference] + 1
		ans = max(ans, f[x])
	}
	return
}

力扣原题 · Doocs 题解来源

1220. 统计元音字母序列的数目

困难2 种解法

标签：动态规划

题目、示例与约束

给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

• 字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
• 每个元音 'a' 后面都只能跟着 'e'
• 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
• 每个元音 'i' 后面 不能 再跟着另一个 'i'
• 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
• 每个元音 'u' 后面只能跟着 'a'

由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

 

示例 1：

输入：n = 1
输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。

示例 2：

输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。

示例 3：

输入：n = 5
输出：68

 

提示：

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

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

思考

长度为 $n$ 的元音串须满足邻接规则， $n$ 达 $2\times {10}^4$，不能逐串枚举。只须记录以各元音结尾的方案数：下一字母的合法前驱是固定的五种转移。

用长度为 $5$ 的数组 $f$ 表示当前长度下各结尾的个数，按前驱关系滚到下一长度，共 $n-1$ 轮。状态只依赖上一长度，模 ${10}^9+7$ 防止溢出。

根据题目描述，我们先列出每个元音字母的后一个字母：

a [e]
e [a|i]
i [a|e|o|u]
o [i|u]
u [a]

那么我们可以推出每个元音字母的前一个字母：

[e|i|u]	a
[a|i]	e
[e|o]	i
[i]	o
[i|o]	u

我们定义 $f[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数，如果长度为 $1$，那么 $f[i]=1$。

当长度大于 $1$ 时，我们定义 $g[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数，那么 $g[i]$ 可以由 $f$ 转移而来，即：

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

最终答案为 $\sum _{i=0}^{4}f[i]$。注意由于答案可能会很大，所以需要对 ${10}^9+7$ 取模。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是字符串的长度，而 $C$ 是元音字母的个数。本题中 $C=5$。

func countVowelPermutation(n int) (ans int) {
	const mod int = 1e9 + 7
	f := make([]int, 5)
	for i := range f {
		f[i] = 1
	}
	for i := 1; i < n; i++ {
		g := make([]int, 5)
		g[0] = (f[1] + f[2] + f[4]) % mod
		g[1] = (f[0] + f[2]) % mod
		g[2] = (f[1] + f[3]) % mod
		g[3] = f[2] % mod
		g[4] = (f[2] + f[3]) % mod
		f = g
	}
	for _, x := range f {
		ans = (ans + x) % mod
	}
	return
}

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

思考

方法一按长度递推需 $O(n)$ 次常数量更新。五种状态的转移是常系数线性关系，写成 $5\times 5$ 矩阵后可用快速幂在 $O(\log n)$ 次矩阵乘法内得到第 $n$ 项，当 $n$ 更大时更有利。

时间复杂度 $O(C^3\times \log n)$，空间复杂度 $O(C^2)$，其中 $C$ 是元音字母的个数，本题中 $C=5$。

const mod = 1e9 + 7

func countVowelPermutation(n int) (ans int) {
	a := [][]int{
		{0, 1, 0, 0, 0},
		{1, 0, 1, 0, 0},
		{1, 1, 0, 1, 1},
		{0, 0, 1, 0, 1},
		{1, 0, 0, 0, 0}}
	res := pow(a, n-1)
	for _, x := range res[0] {
		ans = (ans + x) % mod
	}
	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] = (c[i][j] + a[i][k]*b[k][j]) % mod
			}
		}
	}
	return c
}

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

力扣原题 · Doocs 题解来源

1223. 掷骰子模拟

困难3 种解法

标签：数组、动态规划

题目、示例与约束

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。

现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。

 

示例 1：

输入：n = 2, rollMax = [1,1,2,2,2,3]
输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。

示例 2：

输入：n = 2, rollMax = [1,1,1,1,1,1]
输出：30

示例 3：

输入：n = 3, rollMax = [1,1,1,2,2,3]
输出：181

 

提示：

• 1 <= n <= 5000
• rollMax.length == 6
• 1 <= rollMax[i] <= 15

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

思考

连续同一点数受 $rollMax$ 限制， $n$ 达 $5000$，直接枚举序列不可行。方案数只依赖「还剩几次、上次点数、该点已连续几次」。

记忆化 $dfs(i,j,x)$：第 $i$ 次起、上一次为 $j$ 且已连续 $x$ 次。枚举下一点 $k$，不同则重置连续次数，相同则须 $x$ 仍低于上限。初态 $(0,0,0)$ 表示尚未掷出。

状态 $O(n\times 6\times 15)$，转移枚举 $6$ 个点数，记忆化避免重复子问题。

我们可以设计一个函数 $dfs(i,j,x)$ 表示从第 $i$ 次掷骰子开始，当前掷出的点数为 $j$，且连续掷出 $j$ 的次数为 $x$ 的方案数。其中 $j$ 的取值范围为 $[1,6]$，而 $x$ 的取值范围为 $[1,rollMax[j-1]]$。那么答案就是 $dfs(0,0,0)$。

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

• 如果 $i\ge n$，说明已经掷完了 $n$ 次骰子，返回 $1$。
• 否则，我们枚举下一次掷出的点数 $k$，如果 $k\ne j$，那么我们可以直接掷出 $k$，此时连续掷出 $j$ 的次数 $x$ 就会被重置为 $1$，因此方案数为 $dfs(i+1,k,1)$。如果 $k=j$，那么我们需要判断 $x$ 是否小于 $rollMax[j-1]$，如果小于，那么我们可以继续掷出 $j$，此时连续掷出 $j$ 的次数 $x$ 就会加 $1$，因此方案数为 $dfs(i+1,j,x+1)$。最后将所有方案数相加，即为 $dfs(i,j,x)$ 的值。注意答案可能很大，因此需要对 ${10}^9+7$ 取模。

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

时间复杂度 $O(n\times k^2\times M)$，空间复杂度 $O(n\times k\times M)$。其中 $k$ 为点数的取值范围，而 $M$ 为连续掷出某个点数的最大次数。

func dieSimulator(n int, rollMax []int) int {
	f := make([][7][16]int, n)
	const mod = 1e9 + 7
	var dfs func(i, j, x int) int
	dfs = func(i, j, x int) int {
		if i >= n {
			return 1
		}
		if f[i][j][x] != 0 {
			return f[i][j][x]
		}
		ans := 0
		for k := 1; k <= 6; k++ {
			if k != j {
				ans += dfs(i+1, k, 1)
			} else if x < rollMax[j-1] {
				ans += dfs(i+1, j, x+1)
			}
		}
		f[i][j][x] = ans % mod
		return f[i][j][x]
	}
	return dfs(0, 0, 0)
}

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

思考

方法一已经从最后一次投掷往回填好后缀方案数。同一组选择也可以记成前缀： $f[i][j][x]$ 是掷完前 $i$ 次、结尾为 $j$ 且连续 $x$ 次的方案数，由第 $i-1$ 层按相同规则累加。

方法一已经按后缀填好同一组转移。下面把方案数改记成前 $i$ 次投掷的前缀。

定义 $f[i][j][x]$ 表示投掷前 $i$ 次骰子，且第 $i$ 次投掷的点数为 $j$，且连续投掷点数 $j$ 的次数为 $x$ 的方案数。初始时 $f[1][j][1]=1$，其中 $1\le j\le 6$。答案即是：

$$\sum _{j=1}^6\sum _{x=1}^{rollMax[j-1]}f[n][j][x]$$

我们枚举上一次投掷的点数为 $j$，且连续投掷点数 $j$ 的次数为 $x$，那么当前投掷的点数可以为 $1,2,\cdots ,6$，如果当前投掷的点数为 $k$，那么有如下两种情况：

• 如果 $k\ne j$，那么我们可以直接投掷出 $k$，此时连续投掷点数 $j$ 的次数 $x$ 就会被重置为 $1$，因此方案数 $f[i][k][1]$ 就会增加 $f[i-1][j][x]$。
• 如果 $k=j$，那么我们需要判断 $x+1$ 是否小于等于 $rollMax[j-1]$，如果小于等于，那么我们可以继续投掷出 $j$，此时连续投掷点数 $j$ 的次数 $x$ 就会加 $1$，因此方案数 $f[i][j][x+1]$ 就会增加 $f[i-1][j][x]$。

最终的答案即为所有 $f[n][j][x]$ 的和。

时间复杂度 $O(n\times k^2\times M)$，空间复杂度 $O(n\times k\times M)$。其中 $k$ 为点数的取值范围，而 $M$ 为连续掷出某个点数的最大次数。

func dieSimulator(n int, rollMax []int) (ans int) {
	f := make([][7][16]int, n+1)
	for j := 1; j <= 6; j++ {
		f[1][j][1] = 1
	}
	const mod = 1e9 + 7
	for i := 2; i <= n; i++ {
		for j := 1; j <= 6; j++ {
			for x := 1; x <= rollMax[j-1]; x++ {
				for k := 1; k <= 6; k++ {
					if k != j {
						f[i][k][1] = (f[i][k][1] + f[i-1][j][x]) % mod
					} else if x+1 <= rollMax[j-1] {
						f[i][j][x+1] = (f[i][j][x+1] + f[i-1][j][x]) % mod
					}
				}
			}
		}
	}
	for j := 1; j <= 6; j++ {
		for x := 1; x <= rollMax[j-1]; x++ {
			ans = (ans + f[n][j][x]) % mod
		}
	}
	return
}

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

思考

连续同一点数受 $rollMax$ 限制， $n$ 达 $5000$，直接枚举序列不可行。方案数只依赖还剩几次、上次点数和该点已连续几次。

下一次点数无论是换面还是续面，读到的都是下一次投掷。从第 $0$ 次走到第 $n$ 次，调用链长度就是 $n$。 $n=2000$ 时 Python 抛出 RecursionError， $n=5000$ 时 Java 栈溢出。

因此从最后一次投掷往回填。 $f[i][j][x]$ 是从第 $i$ 次起、上一次为 $j$ 且已连续 $x$ 次的方案数。 $f[n][\cdot ][\cdot ]=1$。换面进入 $(k,1)$，续面则要求 $x$ 仍低于上限并进入 $(j,x+1)$。

定义 $f[i][j][x]$ 表示从第 $i$ 次掷骰子开始，上一次掷出的点数为 $j$，且该点数已经连续出现 $x$ 次时，完成剩余投掷的方案数。 $j=0$ 表示还没有掷出过。答案是 $f[0][0][0]$。

先令 $f[n][j][x]=1$，表示 $n$ 次已经掷完。按 $i$ 从 $n-1$ 降到 $0$ 填写。枚举下一次的点数 $k$：

• 若 $k\ne j$，可以掷出 $k$，连续次数重置为 $1$，方案数加上 $f[i+1][k][1]$。
• 若 $k=j$ 且 $x<rollMax[j-1]$，可以继续掷出 $j$，连续次数变为 $x+1$，方案数加上 $f[i+1][j][x+1]$。

把这些方案数相加，对 ${10}^9+7$ 取模，得到 $f[i][j][x]$。

时间复杂度 $O(n\times k^2\times M)$，空间复杂度 $O(n\times k\times M)$。其中 $k$ 为点数的取值范围，而 $M$ 为连续掷出某个点数的最大次数。

func dieSimulator(n int, rollMax []int) int {
	const mod = 1e9 + 7
	f := make([][7][16]int, n+1)
	for j := 0; j < 7; j++ {
		for x := 0; x < 16; x++ {
			f[n][j][x] = 1
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := 0; j < 7; j++ {
			for x := 0; x < 16; x++ {
				ans := 0
				for k := 1; k <= 6; k++ {
					if k != j {
						ans += f[i+1][k][1]
					} else if x < rollMax[j-1] {
						ans += f[i+1][j][x+1]
					}
				}
				f[i][j][x] = ans % mod
			}
		}
	}
	return f[0][0][0]
}

力扣原题 · Doocs 题解来源

1227. 飞机座位分配概率

中等1 种解法

标签：脑筋急转弯、数学、动态规划、概率与统计

题目、示例与约束

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

• 如果他们自己的座位还空着，就坐到自己的座位上，

• 当他们自己的座位被占用时，随机选择其他座位

第 n 位乘客坐在自己的座位上的概率是多少？

 

示例 1：

输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：

输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

 

提示：

• 1 <= n <= 10^5

方法一：数学 · Go 实现

思考

$n$ 达 ${10}^5$，不能模拟每位乘客的随机选择。第 $n$ 位能坐到自己座位的概率满足：一人时为 $1$，此后乘客 $1$ 要么坐对、要么坐到 $n$ 的位子、要么坐到某位中间乘客的位子并把问题缩成规模更小的同构实例。

该递推化简后， $n\ge 2$ 时概率恒为 $1/2$。因此直接按 $n$ 是否为 $1$ 返回 $1$ 或 $0.5$，无需迭代。

用 $f(n)$ 表示当有 $n$ 位乘客登机时，第 $n$ 位乘客坐在自己的座位上的概率。从最简单的情况开始考虑：

当 $n=1$ 时，只有 $1$ 位乘客和 $1$ 个座位，因此第 $1$ 位乘客只能坐在第 $1$ 个座位上， $f(1)=1$；

当 $n=2$ 时，有 $2$ 个座位，每个座位有 $0.5$ 的概率被第 $1$ 位乘客选中，当第 $1$ 位乘客选中座位之后，第 $2$ 位乘客只能选择剩下的座位，因此第 $2$ 位乘客有 $0.5$ 的概率坐在自己的座位上， $f(2)=0.5$。

当 $n>2$ 时，如何计算 $f(n)$ 的值？考虑第 $1$ 位乘客选择的座位，有以下三种情况。

• 第 $1$ 位乘客有 $\frac{1}{n}$ 的概率选择第 $1$ 个座位，则所有乘客都可以坐在自己的座位上，此时第 $n$ 位乘客坐在自己的座位上的概率是 $1.0$。

• 第 $1$ 位乘客有 $\frac{1}{n}$ 的概率选择第 $n$ 个座位，则第 $2$ 位乘客到第 $n-1$ 位乘客都可以坐在自己的座位上，第 $n$ 位乘客只能坐在第 $1$ 个座位上，此时第 $n$ 位乘客坐在自己的座位上的概率是 $0.0$。

• 第 $1$ 位乘客有 $\frac{n-2}{n}$ 的概率选择其余的座位，每个座位被选中的概率是 $\frac{1}{n}$。 假设第 $1$ 位乘客选择第 $i$ 个座位，其中 $2\le i\le n-1$，则第 $2$ 位乘客到第 $i-1$ 位乘客都可以坐在自己的座位上，第 $i$ 位乘客到第 $n$ 位乘客的座位不确定，第 $i$ 位乘客会在剩下的 $n-(i-1)=n-i+1$ 个座位中随机选择（包括第 $1$ 个座位和第 $i+1$ 个座位到第 $n$ 个座位）。由于此时剩下的乘客数和座位数都是 $n-i+1$，有 $1$ 位乘客会随机选择座位，因此问题规模从 $n$ 减小至 $n-i+1$。

结合上述三种情况，可以得到 $f(n)$ 的递推式：

$$\begin{array}{rl}f(n)& =\frac{1}{n}\times 1.0+\frac{1}{n}\times 0.0+\frac{1}{n}\times \sum _{i=2}^{n-1}f(n-i+1)\\ & =\frac{1}{n}(1.0+\sum _{i=2}^{n-1}f(n-i+1))\end{array}$$

上述递推式中， $i$ 的取值个数有 $n-2$ 个，由于 $i$ 的取值个数必须是非负整数，因此只有当 $n-2\ge 0$ 即 $n\ge 2$ 时，上述递推式才成立。

如果直接利用上述递推式计算 $f(n)$ 的值，则时间复杂度为 $O(n^2)$，无法通过全部测试用例，因此需要优化。

将上述递推式中的 $n$ 换成 $n-1$，可以得到递推式：

$$f(n-1)=\frac{1}{n-1}(1.0+\sum _{i=2}^{n-2}f(n-i))$$

上述递推式中， $i$ 的取值个数有 $n-3$ 个，只有当 $n-3\ge 0$ 即 $n\ge 3$ 时，上述递推式才成立。

当 $n\ge 3$ 时，上述两个递推式可以写成如下形式：

$$\begin{array}{rl}n\times f(n)& =1.0+\sum _{i=2}^{n-1}f(n-i+1)\\ (n-1)\times f(n-1)& =1.0+\sum _{i=2}^{n-2}f(n-i)\end{array}$$

将上述两式相减：

$$\begin{array}{rl}& n\times f(n)-(n-1)\times f(n-1)\\ & =(1.0+\sum _{i=2}^{n-1}f(n-i+1))-(1.0+\sum _{i=2}^{n-2}f(n-i))\\ & =\sum _{i=2}^{n-1}f(n-i+1)-\sum _{i=2}^{n-2}f(n-i)\\ & =f(2)+f(3)+...+f(n-1)-(f(2)+f(3)+...+f(n-2))\\ & =f(n-1)\end{array}$$

整理后得到简化的递推式：

$$\begin{array}{rl}n\times f(n)& =n\times f(n-1)\\ f(n)& =f(n-1)\end{array}$$

由于已知 $f(1)=1$ 和 $f(2)=0.5$，因此当 $n\ge 3$ 时，根据 $f(n)=f(n-1)$ 可知，对任意正整数 $n$ 都有 $f(n)=0.5$。又由于 $f(2)=0.5$，因此当 $n\ge 2$ 时，对任意正整数 $n$ 都有 $f(n)=0.5$。

由此可以得到 $f(n)$ 的结果：

$$f(n)=\{\begin{array}{ll}1.0,& n=1\\ 0.5,& n\ge 2\end{array}$$

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

func nthPersonGetsNthSeat(n int) float64 {
	if n == 1 {
		return 1
	}
	return .5
}

力扣原题 · Doocs 题解来源

1230. 抛掷硬币 🔒

中等2 种解法

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

题目、示例与约束

有一些不规则的硬币。在这些硬币中，prob[i] 表示第 i 枚硬币正面朝上的概率。

请对每一枚硬币抛掷 一次，然后返回正面朝上的硬币数等于 target 的概率。

 

示例 1：

输入：prob = [0.4], target = 1
输出：0.40000

示例 2：

输入：prob = [0.5,0.5,0.5,0.5,0.5], target = 0
输出：0.03125

 

提示：

• 1 <= prob.length <= 1000
• 0 <= prob[i] <= 1
• 0 <= target <= prob.length
• 如果答案与标准答案的误差在 10^-5 内，则被视为正确答案。

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

思考

每枚硬币正面概率不同，求恰好 $target$ 枚朝上的概率。 $n\le 1000$，枚举子集不可行。前 $i$ 枚中恰有 $j$ 枚朝上的概率只依赖前 $i-1$ 枚：第 $i$ 枚反面则 $j$ 不变，正面则由 $j-1$ 转移。

令 $f[i][j]$ 为该概率，初值 $f[0][0]=1$，按硬币顺序填表，答案为 $f[n][target]$。二维表把独立试验的卷积展开成线性递推。

我们定义 $f[i][j]$ 表示前 $i$ 枚硬币中有 $j$ 枚正面朝上的概率，初始时 $f[0][0]=1$，答案即为 $f[n][target]$。

考虑 $f[i][j]$，其中 $i\ge 1$，如果当前硬币反面朝上，那么 $f[i][j]=(1-p)\times f[i-1][j]$；如果当前硬币正面朝上，并且 $j>0$，那么 $f[i][j]=p\times f[i-1][j-1]$。因此状态转移方程为：

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

其中 $p$ 表示第 $i$ 枚硬币正面朝上的概率。

时间复杂度 $O(n\times target)$，空间复杂度 $O(n\times target)$。其中 $n$ 为硬币的数量。

func probabilityOfHeads(prob []float64, target int) float64 {
	n := len(prob)
	f := make([][]float64, n+1)
	for i := range f {
		f[i] = make([]float64, target+1)
	}
	f[0][0] = 1
	for i := 1; i <= n; i++ {
		for j := 0; j <= i && j <= target; j++ {
			f[i][j] = (1 - prob[i-1]) * f[i-1][j]
			if j > 0 {
				f[i][j] += prob[i-1] * f[i-1][j-1]
			}
		}
	}
	return f[n][target]
}

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

思考

方法一的 $f[i][\cdot ]$ 只读上一行。用一维数组并从大到小更新 $j$，避免新值覆盖尚未使用的 $f[j-1]$，空间降为 $O(target)$，转移不变。

$f[i][j]$ 只与上一行有关。内层对 $j$ 从大到小更新，空间复杂度降为 $O(target)$。

func probabilityOfHeads(prob []float64, target int) float64 {
	f := make([]float64, target+1)
	f[0] = 1
	for _, p := range prob {
		for j := target; j >= 0; j-- {
			f[j] *= (1 - p)
			if j > 0 {
				f[j] += p * f[j-1]
			}
		}
	}
	return f[target]
}

力扣原题 · Doocs 题解来源

1235. 规划兼职工作

困难3 种解法

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

题目、示例与约束

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

 

示例 1：

输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：
我们选出第 1 份和第 4 份工作， 
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。

示例 2：

输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输出：150
解释：
我们选择第 1，4，5 份工作。 
共获得报酬 150 = 20 + 70 + 60。

示例 3：

输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
输出：6

 

提示：

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

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

思考

工作区间不可重叠， $n\le 5\times {10}^4$，按时间枚举子集不可行。做到第 $i$ 份与否只影响其后开始时间不早于其结束时间的工作。

按开始时间排序后， $dfs(i)$ 在「跳过 $i$」与「做 $i$ 再跳到第一份 $start\ge en{d}_i$ 的工作」之间取大。后者的下标用二分在有序开始时间上查找。记忆化使每个 $i$ 只算一次。

我们先将工作按照开始时间从小到大排序，然后设计一个函数 $dfs(i)$ 表示从第 $i$ 份工作开始，可以获得的最大报酬。答案即为 $dfs(0)$。

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

对于第 $i$ 份工作，我们可以选择做，也可以选择不做。如果不做，最大报酬就是 $dfs(i+1)$；如果做，我们可以通过二分查找，找到在第 $i$ 份工作结束时间之后开始的第一份工作，记为 $j$，那么最大报酬就是 $profit[i]+dfs(j)$。取两者的较大值即可。即：

$$dfs(i)=max(dfs(i+1),profit[i]+dfs(j))$$

其中 $j$ 是满足 $startTime[j]\ge endTime[i]$ 的最小的下标。

此过程中，我们可以使用记忆化搜索，将每个状态的答案保存下来，避免重复计算。

时间复杂度 $O(n\times \log n)$，其中 $n$ 是工作的数量。

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(profit)
	type tuple struct{ s, e, p int }
	jobs := make([]tuple, n)
	for i, p := range profit {
		jobs[i] = tuple{startTime[i], endTime[i], p}
	}
	sort.Slice(jobs, func(i, j int) bool { return jobs[i].s < jobs[j].s })
	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]
		}
		j := sort.Search(n, func(j int) bool { return jobs[j].s >= jobs[i].e })
		ans := max(dfs(i+1), jobs[i].p+dfs(j))
		f[i] = ans
		return ans
	}
	return dfs(0)
}

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

思考

方法一按开始时间排序，并从末尾填一张后缀表。这里改按结束时间排序， $dp[i]$ 表示前 $i$ 份工作的最优报酬：不做则继承 $dp[i-1]$，做则加上在其开始前结束的最后一份工作的 $dp[j]$， $j$ 仍由二分得到。

方法一按开始时间排序并从末尾填表。这里改按结束时间排序，定义前缀表。

先将工作排序，这次我们按照结束时间从小到大排序，然后定义 $dp[i]$，表示前 $i$ 份工作中，可以获得的最大报酬。答案即为 $dp[n]$。初始化 $dp[0]=0$。

对于第 $i$ 份工作，我们可以选择做，也可以选择不做。如果不做，最大报酬就是 $dp[i]$；如果做，我们可以通过二分查找，找到在第 $i$ 份工作开始时间之前结束的最后一份工作，记为 $j$，那么最大报酬就是 $profit[i]+dp[j]$。取两者的较大值即可。即：

$$dp[i+1]=max(dp[i],profit[i]+dp[j])$$

其中 $j$ 是满足 $endTime[j]\le startTime[i]$ 的最大的下标。

时间复杂度 $O(n\times \log n)$，其中 $n$ 是工作的数量。

相似题目：

• 2008. 出租车的最大盈利
• 1751. 最多可以参加的会议数目 II

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(profit)
	type tuple struct{ s, e, p int }
	jobs := make([]tuple, n)
	for i, p := range profit {
		jobs[i] = tuple{startTime[i], endTime[i], p}
	}
	sort.Slice(jobs, func(i, j int) bool { return jobs[i].e < jobs[j].e })
	dp := make([]int, n+1)
	for i, job := range jobs {
		j := sort.Search(i, func(k int) bool { return jobs[k].e > job.s })
		dp[i+1] = max(dp[i], dp[j]+job.p)
	}
	return dp[n]
}

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

思考

工作区间不可重叠， $n\le 5\times {10}^4$，按时间枚举子集不可行。做到第 $i$ 份与否只影响其后开始时间不早于其结束时间的工作。

按开始时间排序后，跳过当前工作会先调用 $i+1$ 再返回，调用链长度为 $n$，栈会溢出。

更靠后的下标在从末尾往前走时已经就绪。令 $f[i]$ 为从第 $i$ 份工作开始的最大报酬， $f[n]=0$，填表时二分下一份相容工作，从 $i=n-1$ 填到 $0$。

我们先将工作按照开始时间从小到大排序。令 $f[i]$ 表示从第 $i$ 份工作开始可以获得的最大报酬，答案为 $f[0]$，且 $f[n]=0$。

我们从 $i=n-1$ 填到 $0$。对于第 $i$ 份工作，不做则报酬为 $f[i+1]$；做则通过二分查找找到在其结束时间之后开始的第一份工作 $j$，报酬为 $profit[i]+f[j]$。取两者的较大值：

$$f[i]=max(f[i+1],profit[i]+f[j])$$

其中 $j$ 是满足 $startTime[j]\ge endTime[i]$ 的最小下标。因为 $j>i$， $f[j]$ 已经算过。

时间复杂度 $O(n\times \log n)$，其中 $n$ 是工作的数量。

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(profit)
	type tuple struct{ s, e, p int }
	jobs := make([]tuple, n)
	for i, p := range profit {
		jobs[i] = tuple{startTime[i], endTime[i], p}
	}
	sort.Slice(jobs, func(i, j int) bool { return jobs[i].s < jobs[j].s })
	f := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		j := sort.Search(n, func(k int) bool { return jobs[k].s >= jobs[i].e })
		f[i] = max(f[i+1], jobs[i].p+f[j])
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

1246. 删除回文子数组 🔒

困难1 种解法

标签：数组、动态规划

题目、示例与约束

给你一个整数数组 arr，每一次操作你都可以选择并删除它的一个 回文 子数组 arr[i], arr[i+1], ..., arr[j]（ i <= j）。

注意，每当你删除掉一个子数组，右侧元素都会自行向前移动填补空位。

请你计算并返回从数组中删除所有数字所需的最少操作次数。

 

示例 1：

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

示例 2：

输入：arr = [1,3,4,1,5]
输出：3
解释：先删除 [4]，然后删除 [1,3,1]，最后再删除 [5]。

 

提示：

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 20

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

思考

每次可删一段回文， $n\le 100$，求最少次数。区间删除的最优子结构适合区间 DP： $f[i][j]$ 为清空 $arr[i..j]$ 的最少次数。

两端相等时可与内区间一并删掉；否则枚举拆点 $k$，把区间拆成两段分别删除。按区间长度填表，使更短区间先算完。 $n^3$ 在 $100$ 下可接受。

我们定义 $f[i][j]$ 表示删除下标区间 $[i,..j]$ 内的所有数字所需的最少操作次数。初始时 $f[i][i]=1$，表示只有一个数字时，需要执行一次删除操作。

对于 $f[i][j]$，如果 $i+1=j$，即只有两个数字时，如果 $arr[i]=arr[j]$，则 $f[i][j]=1$，否则 $f[i][j]=2$。

对于超过两个数字的情况，如果 $arr[i]=arr[j]$，那么 $f[i][j]$ 可以取 $f[i+1][j-1]$，或者我们可以在下标范围 $[i,..j-1]$ 范围内枚举 $k$，取 $f[i][k]+f[k+1][j]$ 的最小值。将最小值赋给 $f[i][j]$。

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

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

func minimumMoves(arr []int) int {
	n := len(arr)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		f[i][i] = 1
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if i+1 == j {
				f[i][j] = 2
				if arr[i] == arr[j] {
					f[i][j] = 1
				}
			} else {
				t := 1 << 30
				if arr[i] == arr[j] {
					t = f[i+1][j-1]
				}
				for k := i; k < j; k++ {
					t = min(t, f[i][k]+f[k+1][j])
				}
				f[i][j] = t
			}
		}
	}
	return f[0][n-1]
}

力扣原题 · Doocs 题解来源

1255. 得分最高的单词集合

困难1 种解法

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

题目、示例与约束

你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

• 玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
• 可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
• 单词表 words 中每个单词只能计分（使用）一次。
• 根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
• 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

 

示例 1：

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2：

输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3：

输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。

 

提示：

• 1 <= words.length <= 14
• 1 <= words[i].length <= 15
• 1 <= letters.length <= 100
• letters[i].length == 1
• score.length == 26
• 0 <= score[i] <= 10
• words[i] 和 letters[i] 只包含小写的英文字母。

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

思考

单词至多 $14$ 个，子集 $2^{14}$ 可枚举。一组单词合法当且仅当所用字母不超过 $letters$ 的存量。

先统计字母表，再对每个非空掩码拼接被选单词并核对计数，合法则按 $score$ 计分取最大。二进制枚举穷尽选择，计数比较落实字母约束。

我们注意到题目的数据范围不大，因此对于给定的单词表，我们可以使用二进制枚举的方法，枚举出所有的单词组合，然后判断每个单词组合是否满足题目要求，如果满足则计算其得分，最后取得分最大的单词组合。

我们首先用哈希表或数组 $cnt$ 记录字母表 $letters$ 中每个字母出现的次数。

接下来，我们使用二进制枚举的方法，枚举出所有的单词组合。二进制的每一位表示单词表中的每一个单词是否被选中，如果第 $i$ 位为 $1$，则表示第 $i$ 个单词被选中，否则表示第 $i$ 个单词没有被选中。

然后我们统计当前单词组合中每个字母出现的次数，记录在哈希表或数组 $cur$ 中。如果 $cur$ 中的每个字母的出现次数都不大于 $cnt$ 中的对应字母的出现次数，则说明当前单词组合满足题目要求，我们计算当前单词组合的得分，取得分最大的单词组合。

时间复杂度 $O(2^n\times n\times M)$，空间复杂度 $O(C)$。其中 $n$ 和 $M$ 分别为单词集合中单词的个数和单词的最大长度；而 $C$ 为字母表中字母的个数，本题中 $C=26$。

func maxScoreWords(words []string, letters []byte, score []int) (ans int) {
	cnt := [26]int{}
	for _, c := range letters {
		cnt[c-'a']++
	}
	n := len(words)
	for i := 0; i < 1<<n; i++ {
		cur := [26]int{}
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				for _, c := range words[j] {
					cur[c-'a']++
				}
			}
		}
		ok := true
		t := 0
		for i, v := range cur {
			if v > cnt[i] {
				ok = false
				break
			}
			t += v * score[i]
		}
		if ok && ans < t {
			ans = t
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1259. 不相交的握手 🔒

困难1 种解法

标签：数学、动态规划

题目、示例与约束

偶数 个人站成一个圆，总人数为 num_people 。每个人与除自己外的一个人握手，所以总共会有 num_people / 2 次握手。

将握手的人之间连线，请你返回连线不会相交的握手方案数。

由于结果可能会很大，请你返回答案 模 10^9+7 后的结果。

 

示例 1：

输入：num_people = 2
输出：1

示例 2：

输入：num_people = 4
输出：2
解释：总共有两种方案，第一种方案是 [(1,2),(3,4)] ，第二种方案是 [(2,3),(4,1)] 。

示例 3：

输入：num_people = 6
输出：5

示例 4：

输入：num_people = 8
输出：14

 

提示：

• 2 <= num_people <= 1000
• num_people % 2 == 0

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

思考

偶数个人围圆握手且线段不相交，方案数是卡特兰型递推。 $n\le 1000$，不能逐一画匹配。固定一人后，与之握手的对象把圆分成两个更小的偶数圆，方案数相乘再对所有合法对象求和。

$dfs(i)$ 枚举左边偶数个人 $l$，右边 $i-l-2$ 人，记忆化避免重复子圆。模 ${10}^9+7$ 防止溢出。

我们设计一个函数 $dfs(i)$，表示 $i$ 个人的握手方案数。答案为 $dfs(n)$。

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

• 如果 $i<2$，那么只有一种握手方案，即不握手，返回 $1$。
• 否则，我们可以枚举第一个人与谁握手，记剩余的左边的人数为 $l$，右边的人数为 $r=i-l-2$，那么有 $dfs(i)=\sum _{l=0}^{i-1}dfs(l)\times dfs(r)$。

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

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为 $numPeople$ 的大小。

func numberOfWays(numPeople int) int {
	const mod int = 1e9 + 7
	f := make([]int, numPeople+1)
	var dfs func(int) int
	dfs = func(i int) int {
		if i < 2 {
			return 1
		}
		if f[i] != 0 {
			return f[i]
		}
		for l := 0; l < i; l += 2 {
			r := i - l - 2
			f[i] = (f[i] + dfs(l)*dfs(r)) % mod
		}
		return f[i]
	}
	return dfs(numPeople)
}

力扣原题 · Doocs 题解来源

1262. 可被三整除的最大和

中等2 种解法

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

题目、示例与约束

给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。

 

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

 

提示：

• 1 <= nums.length <= 4 * 104
• 1 <= nums[i] <= 104

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

思考

要最大子序列和能被 $3$ 整除。 $n\le 4\times {10}^4$，不能枚举子集。和模 $3$ 只有三种余数，选或不选当前数只在这三种状态间转移。

$f[i][j]$ 为前 $i$ 个数中模 $3$ 余 $j$ 的最大和。不选则继承，选则从余数 $j-x$ 加上 $x$。答案为 $f[n][0]$。余数把目标约束压成常数个状态。

我们定义 $f[i][j]$ 表示前 $i$ 个数中选取若干个数，使得这若干个数的和模 $3$ 余 $j$ 的最大值。初始时 $f[0][0]=0$，其余为 $-\mathrm{\infty }$。

对于 $f[i][j]$，我们可以考虑第 $i$ 个数 $x$ 的状态：

• 如果我们不选 $x$，那么 $f[i][j]=f[i-1][j]$；
• 如果我们选 $x$，那么 $f[i][j]=f[i-1][(j-xmod3+3)mod3]+x$。

因此我们可以得到状态转移方程：

$$f[i][j]=max\{f[i-1][j],f[i-1][(j-xmod3+3)mod3]+x\}$$

最终答案为 $f[n][0]$。

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

func maxSumDivThree(nums []int) int {
	n := len(nums)
	const inf = 1 << 30
	f := make([][3]int, n+1)
	f[0] = [3]int{0, -inf, -inf}
	for i, x := range nums {
		i++
		for j := 0; j < 3; j++ {
			f[i][j] = max(f[i-1][j], f[i-1][(j-x%3+3)%3]+x)
		}
	}
	return f[n][0]
}

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

思考

方法一用 $O(n)$ 行。第 $i$ 行只读上一行三个值，滚动长度为 $3$ 的数组即可，空间降为常数，转移不变。

$f[i][j]$ 只与上一行三个余数状态有关，用长度为 $3$ 的数组滚动即可，空间复杂度 $O(1)$。

func maxSumDivThree(nums []int) int {
	const inf = 1 << 30
	f := [3]int{0, -inf, -inf}
	for _, x := range nums {
		g := [3]int{}
		for j := range f {
			g[j] = max(f[j], f[(j-x%3+3)%3]+x)
		}
		f = g
	}
	return f[0]
}

力扣原题 · Doocs 题解来源

1269. 停在原地的方案数

困难1 种解法

标签：动态规划

题目、示例与约束

有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。

每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。

给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。

由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。

 

示例 1：

输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动

示例  2：

输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动

示例 3：

输入：steps = 4, arrLen = 2
输出：8

 

提示：

• 1 <= steps <= 500
• 1 <= arrLen <= 106

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

思考

在长为 $arrLen$ 的数组上走 $steps$ 步回到原点。 $arrLen$ 可达 ${10}^6$，但 $steps\le 500$，能到达的位置不超过 $steps$。方案数由位置与剩余步数决定。

$dfs(i,j)$ 为位置 $i$、剩余 $j$ 步回到原点的方案；可左、右或停。 $i>j$ 时不可能赶回，直接剪掉。记忆化状态 $O(step{s}^2)$。

我们观察题目的数据范围，可以发现 $steps$ 最大不超过 $500$，这意味着我们最远只能往右走 $500$ 步。

我们可以设计一个函数 $dfs(i,j)$，表示当前在位置 $i$，并且剩余步数为 $j$ 的方案数。那么答案就是 $dfs(0,steps)$。

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

1. 如果 $i>j$ 或者 $i\ge arrLen$ 或者 $i<0$ 或者 $j<0$，那么返回 $0$。
2. 如果 $i=0$ 且 $j=0$，那么此时指针已经停在原地，并且没有剩余步数，所以返回 $1$。
3. 否则，我们可以选择向左走一步，向右走一步，或者不动，所以返回 $dfs(i-1,j-1)+dfs(i+1,j-1)+dfs(i,j-1)$。注意答案的取模操作。

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

时间复杂度 $O(steps\times steps)$，空间复杂度 $O(steps\times steps)$。其中 $steps$ 是题目给定的步数。

func numWays(steps int, arrLen int) int {
	const mod int = 1e9 + 7
	f := make([][]int, steps)
	for i := range f {
		f[i] = make([]int, steps+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) (ans int) {
		if i > j || i >= arrLen || i < 0 || j < 0 {
			return 0
		}
		if i == 0 && j == 0 {
			return 1
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		for k := -1; k <= 1; k++ {
			ans += dfs(i+k, j-1)
			ans %= mod
		}
		f[i][j] = ans
		return
	}
	return dfs(0, steps)
}

力扣原题 · Doocs 题解来源

1277. 统计全为 1 的正方形子矩阵

中等1 种解法

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

题目、示例与约束

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

 

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

 

提示：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

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

思考

统计全 $1$ 正方形个数， $m,n\le 300$，枚举每个正方形 $O(n^3)$ 偏慢。以 $(i,j)$ 为右下角的最大边长受限于上、左、左上三个位置的边长。

$f[i][j]$ 为该边长，格子为 $1$ 时取三者最小再加一。每个这样的正方形贡献 $f[i][j]$ 个（边长 $1\dots f$）。DP 把计数变成一遍填表。

我们定义 $f[i][j]$ 为以 $(i,j)$ 为右下角的正方形子矩阵的边长，初始时 $f[i][j]=0$，答案为 $\sum _{i,j}f[i][j]$。

考虑 $f[i][j]$ 如何进行状态转移。

• 当 $\text{matrix}[i][j]=0$ 时，有 $f[i][j]=0$。
• 当 $\text{matrix}[i][j]=1$ 时，状态 $f[i][j]$ 的值取决于其上、左、左上三个位置的值：
  • 如果 $i=0$ 或 $j=0$，则 $f[i][j]=1$。
  • 否则 $f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i][j-1])+1$。

答案为 $\sum _{i,j}f[i][j]$。

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

func countSquares(matrix [][]int) int {
	m, n, ans := len(matrix), len(matrix[0]), 0
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	for i, row := range matrix {
		for j, v := range row {
			if v == 0 {
				continue
			}
			if i == 0 || j == 0 {
				f[i][j] = 1
			} else {
				f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1
			}
			ans += f[i][j]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1278. 分割回文串 III

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

给你一个由小写字母组成的字符串 s，和一个整数 k。

请你按下面的要求分割字符串：

• 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
• 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

 

示例 1：

输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。

示例 2：

输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。

示例 3：

输入：s = "leetcode", k = 8
输出：0

 

提示：

• 1 <= k <= s.length <= 100
• s 中只含有小写英文字母。

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

思考

把串分成 $k$ 段并使各段成为回文的修改次数最少。 $n\le 100$，适合 DP。一段改成回文的费用可预处理：两端不同则加一，再加内段费用。

$f[i][j]$ 为前 $i$ 个字符分成 $j$ 段的最少修改，枚举上一段结尾 $h$，加上 $g[h][i-1]$。预处理 $O(n^2)$，转移 $O(n^{2}k)$。

我们定义 $f[i][j]$ 表示将字符串 $s$ 的前 $i$ 个字符分割成 $j$ 个回文串所需要的最少修改次数，我们假定 $i$ 下标从 $1$ 开始，答案为 $f[n][k]$。

对于 $f[i][j]$，我们可以枚举第 $j-1$ 个回文串的最后一个字符的位置 $h$，那么 $f[i][j]$ 就等于 $f[h][j-1]+g[h][i-1]$ 的较小值，其中 $g[h][i-1]$ 表示将字符串 $s[h..i-1]$ 变成回文串所需要的最少修改次数（这一部分我们可以通过预处理得到，时间复杂度 $O(n^2)$。

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

func palindromePartition(s string, k int) int {
	n := len(s)
	g := make([][]int, n)
	for i := range g {
		g[i] = make([]int, n)
	}
	for i := n - 1; i >= 0; i-- {
		for j := 1; j < n; j++ {
			if s[i] != s[j] {
				g[i][j] = 1
			}
			if i+1 < j {
				g[i][j] += g[i+1][j-1]
			}
		}
	}
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= min(i, k); j++ {
			if j == 1 {
				f[i][j] = g[0][i-1]
			} else {
				f[i][j] = 100000
				for h := j - 1; h < i; h++ {
					f[i][j] = min(f[i][j], f[h][j-1]+g[h][i-1])
				}
			}
		}
	}
	return f[n][k]
}

力扣原题 · Doocs 题解来源

1289. 下降路径最小和 II

困难1 种解法

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

题目、示例与约束

给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

 

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。

示例 2：

输入：grid = [[7]]
输出：7

 

提示：

• n == grid.length == grid[i].length
• 1 <= n <= 200
• -99 <= grid[i][j] <= 99

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

思考

下降路径相邻行不能同列。 $n\le 200$，朴素 $O(n^3)$ 可过。第 $i$ 行选列 $j$ 的最优值是上一行除 $j$ 外的最小路径和加上 $grid[i][j]$。

只保留上一行的 $n$ 个值，当前行现场加上「除本列外的最小前缀」。滚动数组去掉行维。

定义 $f[i][j]$ 表示前 $i$ 行且最后一个数字在第 $j$ 列的最小路径和：

$$f[i][j]=\underset{k\ne j}{min}f[i-1][k]+\mathit{\text{grid}}[i-1][j]$$

答案为 $\underset{0\le j<n}{min}f[n][j]$。滚动之后只保留最后一行，也就是一维数组 $f$ 的最小值。

$f[i][j]$ 只依赖上一行，因此用两个长度为 $n$ 的一维数组 $f$、 $g$ 滚动即可。

时间复杂度 $O(n^3)$，空间复杂度 $O(n)$。其中 $n$ 为矩阵的行数。

func minFallingPathSum(grid [][]int) int {
	f := make([]int, len(grid))
	const inf = math.MaxInt32
	for _, row := range grid {
		g := slices.Clone(row)
		for i := range f {
			t := inf
			for j := range row {
				if j != i {
					t = min(t, f[j])
				}
			}
			if t != inf {
				g[i] += t
			}
		}
		f = g
	}
	return slices.Min(f)
}

力扣原题 · Doocs 题解来源

1301. 最大得分的路径数目

困难1 种解法

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

题目、示例与约束

给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。

如果没有任何路径可以到达终点，请返回 [0, 0] 。

 

示例 1：

输入：board = ["E23","2X2","12S"]
输出：[7,1]

示例 2：

输入：board = ["E12","1X1","21S"]
输出：[4,2]

示例 3：

输入：board = ["E11","XXX","11S"]
输出：[0,0]

 

提示：

• 2 <= board.length == board[i].length <= 100

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

思考

从右下走到左上，每步只能向左、向上或左上。若枚举全部路径再比较得分， $n\le 100$，路径条数随格子增长而迅速增加，无法完成。同一格子会被多条路径到达，且题目同时要求最大得分及其方案数。

因此从终点倒推：记 $f[i][j]$ 为到达 $(i,j)$ 的最大得分， $g[i][j]$ 为取得该得分的方案数。格子 $(i,j)$ 只可能来自 $(i+1,j)$、 $(i,j+1)$、 $(i+1,j+1)$ 三者中可达且得分最优的前驱；得分严格更优则覆盖方案数，得分相同则累加。障碍与起点不计入数字，最后对方案数取模。

我们定义 $f[i][j]$ 表示从起点 $(n-1,n-1)$ 到达 $(i,j)$ 的最大得分，定义 $g[i][j]$ 表示从起点 $(n-1,n-1)$ 到达 $(i,j)$ 的最大得分的方案数。初始时 $f[n-1][n-1]=0$，并且 $g[n-1][n-1]=1$。其它位置的 $f[i][j]$ 均为 $-1$，而 $g[i][j]$ 均为 $0$。

对于当前位置 $(i,j)$，它可以由 $(i+1,j)$, $(i,j+1)$, $(i+1,j+1)$ 三个位置转移而来，因此我们可以枚举这三个位置，更新 $f[i][j]$ 和 $g[i][j]$ 的值。如果当前位置 $(i,j)$ 有障碍，或者当前位置是起点，或者其它位置越界，则不进行更新。否则，如果其它位置 $(x,y)$ 满足 $f[x][y]>f[i][j]$，那么我们更新 $f[i][j]=f[x][y]$，并且 $g[i][j]=g[x][y]$。如果 $f[x][y]=f[i][j]$，那么我们更新 $g[i][j]=g[i][j]+g[x][y]$。最后，如果当前位置 $(i,j)$ 可达并且是数字，我们更新 $f[i][j]=f[i][j]+board[i][j]$。

最后，如果 $f[0][0]<0$，说明没有路径可以到达终点，返回 $[0,0]$。否则，返回 $[f[0][0],g[0][0]]$。注意，返回结果需要对 ${10}^9+7$ 取余。

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

func pathsWithMaxScore(board []string) []int {
	n := len(board)
	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
		}
	}
	f[n-1][n-1] = 0
	g[n-1][n-1] = 1
	const mod = 1e9 + 7

	update := func(i, j, x, y int) {
		if x >= n || y >= n || f[x][y] == -1 || board[i][j] == 'X' || board[i][j] == 'S' {
			return
		}
		if f[x][y] > f[i][j] {
			f[i][j] = f[x][y]
			g[i][j] = g[x][y]
		} else if f[x][y] == f[i][j] {
			g[i][j] = (g[i][j] + g[x][y]) % mod
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			update(i, j, i+1, j)
			update(i, j, i, j+1)
			update(i, j, i+1, j+1)
			if f[i][j] != -1 && board[i][j] >= '0' && board[i][j] <= '9' {
				f[i][j] += int(board[i][j] - '0')
			}
		}
	}
	ans := make([]int, 2)
	if f[0][0] != -1 {
		ans[0], ans[1] = f[0][0], g[0][0]
	}
	return ans
}

力扣原题 · Doocs 题解来源

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

困难3 种解法

标签：字符串、动态规划

题目、示例与约束

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

 

示例 1：

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

 

提示：

• 1 <= s.length <= 500
• s 中所有字符都是小写字母。

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

思考

把 $s$ 变成回文的最少插入次数。枚举所有插入方案， $n\le 500$，状态空间过大。子问题由左右端点决定：若 $s[i]=s[j]$，只需处理开区间；否则在左侧或右侧插入一个与对端相同的字符，取两者较小者再加一。

区间互相重叠，同一 $(i,j)$ 会被反复问到。记忆化 $dfs(i,j)$ 后每个区间只算一次，复杂度 $O(n^2)$。

我们设计一个函数 $dfs(i,j)$，表示将字符串 $s[i..j]$ 变成回文串所需要的最少操作次数。那么答案就是 $dfs(0,n-1)$。

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

如果 $i\ge j$，此时无需插入任何字符，我们直接返回 $0$。

否则，我们判断 $s[i]$ 与 $s[j]$ 是否相等，如果 $s[i]=s[j]$，那么我们只需要将 $s[i+1..j-1]$ 变成回文串，那么我们返回 $dfs(i+1,j-1)$。否则，我们可以在 $s[i]$ 的左侧或者 $s[j]$ 的右侧插入一个与另一侧相同的字符，那么 $dfs(i,j)=min(dfs(i+1,j),dfs(i,j-1))+1$。

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

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

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

func minInsertions(s string) int {
	n := len(s)
	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(i, j int) int
	dfs = func(i, j int) int {
		if i >= j {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans := 1 << 30
		if s[i] == s[j] {
			ans = dfs(i+1, j-1)
		} else {
			ans = min(dfs(i+1, j), dfs(i, j-1)) + 1
		}
		f[i][j] = ans
		return ans
	}
	return dfs(0, n-1)
}

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

思考

记忆化依赖递归栈与缓存。同一转移写成区间 DP 表 $f[i][j]$ 后，按 $i$ 从大到小、 $j$ 从小到大填表，即可保证 $f[i+1][j-1]$、 $f[i+1][j]$、 $f[i][j-1]$ 均已就绪，去掉递归。

我们定义 $f[i][j]$ 表示将字符串 $s[i..j]$ 变成回文串所需要的最少操作次数。初始时 $f[i][j]=0$，答案即为 $f[0][n-1]$。

对于 $f[i][j]$，如果 $s[i]=s[j]$，那么我们只需要将 $s[i+1..j-1]$ 变成回文串，因此 $f[i][j]=f[i+1][j-1]$。否则，我们可以在 $s[i]$ 的左侧或者 $s[j]$ 的右侧插入一个与另一侧相同的字符，那么 $f[i][j]=min(f[i+1][j],f[i][j-1])+1$。

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

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

在枚举时，我们可以有两种枚举的方式：

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

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

相似题目：

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

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

方法三 · Go 实现

思考

按端点下标填表只是一种合法顺序。改为枚举区间长度 $k$，再枚举左端 $i$（右端 $j=i+k-1$），较短区间先于较长区间计算，转移完全相同，实现上只需一层长度循环。

func minInsertions(s string) int {
	n := len(s)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
	}
	for k := 2; k <= n; k++ {
		for i := 0; i+k-1 < n; i++ {
			j := i + k - 1
			if s[i] == s[j] {
				f[i][j] = f[i+1][j-1]
			} else {
				f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
			}
		}
	}
	return f[0][n-1]
}

力扣原题 · Doocs 题解来源

1320. 二指输入的的最小距离

困难1 种解法

标签：字符串、动态规划

题目、示例与约束

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。

• 例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。

给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。

坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。 

注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。

 

示例 1：

输入：word = "CAKE"
输出：3
解释： 
使用两根手指输入 "CAKE" 的最佳方案之一是： 
手指 1 在字母 'C' 上 -> 移动距离 = 0 
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'C' 到字母 'A' 的距离 = 2 
手指 2 在字母 'K' 上 -> 移动距离 = 0 
手指 2 在字母 'E' 上 -> 移动距离 = 从字母 'K' 到字母 'E' 的距离  = 1 
总距离 = 3

示例 2：

输入：word = "HAPPY"
输出：6
解释： 
使用两根手指输入 "HAPPY" 的最佳方案之一是：
手指 1 在字母 'H' 上 -> 移动距离 = 0
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'H' 到字母 'A' 的距离 = 2
手指 2 在字母 'P' 上 -> 移动距离 = 0
手指 2 在字母 'P' 上 -> 移动距离 = 从字母 'P' 到字母 'P' 的距离 = 0
手指 1 在字母 'Y' 上 -> 移动距离 = 从字母 'A' 到字母 'Y' 的距离 = 4
总距离 = 6

 

提示：

• 2 <= word.length <= 300
• 每个 word[i] 都是一个大写英文字母。

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

思考

两指在 $6\times 5$ 键盘上打完 $\mathit{\text{word}}$，每步由曼哈顿距离计费，首字母可任选一指且不计费。 $n\le 300$，若按指法搜索全部序列，状态随长度指数增长。打完第 $i$ 个字母后，只需知道两指各自停在哪个字母。

令 $f[i][j][k]$ 为打完 $\mathit{\text{word}}[i]$、两指分别在 $j$、 $k$ 的最小花费。第一个字母令一指落在其上、另一指任意，代价为 $0$。之后枚举是哪一指移到当前字母，另一指不动，用键盘曼哈顿距离转移。答案为最后一层的最小值。

我们定义 $f[i][j][k]$ 表示输入完 $\mathit{\text{word}}[i]$，且手指 $1$ 位于位置 $j$，手指 $2$ 位于位置 $k$ 时，最小的移动距离。这里的位置 $j$ 和 $k$ 表示的是字母对应的数字，取值范围为 $[0,..25]$。初始时 $f[i][j][k]=\mathrm{\infty }$。

我们实现一个函数 $\mathit{\text{dist}}(a,b)$，表示位置 $a$ 和位置 $b$ 之间的距离，即 $\mathit{\text{dist}}(a,b)=|\frac{a}{6}-\frac{b}{6}|+|amod6-bmod6|$。

接下来，我们考虑输入 $\mathit{\text{word}}[0]$，即只有一个字母的的情况，此时有两种选择：

• 手指 $1$ 位于 $\mathit{\text{word}}[0]$ 所在的位置，手指 $2$ 位于任意位置，此时 $f[0][\mathit{\text{word}}[0]][k]=0$，其中 $k\in [0,..25]$。
• 手指 $2$ 位于 $\mathit{\text{word}}[0]$ 所在的位置，手指 $1$ 位于任意位置，此时 $f[0][k][\mathit{\text{word}}[0]]=0$，其中 $k\in [0,..25]$。

然后我们考虑输入 $\mathit{\text{word}}[1,..n-1]$，我们记上一个字母和当前字母所在的位置分别为 $a$ 和 $b$，接下来我们进行分情况讨论：

如果当前手指 $1$ 位于位置 $b$，我们枚举手指 $2$ 的位置 $j$，假如上一个位置 $a$ 也是手指 $1$ 的位置，那么此时有 $f[i][b][j]=min(f[i][b][j],f[i-1][a][j]+\mathit{\text{dist}}(a,b))$。如果手指 $2$ 的位置与上一个位置 $a$ 相同，即 $j=a$，那么我们枚举上一个位置的手指 $1$ 所在的位置 $k$，此时有 $f[i][j][j]=min(f[i][b][j],f[i-1][k][a]+\mathit{\text{dist}}(k,b))$。

同理，如果当前手指 $2$ 位于位置 $b$，我们枚举手指 $1$ 的位置 $j$，假如上一个位置 $a$ 也是手指 $2$ 的位置，那么此时有 $f[i][j][b]=min(f[i][j][b],f[i-1][j][a]+\mathit{\text{dist}}(a,b))$。如果手指 $1$ 的位置与上一个位置 $a$ 相同，即 $j=a$，那么我们枚举上一个位置的手指 $2$ 所在的位置 $k$，此时有 $f[i][j][b]=min(f[i][j][b],f[i-1][a][k]+\mathit{\text{dist}}(k,b))$。

最后，我们枚举最后一个位置的手指 $1$ 和手指 $2$ 所在的位置，取最小值即为答案。

时间复杂度 $O(n\times |\mathrm{\Sigma }{|}^2)$，空间复杂度 $O(n\times |\mathrm{\Sigma }{|}^2)$。其中 $n$ 为字符串 $\mathit{\text{word}}$ 的长度，而 $|\mathrm{\Sigma }|$ 为字母表的大小，本题中 $|\mathrm{\Sigma }|=26$。

func minimumDistance(word string) int {
	n := len(word)
	f := make([][26][26]int, n)
	const inf = 1 << 30
	for i := range f {
		for j := range f[i] {
			for k := range f[i][j] {
				f[i][j][k] = inf
			}
		}
	}
	for j := range f[0] {
		f[0][word[0]-'A'][j] = 0
		f[0][j][word[0]-'A'] = 0
	}
	dist := func(a, b int) int {
		x1, y1 := a/6, a%6
		x2, y2 := b/6, b%6
		return abs(x1-x2) + abs(y1-y2)
	}
	for i := 1; i < n; i++ {
		a, b := int(word[i-1]-'A'), int(word[i]-'A')
		d := dist(a, b)
		for j := 0; j < 26; j++ {
			f[i][b][j] = min(f[i][b][j], f[i-1][a][j]+d)
			f[i][j][b] = min(f[i][j][b], f[i-1][j][a]+d)
			if j == a {
				for k := 0; k < 26; k++ {
					t := dist(k, b)
					f[i][b][j] = min(f[i][b][j], f[i-1][k][a]+t)
					f[i][j][b] = min(f[i][j][b], f[i-1][a][k]+t)
				}
			}
		}
	}
	ans := inf
	for j := 0; j < 26; j++ {
		ans = min(ans, f[n-1][word[n-1]-'A'][j])
		ans = min(ans, f[n-1][j][word[n-1]-'A'])
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

1326. 灌溉花园的最少水龙头数目

困难1 种解法

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

题目、示例与约束

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

 

示例 1：

输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：

输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

 

提示：

• 1 <= n <= 104
• ranges.length == n + 1
• 0 <= ranges[i] <= 100

方法一：贪心 · Go 实现

思考

每个水龙头覆盖一段 $[i-r_i,i+r_i]$，要覆盖 $[0,n]$ 的最少个数。枚举子集， $n\le {10}^4$ 不可行。覆盖同一左端点时，右端更远者更优，问题与跳跃游戏相同：把每个区间改写成「从左端能跳到的最远右端」 $\mathit{\text{last}}[l]$。

再沿位置推进，维护当前能到的最远 $mx$ 与上一段终点 $\mathit{\text{pre}}$；走到 $\mathit{\text{pre}}$ 就新开一个水龙头。若某点 $mx\le i$，则无法覆盖。

我们注意到，对于所有能覆盖某个左端点的水龙头，选择能覆盖最远右端点的那个水龙头是最优的。

因此，我们可以先预处理数组 $ranges$，对于第 $i$ 个水龙头，它能覆盖的左端点 $l=max(0,i-ranges[i])$，右端点 $r=i+ranges[i]$，我们算出所有能覆盖左端点 $l$ 的水龙头中，右端点最大的那个位置，记录在数组 $last[i]$ 中。

然后我们定义以下三个变量，其中：

• 变量 $ans$ 表示最终答案，即最少水龙头数目；
• 变量 $mx$ 表示当前能覆盖的最远右端点；
• 变量 $pre$ 表示上一个水龙头覆盖的最远右端点。

我们在 $[0,...n-1]$ 的范围内遍历所有位置，对于当前位置 $i$，我们用 $last[i]$ 更新 $mx$，即 $mx=max(mx,last[i])$。

• 如果 $mx\le i$，说明无法覆盖下一个位置，返回 $-1$。
• 如果 $pre=i$，说明需要使用一个新的子区间，因此我们将 $ans$ 加 $1$，并且更新 $pre=mx$。

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

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为花园的长度。

相似题目：

• 45. 跳跃游戏 II
• 55. 跳跃游戏
• 1024. 视频拼接

func minTaps(n int, ranges []int) (ans int) {
	last := make([]int, n+1)
	for i, x := range ranges {
		l, r := max(0, i-x), i+x
		last[l] = max(last[l], r)
	}
	var pre, mx int
	for i, j := range last[:n] {
		mx = max(mx, j)
		if mx <= i {
			return -1
		}
		if pre == i {
			ans++
			pre = mx
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1335. 工作计划的最低难度

困难1 种解法

标签：数组、动态规划

题目、示例与约束

你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。

你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。

给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。

返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。

 

示例 1：

输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7 

示例 2：

输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。

示例 3：

输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：工作计划为每天一项工作，总难度为 3 。

示例 4：

输入：jobDifficulty = [7,1,7,1,7,1], d = 3
输出：15

示例 5：

输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
输出：843

 

提示：

• 1 <= jobDifficulty.length <= 300
• 0 <= jobDifficulty[i] <= 1000
• 1 <= d <= 10

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

思考

把工作序列切成 $d$ 段，每段难度为段内最大值，总和尽量小。工作不可重排， $n\le 300$、 $d\le 10$，枚举切分点仍过多。前 $i$ 份工作用 $j$ 天的最优只依赖「最后一天做完 $[k..i]$」。

令 $f[i][j]$ 为该最优。倒序枚举 $k$ 时可同步维护段内最大值，转移到 $f[k-1][j-1]$。工作数不足天数则无解。

我们定义 $f[i][j]$ 表示完成前 $i$ 项工作，且一共用了 $j$ 天的最小难度。初始时 $f[0][0]=0$，其余 $f[i][j]$ 均为 $\mathrm{\infty }$。

考虑第 $j$ 天的工作安排，我们可以枚举第 $j$ 天完成的工作 $[k,..i]$，那么有状态转移方程：

$$f[i][j]=\underset{k\in [1,i]}{min}\{f[k-1][j-1]+\underset{k\le t\le i}{max}\{jobDifficulty[t-1]\}\}$$

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

时间复杂度 $O(n^2\times d)$，空间复杂度 $O(n\times d)$。其中 $n$ 和 $d$ 分别为工作数量和需要计划的天数。

func minDifficulty(jobDifficulty []int, d int) int {
	n := len(jobDifficulty)
	f := make([][]int, n+1)
	const inf = 1 << 30
	for i := range f {
		f[i] = make([]int, d+1)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := 1; j <= min(d, i); j++ {
			mx := 0
			for k := i; k > 0; k-- {
				mx = max(mx, jobDifficulty[k-1])
				f[i][j] = min(f[i][j], f[k-1][j-1]+mx)
			}
		}
	}
	if f[n][d] == inf {
		return -1
	}
	return f[n][d]
}

力扣原题 · Doocs 题解来源

1340. 跳跃游戏 V

困难3 种解法

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

题目、示例与约束

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

• i + x ，其中 i + x < arr.length 且 0 < x <= d 。
• i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

 

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2：

输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3：

输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。

示例 4：

输入：arr = [7,1,7,1,7,1], d = 2
输出：2

示例 5：

输入：arr = [66], d = 1
输出：1

 

提示：

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

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

思考

从 $i$ 只能跳到距离不超过 $d$、严格更矮、且中间没有更高柱的位置，求从任意起点能访问的最多下标。 $n\le 1000$，记忆化 $dfs(i)$：向左右扫描直到越界、超距或遇到不低于自己的柱，递归取最大访问数再加一。每个起点取最大。

我们设计一个函数 $\text{dfs}(i)$，表示从下标 $i$ 开始跳跃能够访问的最大下标数。我们可以枚举 $i$ 的所有合法的跳跃目标 $j$，即 $i-d\le j\le i+d$，并且 $\text{arr}[i]>\text{arr}[j]$。对于每个合法的 $j$，我们可以递归地计算 $\text{dfs}(j)$，并取其中的最大值。最终的答案即为所有 $i$ 的 $\text{dfs}(i)$ 的最大值。

我们可以使用记忆化搜索来优化这个过程，即使用一个数组 $f$ 记录每个下标的 $\text{dfs}$ 值，避免重复计算。

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

func maxJumps(arr []int, d int) (ans int) {
	n := len(arr)
	f := make([]int, n)
	var dfs func(int) int
	dfs = func(i int) int {
		if f[i] != 0 {
			return f[i]
		}
		ans := 1
		for j := i - 1; j >= 0; j-- {
			if i-j > d || arr[j] >= arr[i] {
				break
			}
			ans = max(ans, 1+dfs(j))
		}
		for j := i + 1; j < n; j++ {
			if j-i > d || arr[j] >= arr[i] {
				break
			}
			ans = max(ans, 1+dfs(j))
		}
		f[i] = ans
		return ans
	}
	for i := 0; i < n; i++ {
		ans = max(ans, dfs(i))
	}
	return
}

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

思考

方法一已经按柱高从低到高填好同一张 $f$。下面的转移与那张表是同一定义。

我们可以将数组 $\text{arr}$ 中的每个元素 $x$ 与其下标 $i$ 组成一个元组 $(x,i)$，并将这些元组按照 $x$ 从小到大排序。

我们可以将数组 $arr$ 中的每个元素 $x$ 与其下标 $i$ 组成一个元组 $(x,i)$，并将这些元组按照 $x$ 从小到大排序。

接下来定义 $f[i]$ 表示从下标 $i$ 开始跳跃能够访问的最大下标数。初始时 $f[i]=1$，即每个下标都可以单独作为一次跳跃。

我们可以按照元组 $(x,i)$ 的顺序枚举 $i$，并枚举 $i$ 的所有合法的跳跃目标 $j$，即 $i-d\le j\le i+d$，并且 $arr[i]>arr[j]$。对于每个合法的 $j$，我们可以更新 $f[i]$ 的值，即 $f[i]=max(f[i],1+f[j])$。

最终的答案即为 $\underset{0\le i<n}{max}f[i]$。

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

func maxJumps(arr []int, d int) int {
	n := len(arr)
	idx := make([]int, n)
	f := make([]int, n)
	for i := range f {
		idx[i] = i
		f[i] = 1
	}
	sort.Slice(idx, func(i, j int) bool { return arr[idx[i]] < arr[idx[j]] })
	for _, i := range idx {
		for j := i - 1; j >= 0; j-- {
			if i-j > d || arr[j] >= arr[i] {
				break
			}
			f[i] = max(f[i], 1+f[j])
		}
		for j := i + 1; j < n; j++ {
			if j-i > d || arr[j] >= arr[i] {
				break
			}
			f[i] = max(f[i], 1+f[j])
		}
	}
	return slices.Max(f)
}

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

思考

把每一步能落到的更矮柱子都展开，路径数是指数级的。数组长度可以到 $1000$，从一根柱子向相邻更矮的柱子走时，第一次调用总是落到下一根，递归深度就是 $n$。一次跳跃只能落到严格更矮、且中间没有不低于自己的位置，因此 $f[i]$ 只依赖更矮的下标。将下标按高度升序排列后，处理 $i$ 时左右窗口里合法的 $j$ 都已有最终答案，于是用 $f[i]=max(f[i],1+f[j])$ 更新，初值为 $1$。答案取整张表的最大值。

我们令 $f[i]$ 表示从下标 $i$ 出发能够访问的最大下标数，初始时 $f[i]=1$。

将每个下标按照 $\text{arr}[i]$ 从小到大排序。处理下标 $i$ 时，分别向左、向右扫描，直到距离超过 $d$，或遇到高度不低于 $\text{arr}[i]$ 的柱子。对扫描中遇到的每个合法下标 $j$，用 $f[i]=max(f[i],1+f[j])$ 更新。更矮的柱子已经处理完毕，因此 $f[j]$ 不再变化。

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

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

func maxJumps(arr []int, d int) int {
	n := len(arr)
	idx := make([]int, n)
	f := make([]int, n)
	for i := range f {
		idx[i] = i
		f[i] = 1
	}
	sort.Slice(idx, func(i, j int) bool { return arr[idx[i]] < arr[idx[j]] })
	for _, i := range idx {
		for j := i - 1; j >= 0; j-- {
			if i-j > d || arr[j] >= arr[i] {
				break
			}
			f[i] = max(f[i], 1+f[j])
		}
		for j := i + 1; j < n; j++ {
			if j-i > d || arr[j] >= arr[i] {
				break
			}
			f[i] = max(f[i], 1+f[j])
		}
	}
	return slices.Max(f)
}

力扣原题 · Doocs 题解来源

1349. 参加考试的最大学生数

困难1 种解法

标签：位运算、数组、动态规划、位掩码、矩阵、最小割、二分图、最大流、图的匹配、最大匹配、Edmonds–Karp 算法、Dinic 算法、MPM 算法、Push-Relabel 算法、网络流

题目、示例与约束

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。

学生必须坐在状况良好的座位上。

 

示例 1：

输入：seats = [["#",".","#","#",".","#"],
              [".","#","#","#","#","."],
              ["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。 

示例 2：

输入：seats = [[".","#"],
              ["#","#"],
              ["#","."],
              ["#","#"],
              [".","#"]]
输出：3
解释：让所有学生坐在可用的座位上。

示例 3：

输入：seats = [["#",".",".",".","#"],
              [".","#",".","#","."],
              [".",".","#",".","."],
              [".","#",".","#","."],
              ["#",".",".",".","#"]]
输出：10
解释：让学生坐在第 1、3 和 5 列的可用座位上。

 

提示：

• seats 只包含字符 '.' 和'#'
• m == seats.length
• n == seats[i].length
• 1 <= m <= 8
• 1 <= n <= 8

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

思考

座位 $m,n\le 8$，学生不能左右相邻，也不能与斜前方相邻。按行枚举行内子集， $2^{mn}$ 过大，但一行状态只有 $2^n$ 种。把空座位压成掩码，枚举与空位相容且无左右相邻的 $\mathit{\text{mask}}$，再从下一行空位中挖掉斜前方被挡住的位置，记忆化 $dfs(\mathit{\text{seat}},i)$ 取最大人数。

我们注意到，每个座位有两种状态：可选和不可选。因此，我们可以使用二进制数来表示每一行的座位状态，其中 $1$ 表示可选，而 $0$ 表示不可选。例如，对于示例 $1$ 中的第一行，我们可以表示为 $010010$。因此，我们将初始座位转换为一个一维数组 $ss$，其中 $ss[i]$ 表示第 $i$ 行的座位状态。

接下来，我们设计一个函数 $dfs(seat,i)$，表示从第 $i$ 行开始，当前行的座位状态为 $seat$，可以容纳的最多学生人数。

我们可以枚举第 $i$ 行的所有选座状态 $mask$，并且判断 $mask$ 是否满足以下条件：

• 状态 $mask$ 不能选择 $seat$ 之外的座位；
• 状态 $mask$ 不能选择相邻的座位。

如果满足条件，我们求出当前行选择的座位个数 $cnt$，如果当前是最后一行，则更新函数的返回值，即 $ans=max(ans,cnt)$。否则，我们继续递归地求解下一行的最大人数，下一行的座位状态 $nxt=ss[i+1]$，并且需要排除当前行已选座位的左右两侧。然后我们递归地求解下一行的最大人数，即 $ans=max(ans,cnt+dfs(nxt,i+1))$。

最后，我们将 $ans$ 作为函数的返回值返回。

为了避免重复计算，我们可以使用记忆化搜索，将函数 $dfs(seat,i)$ 的返回值保存在一个二维数组 $f$ 中，其中 $f[seat][i]$ 表示从第 $i$ 行开始，当前行的座位状态为 $seat$，可以容纳的最多学生人数。

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

func maxStudents(seats [][]byte) int {
	m, n := len(seats), len(seats[0])
	ss := make([]int, m)
	f := make([][]int, 1<<n)
	for i, seat := range seats {
		for j, c := range seat {
			if c == '.' {
				ss[i] |= 1 << j
			}
		}
	}
	for i := range f {
		f[i] = make([]int, m)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(seat, i int) int {
		if f[seat][i] != -1 {
			return f[seat][i]
		}
		ans := 0
		for mask := 0; mask < 1<<n; mask++ {
			if (seat|mask) != seat || (mask&(mask<<1)) != 0 {
				continue
			}
			cnt := bits.OnesCount(uint(mask))
			if i == m-1 {
				ans = max(ans, cnt)
			} else {
				nxt := ss[i+1] & ^(mask >> 1) & ^(mask << 1)
				ans = max(ans, cnt+dfs(nxt, i+1))
			}
		}
		f[seat][i] = ans
		return ans
	}
	return dfs(ss[0], 0)
}

力扣原题 · Doocs 题解来源

1359. 有效的快递序列数目

困难1 种解法

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

题目、示例与约束

给你 n 笔订单，每笔订单都需要快递服务。

计算所有有效的 取货 / 交付 可能的顺序，使 delivery(i) 总是在 pickup(i) 之后。

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

 

示例 1：

输入：n = 1
输出：1
解释：只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。

示例 2：

输入：n = 2
输出：6
解释：所有可能的序列包括：
(P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
(P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。

示例 3：

输入：n = 3
输出：90

 

提示：

• 1 <= n <= 500

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

思考

$n$ 个订单，每个有取件、送达且取件必须在送达前，求排列数。 $n\le 500$，不能枚举 $(2n)!$ 再过滤。第 $i$ 个订单的送达可当作当前序列的最后一次送达，其取件可插在前 $2i-1$ 个空隙之一，并与前 $i-1$ 个订单的方案相乘，再乘上选择哪一单放最后的 $i$ 种。滚动 $f\leftarrow f\cdot i\cdot (2i-1)$ 并对模取余。

我们定义 $f[i]$ 表示 $i$ 个订单的所有有效的收件/配送序列的数目。初始时 $f[1]=1$。

我们可以选择这 $i$ 个订单中的任意一个作为最后一个配送的订单 $D_i$，那么它的收件订单 $P_i$ 可以在之前 $2\times i-1$ 的任意一个位置，剩下的 $i-1$ 个订单的配送/收件序列数目为 $f[i-1]$，所以 $f[i]$ 可以表示为：

$$f[i]=i\times (2\times i-1)\times f[i-1]$$

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

我们注意到 $f[i]$ 的值只与 $f[i-1]$ 有关，所以可以用一个变量代替数组，降低空间复杂度。

时间复杂度 $O(n)$，其中 $n$ 为订单数目。空间复杂度 $O(1)$。

func countOrders(n int) int {
	const mod = 1e9 + 7
	f := 1
	for i := 2; i <= n; i++ {
		f = f * i * (2*i - 1) % mod
	}
	return f
}

力扣原题 · Doocs 题解来源

1363. 形成三的最大倍数

困难1 种解法

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

题目、示例与约束

给你一个整数数组 digits，你可以通过按 任意顺序 连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。如果无法得到答案，请返回一个空字符串。返回的结果不应包含不必要的前导零。

 

示例 1：

输入：digits = [8,1,9]
输出："981"

示例 2：

输入：digits = [8,6,7,1,0]
输出："8760"

示例 3：

输入：digits = [1]
输出：""

示例 4：

输入：digits = [0,0,0,0,0,0]
输出："0"

 

提示：

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9

方法一：贪心 + 动态规划 + 逆推 · Go 实现

思考

用给定数位组成能被 $3$ 整除的最大整数。贪心删掉模 $3$ 余数最小的若干位即可，但同等长度下还要尽量靠左放较大数位，实现上容易漏边界。数位和模 $3$ 为 $0$ 当且仅当所选集合模 $3$ 为 $0$，因此先升序，再用 $f[i][j]$ 表示前 $i$ 个数中选出和模 $3$ 为 $j$ 的最大个数。

从 $f[n][0]$ 逆推所选数位：能转移则取当前位。升序保证同等长度时较大位更晚被考虑、因而更先被写入答案；去掉前导零后即为最大整数。无法选出任何位（含单独的 $0$ 之外的空集）则返回空串。

我们定义 $f[i][j]$ 表示在前 $i$ 个数中选取若干个数，使得选取的数的和模 $3$ 为 $j$ 的最大长度。为了使得选取的数最大，我们需要尽可能选取更多的数，因此我们需要使得 $f[i][j]$ 尽可能大。我们初始化 $f[0][0]=0$，其余的 $f[0][j]=-\mathrm{\infty }$。

考虑 $f[i][j]$ 如何进行状态转移。我们可以不选取第 $i$ 个数，此时 $f[i][j]=f[i-1][j]$；我们也可以选取第 $i$ 个数，此时 $f[i][j]=f[i-1][(j-x_{i}mod3+3)mod3]+1$，其中 $x_i$ 表示第 $i$ 个数的值。因此我们有如下的状态转移方程：

$$f[i][j]=max\{f[i-1][j],f[i-1][(j-x_{i}mod3+3)mod3]+1\}$$

如果 $f[n][0]\le 0$，那么我们无法选取任何数，因此答案字符串为空。否则我们可以通过 $f$ 数组进行逆推，找出选取的数。

定义 $i=n$, $j=0$，从 $f[i][j]$ 开始逆推，记 $k=(j-x_{i}mod3+3)mod3$，如果 $f[i-1][k]+1=f[i][j]$，那么我们选取了第 $i$ 个数，否则我们没有选取第 $i$ 个数。如果我们选取了第 $i$ 个数，那么我们将 $j$ 更新为 $k$，否则我们保持 $j$ 不变。为了使得同等长度的数最大，我们应该优先选取较大的数，因此，我们在前面首先对数组进行排序。

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

func largestMultipleOfThree(digits []int) string {
	sort.Ints(digits)
	n := len(digits)
	const inf = 1 << 30
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, 3)
		for j := range f[i] {
			f[i][j] = -inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := 0; j < 3; j++ {
			f[i][j] = max(f[i-1][j], f[i-1][(j-digits[i-1]%3+3)%3]+1)
		}
	}
	if f[n][0] <= 0 {
		return ""
	}
	ans := []byte{}
	for i, j := n, 0; i > 0; i-- {
		k := (j - digits[i-1]%3 + 3) % 3
		if f[i][j] == f[i-1][k]+1 {
			ans = append(ans, byte('0'+digits[i-1]))
			j = k
		}
	}
	i := 0
	for i < len(ans)-1 && ans[i] == '0' {
		i++
	}
	return string(ans[i:])
}

力扣原题 · Doocs 题解来源

1387. 将整数按权重排序

中等1 种解法

标签：记忆化、动态规划、排序

题目、示例与约束

我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：

• 如果 x 是偶数，那么 x = x / 2
• 如果 x 是奇数，那么 x = 3 * x + 1

比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。

给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。

请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。

 

示例 1：

输入：lo = 12, hi = 15, k = 2
输出：13
解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。

示例 2：

输入：lo = 7, hi = 11, k = 4
输出：7
解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。

 

提示：

• 1 <= lo <= hi <= 1000
• 1 <= k <= hi - lo + 1

方法一：自定义排序 · Go 实现

思考

区间 $[lo,hi]$ 按「变成 $1$ 的步数」排序，步数相同按数值，取第 $k$ 个。区间长度不超过 $1000$，直接对每个数模拟 Collatz 步数即可；记忆化避免重复计算。自定义键 $f$ 后取下标 $k-1$。

我们先定义一个函数 $\mathit{\text{f}}(x)$，表示将数字 $x$ 变成 $1$ 所需要的步数，也即是数字 $x$ 的权重。

然后我们将区间 $[\mathit{\text{lo}},\mathit{\text{hi}}]$ 内的所有数字按照权重升序排序，如果权重相同，按照数字自身的数值升序排序。

最后返回排序后的第 $k$ 个数字。

时间复杂度 $O(n\times \log n\times M)$，空间复杂度 $O(n)$。其中 $n$ 是区间 $[\mathit{\text{lo}},\mathit{\text{hi}}]$ 内的数字个数，而 $M$ 是 $f(x)$ 的最大值，本题中 $M$ 最大为 $178$。

func getKth(lo int, hi int, k int) int {
	f := func(x int) (ans int) {
		for ; x != 1; ans++ {
			if x%2 == 0 {
				x /= 2
			} else {
				x = 3*x + 1
			}
		}
		return
	}
	nums := make([]int, hi-lo+1)
	for i := range nums {
		nums[i] = lo + i
	}
	sort.Slice(nums, func(i, j int) bool {
		fx, fy := f(nums[i]), f(nums[j])
		if fx != fy {
			return fx < fy
		}
		return nums[i] < nums[j]
	})
	return nums[k-1]
}

力扣原题 · Doocs 题解来源

1388. 3n 块披萨

困难1 种解法

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

题目、示例与约束

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

• 你挑选 任意 一块披萨。
• Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
• Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
• 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

 

示例 1：

输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2：

输入：slices = [8,9,8,6,1,1]
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

 

提示：

• 1 <= slices.length <= 500
• slices.length % 3 == 0
• 1 <= slices[i] <= 1000

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

思考

环形排列中取 $n$ 块，不能取相邻，总和最大。证明可把问题化成「环上取 $n$ 个不相邻」。环的首尾互斥，故拆成去掉首、去掉尾的两段线性问题。线性部分用 $f[i][j]$：前 $i$ 个里选 $j$ 个不相邻的最大和，不选则 $f[i-1][j]$，选则 $f[i-2][j-1]+nums[i-1]$。两段取较大。

我们可以将这个问题转化为：在一个长度为 $3n$ 的环形数组中，选择其中 $n$ 个不相邻的数，使得这 $n$ 个数的和最大。

证明如下：

• 当 $n=1$ 时，我们可以选择数组中的任意一个数。
• 当 $n>1$ 时，那么一定存在一个数，使得它的某一侧有两个连续的数没有被选择，而另一侧至少有一个数没有被选择。因此，我们可以将这个数和它两侧的数一起从数组中删除，然后剩下的 $3(n-1)$ 个数构成一个新的环形数组。问题规模缩小成了在长度为 $3(n-1)$ 的环形数组中选择 $n-1$ 个不相邻的数，使得这 $n-1$ 个数的和最大。

因此，我们需要求解的问题可以转化为：在一个长度为 $3n$ 的环形数组中，选择其中 $n$ 个不相邻的数，使得这 $n$ 个数的和最大。

环形数组中，如果选择了第一个数，那么最后一个数就不能选择，如果选择了最后一个数，那么第一个数就不能选择，因此我们可以将环形数组拆成两个数组，一个是去掉第一个数的，一个是去掉最后一个数的，然后分别求解这两个数组的最大值，最后取两个最大值中的较大值即可。

我们用一个函数 $g(nums)$，表示在数组 $nums$ 中选择 $n$ 个不相邻的数，使得这 $n$ 个数的和最大，那么我们的目标就是求 $g(slices)$ 和 $g(slices[1:])$ 中的较大值。

函数 $g(nums)$ 的求解方法如下：

我们记数组 $nums$ 的长度为 $m$，定义 $f[i][j]$ 表示在数组 $nums$ 的前 $i$ 个数中选择 $j$ 个不相邻的数的最大和。

考虑 $f[i][j]$，如果我们不选择第 $i$ 个数，那么 $f[i][j]=f[i-1][j]$，如果我们选择第 $i$ 个数，那么 $f[i][j]=f[i-2][j-1]+nums[i-1]$，因此我们可以得到状态转移方程：

$$f[i][j]=max(f[i-1][j],f[i-2][j-1]+nums[i-1])$$

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

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

func maxSizeSlices(slices []int) int {
	n := len(slices) / 3
	g := func(nums []int) int {
		m := len(nums)
		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++ {
				f[i][j] = max(f[i-1][j], nums[i-1])
				if i >= 2 {
					f[i][j] = max(f[i][j], f[i-2][j-1]+nums[i-1])
				}
			}
		}
		return f[m][n]
	}
	a, b := g(slices[:len(slices)-1]), g(slices[1:])
	return max(a, b)
}

力扣原题 · Doocs 题解来源