342. Number of Sets of K Non-Overlapping Line Segments

MediumDynamic Programming

Given `n` points on a 1-D plane, where the `i`th 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`.

Examples

Input: 4 2

Output: 5

Explanation: The 5 ways to draw 2 non-overlapping segments over points 0..3: {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Constraints

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

Run checks all cases above. Submit evaluates all test cases.