고유한 게임을 하고 있고 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 반환
-
-
return dp(경로 + 1) − (dp(경로 + h + 1) − dp(경로 + 1)) / h
-
-
주요 기능에서 다음을 수행하십시오 -
-
k가 0이면
-
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