1
2
3
4
5

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

1
2
3

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

1
2
3

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

1
2

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

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设 dp[i][j]: i个点, j条线段的总方案数;
    /// 2. 如果第j条线段右端点不是i, 则去掉第i个点,组成j条线段的方案数不变,
    ///    则有: dp[i][j] = dp[i-1][j];
    /// 3. 如果第j条线段右端点是i, 则去掉第j条线段, 所有由前面点组成j-1条线段的总方案数为:
    ///    dp[i-1][j-1] + dp[i-2][j-1] + .. dp[0][j-1]), 记为sum_dp[i-1][j-1]
    ///    则 sum_dp[i][j] = sum_dp[i-1][j] + dp[i][j]
    /// 4. 所以得到递推关系:
    ///       dp[i][j] = dp[i-1][j] + sum_dp[i-1][j-1]
    ///       sum_dp[i][j] = sum_dp[i-1][j] + dp[i][j]
    /// 5. 初始条件:
    ///       dp[i][1] = dp[i-1][1] + (i - 1)   (i=1..=n)
    ///                      |           |-- 线段右端点为i, 因为总共只有一条线段,所以前面部分不是线段,
    ///                      |               以i为右端点的线段总共有i-1条
    ///                      |-- 线段右端点不是i, 第i-1个端点组成1条线段的方案数
    ///       sum_dp[i][1] = sum_dp[i-1][1] + dp[i][1]
    /// 6. 终止条件: dp[n][k]
    pub fn number_of_sets(n: i32, k: i32) -> i32 {
        let (n, k) = (n as usize, k as usize);
        const MOD: i32 = 1000_000_000 + 7;
        let mut dp = vec![vec![0_i32; k+1]; n+1];
        let mut sum_dp = vec![vec![0_i32; k+1]; n+1];
        // 初始化, k=1时,
        for i in 1..=n {
            dp[i][1] = (dp[i-1][1] + ( i as i32 - 1 )) % MOD ;
            sum_dp[i][1] = (sum_dp[i-1][1] + dp[i][1] ) % MOD;
        }

        for i in 1..=n {
            for j in 2..=k {
                dp[i][j] = (dp[i-1][j] + sum_dp[i-1][j-1] ) % MOD;
                sum_dp[i][j] = (sum_dp[i-1][j] + dp[i][j]) % MOD;
            }
        }

        dp[n][k]
    }
}
// @lc code=end

struct Solution;