动态规划
f[i]为点数到达i的概率，这里有两种思考方式：
第一种考虑f[i]由f[i-1],f[i-2]…f[i-W]转移过来；
第二种考虑用f[i]去更新f[i+1],f[i+2]…f[i+W]。
优化方法：
第一种的话需要快速求出一段的总和，可以用滑动窗口来优化，要注意当i大于等于K的时候是不可以给tot贡献值的，因为只有i小于K的时候我们才可以继续摸牌；
第二种需要快速进行区间修改操作，可以用差分数组来优化。

ps.代码里注释掉的那部分就是无优化版的
滑动窗口优化版代码

class Solution {
public:
    double new21Game(int N, int K, int W) {
        double f[20005]={0};
        double p=1.0/W,tot=0;
        f[0]=1;
        int l=0,r=-1;
        for(int i=0;i<=K-1+W;i++)
        {
            f[i]+=p*tot;
            if(i<K) tot+=f[i];
            r=i;
            while(r-l+1>W) tot-=f[l++];
        }
        double ans=0;

        for(int i=K;i<=N;i++)
            ans+=f[i];
        return ans;
    }
};

差分数组优化版代码

class Solution {
public:
    double new21Game(int N, int K, int W) {
        N++,K++;
        double f[20015]={0};
        double p=1.0/W,x;
        f[1]=1,f[2]=-1;
        for(int i=1;i<=K-1;i++)
        {
            f[i]+=f[i-1];
            x=p*f[i];
            int l=i+1,r=i+W;
            f[l]+=x,f[r+1]-=x;
            /*
            for(int j=1;j<=W;j++)
                f[i+j]+=x;
            */
        }
        double ans=0;
        for(int i=K;i<=N;i++)
            f[i]+=f[i-1],ans+=f[i];
        return ans;
    }
};