空山新雨后 天气晚来秋
先说明，这次的题解我会写的非常详细，因为这是我见过的非常动态规划的题。。。
这种题一看就是dp题，dp题我就喜欢先暴力，再慢慢推导出转移公式。。。但这次我却暴力不出来了，发现枚举的每一种和并不是等概率的。。。
然后就写出来错误代码：
class Solution {
private:
void dfs(int sum, int k, int n, int w, int &cnt, int &total) {
if (sum >= k) {
total++;
if (sum <= n) cnt++;
return ;
}
for (int i = 1; i <= w; i++) {
dfs(sum + i, k, n, w, cnt, total);
}
}
public:
double new21Game(int N, int K, int W) {
int cnt = 0;
int total = 0;
dfs(0, K, N, W, cnt, total);
return ((double) cnt) / total;
}
};
最后想了想，每个样本都不是等概率的，那就加上概率就好了，可以确定的是每次抽牌是等概率的。
class Solution {
private:
void dfs(int N, int K, int W, int sum, int cnt, double &ans) {
if (K <= sum) {
if (sum <= N)
ans += pow(1.0 / W, cnt);
return ;
}
for (int i = 1; i <= W; i++) {
dfs(N, K, W, sum + i, cnt + 1, ans);
}
}
public:
double new21Game(int N, int K, int W) {
double ans = 0;
dfs(N, K, W, 0, 0, ans);
return ans;
}
};
但是会超时，再想想怎么做优化～。
写代码前，进行公式推导。。。
这里假设dp(x)表示在某次抽牌时，和为x的概率，那么就有x < k时：
其中dp(0) = 1.0，dp(1) = 1 / W。那么在x >= K时，公式就转变成：
于是最终公式就变成了：
\[dp(x) = \begin {cases} [dp(x - W) + ... + dp(x - 1) ] * \frac {1} {W}, \quad &x < K \\ [dp(x - W) + ... dp(K - 1)] * \frac {1} {W}, \quad &x \geq K \end {cases}\]利用动态规划进行非递归：
class Solution {
public:
double new21Game(int N, int K, int W) {
if (K == 0 || K - 1 + W <= N)
return 1.0;
double *dp = new double[N + 1];
dp[0] = 1.0;
for (int i = 1; i <= N; i++) {
for (int j = max(i - W, 0); j < i; j++) {
if (j < K)
dp[i] += (1.0 / W) * dp[j];
}
}
double ans = 0.0;
for (int i = K; i <= N; i++)
ans += dp[i];
delete[] dp;
return ans;
}
};
残酷的事情就是这样子会超时。。。复杂度是O(N2).
前面的思路虽然可行，但是显然不够动态规划。。。举个例子，对于N = 21, K = 17, W = 10这个输入，在计算dp[16]的时候，是直接循环，然后：
但实际里面很大一部分在计算dp[15]的时候已经计算过了，实际上可以：
然后从特例推导到整个过程就是：
\[dp(x) = dp(x - 1) - dp(x - W) * \frac {1} {W} + dp(x - 1) * \frac {1} {W}\]加上特殊情况的处理，公式可以变成：
\[dp(x) = \begin {cases} dp(x - 1) - dp(x - W - 1) * \frac {1} {W} + dp(x - 1) * \frac {1} {W}, \quad & W + 1 \leq x \leq K \\ dp(x - 1) + dp(x - 1) * \frac {1} {W}, \quad & x \leq K \\ dp(x - 1) - dp(x - W - 1) * \frac {1} {W}, \quad & W + 1 \leq x\\ dp(x - 1), \quad & other \end {cases}\]总的来说，可以把[i - W, i - 1]这个宽度当成一个窗口，如果窗口能完美被[0, K]的范围包括，就是上述推导的情况。。。然后分别就是考虑窗口左侧存在小于0的情况以及窗口右侧会大于K的情况。
基于上述推导，就能写出代码了。
class Solution {
public:
double new21Game(int N, int K, int W) {
if (K == 0 || K - 1 + W <= N)
return 1.0;
double *dp = new double[N + 1];
dp[0] = 1.0;
dp[1] = 1.0 / W;
for (int i = 2; i <= N; i++) {
if (i - W - 1 >= 0 && i <= K)
dp[i] = dp[i - 1] - dp[i - W - 1] * 1.0 / W + dp[i - 1] * 1.0 / W;
else if (i <= K)
dp[i] = dp[i - 1] + dp[i - 1] * 1.0 / W;
else if (i - W - 1 >= 0)
dp[i] = dp[i - 1] - dp[i - W - 1] * 1.0 / W;
else
dp[i] = dp[i-1];
}
double ans = 0.0;
for (int i = K; i <= N; i++)
ans += dp[i];
delete[] dp;
return ans;
}
};
