Chương trình đếm số cách để giành chiến thắng tối đa k trò chơi liên tiếp bằng Python

Giả sử chúng ta có hai số n và k. Ở đây n đại diện cho số lượng trò chơi chúng ta sẽ chơi. Chúng ta phải tìm xem có bao nhiêu cách để có thể thắng liên tiếp k hoặc ít ván hơn. Nếu câu trả lời quá lớn, hãy sửa đổi kết quả bằng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =3 k =2, thì đầu ra sẽ là 7, vì những cách khả thi mà chúng ta có thể giành chiến thắng 2 lần trở xuống liên tiếp, là ["LLL", "WLL", "LWL", "LLW", "WWL", "LWW", "WLW"]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=1 ^ 9 + 7
• Định nghĩa một hàm dp (). Điều này sẽ đưa tôi, K
• nếu tôi> =n hoặc K> k, thì
  • trả về true khi K <=k, ngược lại là false
• return dp (i + 1, 0) mod m + dp (i + 1, K + 1) mod m
• Từ phương pháp chính, hãy thực hiện như sau -
• return dp (0, 0) mod m

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 = 1**9 + 7

   def dp(i, K):
      if i >= n or K > k:
         return K <= k
      return dp(i + 1, 0) % m + dp(i + 1, K + 1) % m

   return dp(0, 0) % m

n = 4
k = 2
print(solve(n, k))

Đầu vào

4, 2

Đầu ra

5