number-of-sets-of-k-non-overlapping-line-segments

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given <code>n</code> points on a 1-D plane, where the <code>ith</code> point (from <code>0</code> to <code>n-1</code>) is at <code>x = i</code>, find the number of ways we can draw exactly <code>k</code> non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The <code>k</code> line segments do not have to cover all <code>n</code> points, and they are allowed to share endpoints.

Return the number of ways we can draw <code>k</code> non-overlapping line segments. Since this number can be huge, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/07/ex1.png" style="width: 179px; height: 222px;" />
<pre>
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)}.
</pre>

Example 2:

<pre>
Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.
</pre>

Example 3:

<pre>
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 109 + 7 gives us 796297179.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= n-1</code></li>
</ul>

numberOfSets

Number of Sets of K Non-Overlapping Line Segments

Math

Dynamic Programming

Combinatorics

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

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

 

示例 1：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/17/ex1.png" style="width: 179px; height: 222px;" />
<pre>
输入：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)} 。</pre>

示例 2：

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

示例 3：

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

示例 4：

<pre>
输入：n = 5, k = 3
输出：7
</pre>

示例 5：

<pre>
输入：n = 3, k = 2
输出：1</pre>

 

提示：

<ul>
	<li><code>2 <= n <= 1000</code></li>
	<li><code>1 <= k <= n-1</code></li>
</ul>