2020-02-10 13:24:26
问题描述：
问题求解：
第一次看到这个题目的时候想到的是之前做过的一条概率题，就是那个国际象棋，那条题目的做法是使用dp去对所有留在棋盘的种类进行计数，然后除以总数。所以，我一开始的做法也是这样做的。
但是实际是不对的，问题就是最后得到的解的概率是不等的，所以不能简单的计数符合条件的个数和最后的总个数并相除，如下面的例子。
If you draw 1, then 9, probability is P(1) * P(9) = 0.1 * 0.1 = 0.01
If you draw 10, probability is P(10) = 0.1.(1, 9) and (10) can't be simply regarded as combination candidates for they don't share the same probability
实际是需要使用dp来做的。
public double new21Game(int N, int K, int W) {
if (N < K) return 0;
if (K == 0 || N >= K - 1 + W) return 1;
int maxPoint = K + W - 1;
// probability[i] is probability of getting point i.
double[] probability = new double[maxPoint + 1];
probability[0] = 1;
for (int i = 1; i <= maxPoint; i++) {
for (int w = 1; w <= W; w++) {
if (i - w >= 0 && i - w < K)
probability[i] += probability[i - w] * 1 / W;
}
}
double targetProbability = 0; // Probability of N or less points.
for (int i = K; i <= N; i++) {
targetProbability += probability[i];
}
return targetProbability;
}
上述的代码非常简洁明了，但是会TLE。我们需要对它进行优化。
dp[i] = sum(dp[i - 1] + dp[i - 2] + ... + dp[i - w]) * 1 / W，如果我们使用dp[i]直接去存储sum(dp[0] + dp[1] + dp[2] + ... + dp[i])，那么dp[i] = (dp[i - 1] - dp[i - W - 1]) * 1 / W + dp[i - 1]。
这个里面如果i - w >= K是不能加入计算的，也就是当i >= K + w的时候就需要将部分的和去掉。
public double new21Game(int N, int K, int W) {
if (N < K) return 0;
if (K == 0 || N >= K - 1 + W) return 1;
int max_point = K - 1 + W;
double[] dp = new double[max_point + 1];
dp[0] = 1;
for (int i = 1; i <= max_point; i++) {
if (i - W - 1 < 0) dp[i] = dp[i - 1] * (1.0 / W) + dp[i - 1];
else {
dp[i] = (dp[i - 1] - dp[i - W - 1]) * (1.0 / W) + dp[i - 1];
}
if (i > K) dp[i] -= (dp[i - 1] - dp[K - 1]) * (1.0 / W);
}
return dp[N] - dp[K - 1];
}