1. 原理觉得应该有数学公式，但是没有。自己退出来的是错的。说明不能直接从k-w+1开始推，前面是有概率影响的。
2. dp[i] = (dp[i+w] +....dp[i+1])/w,这是公式，也就是倒着推的，这是没想到的。把想要的结果看出概率1，不想要的看成0，倒推从0开始的概率。
为什么这么推呢？因为正着推很费力气，不确定方向。
3. 还有一个问题，就是范围。最大不超过min(n,w+k-1), 因为不超过n，切不小于k，所以取二者较小的。
4. 至于O（n）的优化，就是把for提取出来。amount要时刻刷新值，这个错了好久。
5. 这是一个很好的题目。开拓眼界
代码如下：
class Solution {
public double new21Game(int n, int k, int w) {
double[] dp = new double[k+w];
int small = Math.min(n,k+w-1);
for(int i = k; i <= small; i++){
dp[i] = 1;
}
for(int i = small+1; i <= k+w-1; i++){
dp[i] = 0;
}
double amount = 0;
for(int j = k; j <= w+k-1; j++){
amount+=dp[j];
}
if(k-1>=0){
dp[k-1] = amount/w;
}
for(int i = k-2; i >=0; i-- ){
amount = amount-dp[w+i+1] + dp[i+1];
dp[i] = amount/w;
}
return dp[0];
}
}
