เกมสุ่มคะแนน: เริ่ม 0 คะแนน สุ่มเลข 1 ถึง h ได้คะแนนเท่านั้น หยุดเมื่อได้คะแนน ≥ k หาความน่าจะเป็นที่คะแนนสุดท้าย ≤ n
ตัวอย่าง: n=2, k=2, h=10 → 0.11
อัลกอริธึม DP แบบ Top-down
- ฟังก์ชัน
dp(path)คืนความน่าจะเป็นจากคะแนนสะสมpath - Base cases: path==k-1 → min(n-k+1, h)/h; path>n → 0; path≥k → 1
- Recurrence: dp(path+1) - (dp(path+h+1) - dp(path+1))/h
การนำไปใช้
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)) # 0.11
