## Wednesday, May 30, 2018

### LeetCode 837 - New 21 Game

https://leetcode.com/problems/new-21-game/description/
Alice plays the following game, loosely based on the card game "21".
Alice starts with 0 points, and draws numbers while she has less than K points.  During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer.  Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets K or more points.  What is the probability that she has N or less points?
Example 1:
Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation:  Alice gets a single card, then stops.
Example 2:
Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.
Example 3:
Input: N = 21, K = 17, W = 10
Output: 0.73278
Note:
1. 0 <= K <= N <= 10000
2. 1 <= W <= 10000
3. Answers will be accepted as correct if they are within 10^-5 of the correct answer.
4. The judging time limit has been reduced for this question.
https://leetcode.com/problems/new-21-game/discuss/132358/Java-O(K-+-W)-DP-solution-with-explanation
Firstly I came up with a basic DP solution which cost O((K + W) * W) time and it runs TLE:
class Solution {
public double new21Game(int N, int K, int W) {
if (K == 0) {
return 1;
}
int max = K + W - 1;
double[] dp = new double[max + 1];
dp[0] = 1;
for (int i = 1; i <= max; i++) {
for (int j = 1; j <= W; j++) {
if (i - j >= 0 && i - j < K) {
dp[i] += dp[i - j] / W;
}
}
}
double result = 0;
for (int i = K; i <= N; i++) {
result += dp[i];
}
return result;
}
}
Then I realize that the transition equation dp[i] = (dp[i - W] + dp[i - W + 1] + ... + dp[i - 1]) / W could be simplified to dp[i] = (sum[i - 1] - sum[i - W - 1]) / W.
Furthermore, if we use dp[i] to directly represent the sum[i], we can get dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - W - 1]) / W. This equation takes us to the final O(K + W) solution. Just take care with the beginning and the end of the array.
public double new21Game(int N, int K, int W) {
if (K == 0) {
return 1;
}
int max = K + W - 1;
double[] dp = new double[max + 1];
dp[0] = 1;
for (int i = 1; i <= max; i++) {
dp[i] = dp[i - 1];
if (i <= W) {
dp[i] += dp[i - 1] / W;
} else {
dp[i] += (dp[i - 1] - dp[i - W - 1]) / W;
}
if (i > K) {
dp[i] -= (dp[i - 1] - dp[K - 1]) / W;
}
}
return dp[N] - dp[K - 1];
}

https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP
In a word,
dp[i]: probability of get points i
dp[i] = sum(last W dp values) / W
public double new21Game(int N, int K, int W) {
if (K == 0 || N >= K + W) return 1;
double dp[] = new double[N + 1],  Wsum = 1, res = 0;
dp[0] = 1;
for (int i = 1; i <= N; ++i) {
dp[i] = Wsum / W;
if (i < K) Wsum += dp[i]; else res += dp[i];
if (i - W >= 0) Wsum -= dp[i - W];
}
return res;
}

It is clear that the probability that Alice wins the game is only related to how many points x she starts the next draw with, so we can try to formulate an answer in terms of x.
Algorithm
Let f(x) be the answer when we already have x points. Clearly, f(x) = 1.0 when K <= x <= N, and f(x) = 0.0 when x > N.
We can write a recursion, $f(x) = \frac{1}{W}\big( \sum_{i=1}^W f(x+i) \big)$.
With naive dynamic programming, this leads to a $O(K * W + (N-K))$ solution: for each state k < K in decreasing order, we'll use the recursion to calculate f(k), doing $O(W)$ work each time. This is not efficient enough.
However, the sums for f(x) and f(x-1) are related: namely, $f(x) - f(x-1) = \frac{1}{W} \big( f(x+W) - f(x) \big)$. This allows us to calculate f(k-1) from f(k) in $O(1)$ time, by maintaining the numerator $S = \sum_{i=1}^W f(x+i)$.
Note that we can reduce the time complexity to $O(\max(K, W))$ and the space complexity to $O(W)$ by only keeping track of the last $W$ values of dp, but it isn't required.

public double new21Game(int N, int K, int W) {
double[] dp = new double[N + W + 1];
for (int k = K; k <= N; ++k)
dp[k] = 1.0;

double S = Math.min(N - K + 1, W);
for (int k = K - 1; k >= 0; --k) {
dp[k] = S / W;
S += dp[k] - dp[k + W];
}
return dp[0];
}

http://www.cnblogs.com/seyjs/p/9076034.html