สมมติว่าเรามีตัวเลขสองตัว n และ k ในที่นี้ n หมายถึงจำนวนเกมที่เราจะเล่น เราต้องค้นหาว่าเราจะชนะ k หรือน้อยกว่านั้นได้กี่เกมติดต่อกัน หากคำตอบมีขนาดใหญ่เกินไป ให้แก้ไขผลลัพธ์ด้วย 10^9 + 7
ดังนั้น หากอินพุตเป็น n =3 k =2 เอาต์พุตจะเป็น 7 เนื่องจากวิธีที่เป็นไปได้ที่เราสามารถชนะ 2 ครั้งหรือน้อยกว่าติดต่อกันคือ ["LLL", "WLL", "LWL", "LLW", "WWL", "LWW", "WLW"]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ม :=1^9 + 7
- กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, K
- ถ้า i>=n หรือ K> k แล้ว
- คืนค่า จริง เมื่อ K <=k ไม่เช่นนั้น เท็จ
- ส่งคืน dp(i + 1, 0) mod m + dp(i + 1, K + 1) mod m
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- คืนค่า dp(0, 0) mod m
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
4, 2
ผลลัพธ์
5
