LeetCode 题解工作台
大小为 K 的不重叠线段的数目
给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1 ）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。 请你返回 k 个不重叠线段的方案…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
记 表示使用前 个点构造了 条线段，且最后一条线段的右端点不为 的方案数；记 表示使用了前 个点构造了 条线段，且最后一条线段的右端点为 的方案数。初始时 。 考虑 ，由于第 条线段的右端点不为 ，因此前 个点构造了 条线段，因此有：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。
请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 109 + 7 取余 后返回。
示例 1：
输入：n = 4, k = 2
输出：5
解释：
如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。
示例 2：
输入：n = 3, k = 1
输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。
示例 3：
输入：n = 30, k = 7 输出：796297179 解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。
示例 4：
输入：n = 5, k = 3 输出：7
示例 5：
输入：n = 3, k = 2 输出：1
提示：
2 <= n <= 10001 <= k <= n-1
解题思路
方法一：动态规划
记 表示使用前 个点构造了 条线段，且最后一条线段的右端点不为 的方案数；记 表示使用了前 个点构造了 条线段，且最后一条线段的右端点为 的方案数。初始时 。
考虑 ，由于第 条线段的右端点不为 ，因此前 个点构造了 条线段，因此有：
考虑 ，第 条线段的右端点为 ，如果第 条线段的长度超过 ，则前 个点构造了 条线段，且第 条线段的右端点一定覆盖了 ，因此有：
如果第 条线段的长度为 ，则前 个点构造了 条线段，有：
答案为 。
时间复杂度 ，空间复杂度 。
class Solution:
def numberOfSets(self, n: int, k: int) -> int:
mod = 10**9 + 7
f = [[0] * (k + 1) for _ in range(n + 1)]
g = [[0] * (k + 1) for _ in range(n + 1)]
f[1][0] = 1
for i in range(2, n + 1):
for j in range(k + 1):
f[i][j] = (f[i - 1][j] + g[i - 1][j]) % mod
g[i][j] = g[i - 1][j]
if j:
g[i][j] += f[i - 1][j - 1]
g[i][j] %= mod
g[i][j] += g[i - 1][j - 1]
g[i][j] %= mod
return (f[-1][-1] + g[-1][-1]) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n*k) for the DP approach, as each dp state is computed once. Space can be reduced to O(k) using rolling arrays. Precomputation for combinatorial formulas takes O(n+k) time and space. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on defining states that include the current index and remaining segments to form.
- question_mark
Expect discussion about modulo arithmetic and integer overflows.
- question_mark
Look for optimization from O(n*k) space to O(k) using rolling DP arrays.
常见陷阱
外企场景- error
Incorrectly allowing overlapping segments by not enforcing endpoint constraints.
- error
Forgetting that segments must cover at least two points, causing overcounting.
- error
Neglecting modulo operations, leading to incorrect results for large n and k.
进阶变体
外企场景- arrow_right_alt
Count the number of non-overlapping segments covering all n points.
- arrow_right_alt
Allow segments of length exactly 2 and count the arrangements for k segments.
- arrow_right_alt
Compute the number of sets where segments can only share start points, not end points.