Giả sử chúng ta có n điểm trên một đoạn thẳng, trong đó điểm thứ i (từ 0 đến n-1) ở vị trí x =i, chúng ta phải tìm số cách có thể vẽ đúng k đoạn thẳng không trùng nhau sao cho mỗi phân đoạn bao gồm hai hoặc nhiều điểm. Các điểm cuối của mỗi đoạn thẳng phải có tọa độ tích phân. K đoạn thẳng không nhất thiết phải bao phủ tất cả n điểm đã cho và chúng có thể chia sẻ điểm cuối. Nếu câu trả lời quá lớn, thì trả về kết quả mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là n =4 k =2, thì đầu ra sẽ là 5 vì chúng ta có thể thực hiện năm khả năng [(0 đến 2), (2 đến 3)], [(0 đến 1), (1 đến 3)], [(0 đến 1), (2 đến 3)], [(1 đến 2), (2 đến 3)] và [(0 đến1), (1 đến 2)]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- m:=10 ^ 9 + 7
- n:=n - 1
- Định nghĩa một hàm dp (). Điều này sẽ đưa tôi, được bảo hiểm, j
- nếu tôi giống n, thì
- trả về true nếu j giống với k, ngược lại là false
- nếu j> k, thì
- ans:=dp (i + 1, False, j) + dp (i + 1, True, j + 1)
- nếu được đề cập là đúng, thì
- ans:=ans + dp (i + 1, True, j)
- return ans mod m
- Từ phương thức chính trả về dp (0, False, 0)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
4, 2
Đầu ra
5