Logical Thinking
Game rule is as follows\n\npoint 0 initially\nwhile (point < K) {\n    draw w  from [1, W] randomly \n    point += w\n}\nprobability(point <= N) ?\n\n> Let\'s o
>**Game rule** is as follows\n```\npoint 0 initially\nwhile (point < K) {\n    draw w  from [1, W] randomly \n    point += w\n}\nprobability(point <= N) ?\n```\n> **Let\'s observe that**\n```\npoint total range [0, K + W - 1]\n```\n> we define `probability[i]` as probability to get i points\nsince all start with point 0 => `probability[0] = 1`\n\n>**Probability transition:**\n```\nBefore we reach point `i`, we draw `w`, i.e., our last point is `i - w` \n\nprobability to get i points = sum(probability to get i - w points * 1 / W) for w can be any of [1, W]\nwhere 0 <= i - w < K\n```\n\n> target probability = sum of prabability to get points [K, N]\n\n> **Note**\n> \n> If K = 10, W = 10\n>draw 1, then 9, probability is P(1) * P(9) = 0.1 * 0.1 = 0.01\n>draw 10, probability is P(10) = 0.1.\n>\n> (1, 9) and (10) can\'t be simply regarded as combination candidates for they don\'t share the same probability.\n\n****\n```\n    public double new21Game(int N, int K, int W) {\n        // Corner cases.\n        if (K == 0) return 1;\n        \n        int maxPoint = K + W - 1;\n        // probability[i] is probability of getting point i.\n        double[] probability = new double[maxPoint + 1];\n        \n        probability[0] = 1;\n        for (int i = 1; i <= maxPoint; i++) {\n            for (int w = 1; w <= W; w++) {\n                if (i - w >= 0 && i - w < K)\n                    probability[i] += probability[i - w] * 1 / W;\n            }\n        }\n        \n        double targetProbability = 0; // Probability of N or less points.\n        for (int i = K; i <= N; i++) {\n            targetProbability += probability[i];\n        }\n        \n        return targetProbability;\n    }\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]