目标
给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。
请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 10^9 + 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 种。将这个数对 10^9 + 7 取余得到 796297179 。示例 4：
输入：n = 5, k = 3
输出：7示例 5：
输入：n = 3, k = 2
输出：1说明：
- 2 <= n <= 1000
- 1 <= k <= n-1
思路
数轴上有 n 个点，编号为 0 ~ n - 1，求从中选择 k 个不重叠线段（至少覆盖两个点）的方案数。线段 [a, b] 与 [c, d] 不重叠指 b <=c 或 d <= a。
定义 dp[i][k] 表示 [0, i] 中恰好 k 个不重叠线段的方案数。根据选或者不选 i 考虑状态转移方程，如果不选 i，方案数等于前面的方案数，如果选，需要枚举前面所有的 p ∈ [0, i - 1]，累加 dp[p][j - 1]。
dp[i][j] = (dp[i - 1][j] + sum) % mod，sum = Σdp[p][j - 1], p ∈ [0, i - 1]
代码
/**
* @date 2026-09-17 15:31
*/
public class NumberOfSets1621 {
public int numberOfSets(int n, int k) {
int mod = 1000000007;
int[][] dp = new int[n][k + 1];
dp[0][0] = 1;
int[] prefix = new int[k + 1];
for (int i = 1; i < n; i++) {
for (int j = 1; j <= k; j++) {
prefix[j] = (prefix[j] + dp[i - 1][j - 1]) % mod;
dp[i][j] = (dp[i - 1][j] + prefix[j]) % mod;
}
}
int res = 0;
for (int i = 0; i < n; i++) {
res = (res + dp[i][k]) % mod;
}
return res;
}
}
性能
