给你一维空间的 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 <= 1000 1 <= k <= n-1
方法一：动态规划。
dp[i][j][0]：表示前i个点放了j个线段并且第j个线段没有延伸到i位置的方案数。
dp[i][j][1]：表示前i个点放了j个线段并且第j个线段延伸到i位置的方案数。
状态转移方程见代码：
class Solution { private int mod = 1000000007; public int numberOfSets(int n, int k) { long[][][] dp = new long[n][k + 1][2]; dp[0][0][0] = 1; for (int i = 1; i < n; i++) for (int j = 0; j <= k; j++) { dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % mod; dp[i][j][1] = dp[i - 1][j][1]; if (j > 0) { dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j - 1][0]) % mod; dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j - 1][1]) % mod; } } return (int) ((dp[n - 1][k][0] + dp[n - 1][k][1]) % mod); } }方法二：组合数学。
这种解法我只能扣666了，对着题解思考，发现还是不难想到的。我们知道k个线段在n个点上放置时最多会有2k个端点（所有线段不相接），而最少有k+1个点（所有线段相接，但是最左边和最右边的点一直存在，中间看成k-1个点）。也就是说中间选择的k-1个点可以任意重复放置一次，因此我们能够将问题转化为在n+k-1个点上选择2k个点的方案数（由于一个线段两个点，k个线段就是2k个点啦）。
class Solution { private int mod = 1000000007; private long C[][]; private void init(int n) { C = new long[n + 1][n + 1]; for (int i = 0; i <= n; i++) C[i][0] = C[i][i] = 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } public int numberOfSets(int n, int k) { if (2 * k > n + k - 1) return 0; init(n + k); return (int) C[n + k - 1][2 * k]; } }
