資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告