题目描述

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。

样例

输入：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)} 。

输入：n = 3, k = 1
输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

输入：n = 30, k = 7
输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。

输入：n = 5, k = 3
输出：7

输入：n = 3, k = 2
输出：1

提示：

• 2 <= n <= 1000
• 1 <= k <= n-1

算法分析

时间复杂度 $O(nk)$

空间复杂度 $O(nk)$

由于当前层只会依赖上一层，因此可以优化到一维

Java 代码

class Solution {
    static int N = 1010, mod = 1000000000 + 7;
    static long[][][] f = new long[N][N][2];
    public int numberOfSets(int n, int k) {
        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < n;j ++)
                Arrays.fill(f[i][j], 0);
            f[i][0][0] = 1;
        }

        for(int i = 1;i < n;i ++)
            for(int j = 1;j <= k;j ++)
            {
                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mod;
                f[i][j][1] = (f[i - 1][j - 1][0] + f[i - 1][j][1] + f[i - 1][j - 1][1]) % mod;
            }

        return (int)((f[n - 1][k][0] + f[n - 1][k][1]) % mod);
    }
}