数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找k个不相交线段集的数量
假设我们在一行上有n个点，其中第i个点（从0到n-1）位于x=i处，我们必须找到可以绘制正好k个不同的不相交线段的方法数量，使得每个线段覆盖两个或多个点。每个线段的端点必须具有整数坐标。k个线段不必覆盖所有给定的n个点，并且它们可以共享端点。如果答案太大，则返回结果模10^9+7。
因此，如果输入类似于n = 4 k = 2，则输出将为5，因为我们可以产生五种可能性[(0到2),(2到3)]，[(0到1),(1到3)]，[(0到1),(2到3)]，[(1到2),(2到3)]和[(0到1),(1到2)]
为了解决这个问题，我们将遵循以下步骤：
- m := 10^9 + 7
- n := n - 1
- 定义一个函数dp()。这将接收i，covered，j作为参数
- 如果i等于n，则
- 如果j等于k则返回true，否则返回false
- 如果j > k，则
- ans := dp(i + 1, False, j) + dp(i + 1, True, j + 1)
- 如果covered为true，则
- ans := ans + dp(i + 1, True, j)
- 返回ans mod m
- 从主方法返回dp(0, False, 0)
示例
让我们看看下面的实现以更好地理解：
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
更新于：2021年10月5日
244 次浏览
广告