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

题目信息

题号:

1621

难度:

Medium

主题:

动态规划、组合计数

原题:

LeetCode 1621

重点:

在线上 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)。