[Python/C++] Posterior probability + climbing stairs
The question ask us to play a game:\n\nlet X = 0\nwhile X <= K:\n\tX += draw a sample from W, where W = [1, 10]\n\nand figure out that, at the end of the game, 
The question ask us to play a game:\n```\nlet X = 0\nwhile X <= K:\n\tX += draw a sample from W, where W = [1, 10]\n```\nand figure out that, at the end of the game, what\'s the probability \n```\nP( X \u2264 N | X \u2265 K) \uFF1F\n```\n\nFor each probablity X = i, it is the relation:\n```\nP( X = i ) = P( X = i - 1) + P ( X = i - 2 ) + .... P ( X = i - W ), where i > W\n```\n\nFor example, \n```\nP( X = 0 ) = 1                           # Initial state, no need to draw cards\nP( X = 1 ) = 1/W                         # Only 1 out of W chance in getting X = 1\nP( X = 2 ) = 1/W + 1/W^2                 # We can draw a 2 or two 1s.\nP( X = 3 ) = 1/W + 1/W^2 + 1/W^2 + 1/W^3 # We can draw a 3, a (2,1), a (1,2), and two 1s. \nP (X = 4 ) = ( P( X = 3 ) + P( X = 2 ) ) / W\n.etc\n```\n\nThe above sequence is similar to climbing stairs or Fibo series, except, this time, we would be updating probabilities.\n\nThus, we can represent the above probabilities with an array of length ```N + 1``` and add up the probabilities between ```[K, N]```. \n\n\n**Python**\n```\nclass Solution:\n    def new21Game(self, N: int, K: int, W: int) -> float:\n        if K == 0 or N >= K + W:\n            return 1\n        \n        dp = [1] + [0] * N\n        res = 0\n        wsum = 1.0\n        for i in range(1, N+1):\n            dp[i] = wsum / W\n            if i < K:\n                wsum += dp[i]\n            else:\n                res += dp[i]\n                \n            if i - W >= 0:\n                wsum -= dp[i-W]\n        \n        return res\n```\n\n**C++**\n```\nclass Solution {\npublic:\n    double new21Game(int N, int K, int W) {\n        if(K == 0 or N >= K + W)\n            return 1;\n        \n        vector<double> dp(N + 1, 0);\n        dp[0] = 1;\n        \n        double wsum = 1.0;\n        double res = 0;\n        for(int i=1; i<N+1; i++) {\n            dp[i] = wsum / double(W);\n            if(i < K)\n                wsum += dp[i];\n            else\n                res += dp[i];\n            \n            if(i-W >= 0)\n                wsum -= dp[i-W];\n        }\n        \n        return res;\n    }\n};\n```\n
[]