Chương trình tìm xác suất có n điểm hoặc ít hơn trong Python

Trò chơi: bắt đầu 0 điểm, mỗi lần chọn ngẫu nhiên số từ 1 đến h (đều xác suất), cộng điểm. Dừng khi đạt ít nhất k điểm. Tìm xác suất điểm cuối cùng <= n.

Ví dụ: n=2, k=2, h=10 -> 0.11.

Giải bằng DP đệ quy có memoization ngầm: dp(path) = xác suất từ trạng thái path điểm.

Ví dụ

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))

Đầu vào

2, 2, 10

Đầu ra

0.11