大小为 K 的不重叠线段的数目
难度:
标签:
题目描述
给你一维空间的 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
代码结果
运行时间: 28 ms, 内存: 16.0 MB
/*
* 思路：
* Java Stream 不适合解决动态规划问题，但我们可以用函数式编程的思想进行模拟。
* 由于需要修改全局状态，纯粹的 Stream 难以处理。
* 我们依旧会使用动态规划的思路。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class SolutionStream {
private static final int MOD = 1000000007;
public int numberOfSets(int n, int k) {
int[][] dp = new int[n + 1][k + 1];
for (int[] row : dp) {
Arrays.fill(row, 0);
}
dp[0][0] = 1;
IntStream.range(1, n + 1).forEach(i -> {
IntStream.rangeClosed(0, k).forEach(j -> {
dp[i][j] = dp[i - 1][j];
if (j > 0) {
dp[i][j] = (dp[i][j] + IntStream.range(0, i - 1).map(m -> dp[m][j - 1]).sum()) % MOD;
}
});
});
return dp[n][k];
}
public static void main(String[] args) {
SolutionStream solution = new SolutionStream();
System.out.println(solution.numberOfSets(4, 2)); // 输出 5
System.out.println(solution.numberOfSets(3, 1)); // 输出 3
System.out.println(solution.numberOfSets(30, 7)); // 输出 796297179
System.out.println(solution.numberOfSets(5, 3)); // 输出 7
System.out.println(solution.numberOfSets(3, 2)); // 输出 1
}
}解释
方法:
该题解应用了排列组合的思路。首先，题目要求找到k个不重叠线段，每个线段至少包含两个点。因此，最少需要2k个点来形成k个线段。为了方便计算，可以将问题转化为组合问题。考虑如果把每个线段简化为两个点，那么k个线段就是选择2k个点，可以看作是从n个点中选择2k个点的组合。然而，题目中线段的端点可以重合，这意味着选取的点可以是相邻的。这种情况下，可以通过引入额外的点，将问题转化为从增广的点集中选择2k个点，点集大小为n+k-1。组合公式C(m, n)表示从m个元素中选择n个元素的组合数。题解中使用了组合公式和费马小定理来计算组合数，以避免大数的直接除法运算。
时间复杂度:
O(k)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到的`额外的点`是如何引入的，以及这些点在实际问题中代表什么含义？
▷🦆
在计算组合数时，为什么需要使用费马小定理来计算分母的模逆，直接求解不可行吗？
▷🦆
题解中将问题转化为从增广点集中选择点的组合数，这种方法是否有可能在某些情况下重复计数？
▷