在Python中查找k-非重叠线段集数的程序
假设我们在一条线上有n个点，其中第i个点（从0到n-1）位于位置x=i，我们必须找到可以精确绘制k个不同的非重叠线段的方法的数量，使得每个段涵盖两个或更多点。每条线段的端点必须具有积分坐标。k条线段不必覆盖所有给定的n个点，它们可以共享端点。如果答案太大，则返回结果mod10^9+7。
所以，如果输入像n=4k=2，那么输出将是5，因为我们可以有五种可能性[(0to2),(2to3)],[(0to1),(1to3)],[(0to1),(2to3)],[(1to2),(2to3)]和[(0to1),(1to2)]
示例
让我们看看以下实现以获得更好的理解-
def solve(n, k):
m = 10 ** 9 + 7
n -= 1
def dp(i, covered, j):
if i == n:
return j == k
if j > k:
return 0
ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1)
if covered:
ans += dp(i + 1, True, j)
return ans % m
return dp(0, False, 0)
n = 4
k = 2
print(solve(n, k))输入
4, 2输出结果
5
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短