สมมติว่าเรากำลังเล่นเกมที่ไม่เหมือนใครและมีค่าสามค่าคือ n, k และ h เราเริ่มต้นจาก 0 คะแนน จากนั้นเราสามารถสุ่มเลือกตัวเลขระหว่าง 1 ถึง h (รวม) แล้วเราจะได้คะแนนนั้นมาก เราหยุดเมื่อเราได้คะแนนขั้นต่ำ k คะแนน เราต้องหาความน่าจะเป็นที่เรามี n คะแนนหรือน้อยกว่านั้น ที่นี่สามารถเลือกหมายเลขใดก็ได้แบบสุ่มและผลลัพธ์ทั้งหมดมีความน่าจะเป็นเท่ากัน
ดังนั้น หากอินพุตเป็น n =2, k =2, h =10 เอาต์พุตจะเป็น 0.11
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน dp() นี่จะเป็นเส้นทาง
-
ถ้าเส้นทางเหมือนกับ k − 1 แล้ว
-
ผลตอบแทน (ขั้นต่ำของ n − k + 1 และ h) / h
-
-
ถ้าเส้นทาง> n แล้ว
-
คืนค่า 0
-
-
ถ้าเส้นทาง>=k แล้ว
-
กลับ 1
-
-
กลับ dp(เส้นทาง + 1) − (dp(เส้นทาง + ชั่วโมง + 1) − dp(เส้นทาง + 1)) / ชั่วโมง
-
-
จากหน้าที่หลัก ให้ทำดังต่อไปนี้ -
-
ถ้า k เป็นศูนย์ แล้ว
-
กลับ 1
-
-
ถ้า n
-
คืนค่า 0
-
-
กลับ dp(0)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, n, k, h): if not k: return 1 if n < k: return 0 def dp(path): if path == k− 1: return min((n− k + 1), h) / h if path > n: return 0 if path >= k: return 1 return dp(path + 1)− (dp(path + h + 1)− dp(path + 1)) / h return dp(0) ob = Solution() print(ob.solve(2,2,10))
อินพุต
2,2,10
ผลลัพธ์
0.11
