New 21 Game

https://leetcode.com/problems/new-21-game/description/

풀기 전

처음에 던질때는 1부터 maxPts까지 확률이 모두 1/maxPts다.

두 번째 던질 때는 어떨까?

처음에 1이 나오고 두 번째에 2가 나왔다면 합은 3이다.

처음에 2가 나오고 두 번째에 1이 나왔다면 그 합도 3이다.

두 번 던져서 3이 나올 확률은 위 두 확률을 더해서 구해야한다.

하지만 처음부터 한 번에 3이 나오는 경우도 있다.

그럼 그것까지 더하면 3이 나올 확률이 구해진다.

이런식으로 구해야되는데 exponential한 전체탐색 방법밖에 생각이 안난다.

어떻게 해야될까.

솔루션 학습

def new21Game(self, N, K, W):
        if K == 0 or N >= K + W: return 1
        dp = [1.0] + [0.0] * N
        Wsum = 1.0
        for i in range(1, N + 1):
            dp[i] = Wsum / W
            if i < K: Wsum += dp[i]
            if i - W >= 0: Wsum -= dp[i - W]
        return sum(dp[K:])

When the game ends, the point is between K and K-1+W
    What is the probability that the the point is less than N?
    - If N is greater than K-1+W, probability is 1
    - If N is less than K, probability is 0

    If W == 3 and we want to find the probability to get a 5
    - You can get a card with value 1, 2, or 3 with equal probability (1/3)
    - If you had a 4 and you get a 1: prob(4) * (1/3)
    - If you had a 3 and you get a 2: prob(3) * (1/3)
    - If you had a 2 and you get a 3: prob(2) * (1/3)
    - If you had a 1, you can never reach a 5 in the next draw
    - prob(5) = prob(4) / 3 + prob(3) / 3 + prob(2) /3

    To generalize:
    The probability to get point K is
    p(K) = p(K-1) / W + p(K-2) / W + p(K-3) / W + ... p(K-W) / W

    let wsum = p(K-1) + p(K-2) + ... + p(K-W)
    p(K) = wsum / W

    dp is storing p(i) for i in [0 ... N]
    - We need to maintain the window by
      adding the new p(i),
      and getting rid of the old p(i-w)
    - check i >= W because we would not have negative points before drawing a card
      For example, we can never get a point of 5 if we drew a card with a value of 6
    - check i < K because we cannot continue the game after reaching K
      For example, if K = 21 and W = 10, the eventual point is between 21 and 30
      To get a point of 27, we can have:
      - a 20 point with a 7
      - a 19 point with a 8
      - a 18 point with a 9
      - a 17 point with a 10
      - but cannot have 21 with a 6 or 22 with a 5 because the game already ends

분석

시간복잡도 O(N)

공간복잡도 O(N)

너무 어렵다..