题目描述
LeetCode原题链接：1621. Number of Sets of K Non-Overlapping Line Segments
Given n points on a 1-D plane, where the ith point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.
Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 10^9 + 7.
Example 1:
Input: n = 4, k = 2
Output: 5
Explanation: The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.
Example 2:
Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.
Example 3:
Input: n = 30, k = 7 Output: 796297179 Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10^9 + 7 gives us 796297179.
Constraints:
2 <= n <= 10001 <= k <= n-1
题目分析
这道题可以用动态规划来做，就是状态量会比较多一些，可能不大好理解。题目中给了n和k，那肯定我们先需要一个二维 dp[i][j] ，其中每个位置表示前0～i这些点分成j段有几种分法。这个比较直观，最终的结果就是dp[n-1][k]。现在我们来看对于遍历到的任意一个位置i，(i, 0)这个点和已经出现的线段能组成哪些新的情况，就用example1中的示意图作为例子， 假设当前遍历到了i=2这个位置：
case1: 将上一个位置（即：(1,0)点）的最后一根线段延长到当前位置，此时 (2,0) 成为了上一个位置最后一根线段延长后的新的终点，没有新的线段产生；
case2/case3: 将上一个位置（即：(1,0)点）最后一根线段的终点最为起点，将当前位置 (2,0) 作为终点，产生了一条新的线段（蓝色线段）；
注意这里为啥要把case2和case3分开呢？虽然它们都是以 (1,0) 为起点，(2,0) 为终点产生一条新线段，但由于 (1,0) 点之前的情况不同（空隙or某一线段终点），实际上最终结果是两种不同的情况。由此可见，我们还需要另外一种状态来标记某一点是否是最后一个线段的终点，即是否这个点之前挨着的是空隙。因此再在原有的二维dp数组上增加一个纬度，用来标识这种状态：
- dp[i][j][0]: 前i个点分成j段并且i点不是最后一根线段终点时（最后一根线段没有延伸到i点）有几种分法
- dp[i][j][1]: 前i个点分成j段并且i点是最后一根线段终点时（最后一根线段延伸到了i点）有几种分法
于是结合之前的分析，我们可以得到状态转移方程为：
- dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] （如果不能延伸到 (i,0) 点，那么就要求在上一位置 (i-1,0) 点就要分割成j段）
- dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1] + dp[i-1][j-1][0] （如果能延伸到 (i,0)点，那么分别对应上图中的三种情况）
最后，初始化的时候 dp[0][0][0]=1，其余为0。最终结果返回 dp[n-1][k][0] + dp[n-1][k][1]
代码示例（JS)
1 var numberOfSets = function(n, k) {
2 let mod = 1000000007;
3 let dp = new Array(n);
4 for(let i = 0; i < n; i++) {
5 dp[i] = new Array(k + 1);
6 for(let j = 0; j <= k; j++) {
7 dp[i][j] = new Array(2);
8 dp[i][j].fill(0);
9 }
10 }
11 dp[0][0][0] = 1;
12 for(let i = 1; i < n; i++) {
13 for(let j = 0; j <= k; j++) {
14 dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % mod;
15 dp[i][j][1] = dp[i-1][j][1];
16 if(j > 0) {
17 dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][0] + dp[i-1][j-1][1]) % mod;
18 }
19 }
20 }
21 return (dp[n-1][k][0] + dp[n-1][k][1]) % mod;
22 };