1621. Number of Sets of K Non-Overlapping Line Segments¶
题目信息¶
- 题号:
1621
- 难度:
Medium
- 主题:
动态规划、组合计数
- 原题:
- 重点:
在线上
n个点间选择k条正长度线段,内部不能重叠但端点可以共用
题目重述¶
点编号为 0 到 n-1。统计选择恰好 k 条线段的方法数,每条线段连接两个不同点,任意两条线段不能在正长度区间上重叠。结果对 10^9+7 取模。
自建示例¶
输入:n = 4, k = 2
输出:5
解释:共享端点允许,因此除两组分离线段外,还包含多种首尾相接方案。
输入:n = 3, k = 1
输出:3
解释:可选择端点对 (0,1)、(0,2)、(1,2)。