LC 837. New 21 Game (概率)

link

 参考@vividlau

https://leetcode.com/problems/new-21-game/discuss/220949/Python-3-Memorize-DFS-from-O(KW%2BW)-to-O(K-%2B-W)

class Solution {
public:
    double memo[10000];
    double new21Game(int N, int K, int W) {
        for(int i=0;i<10000;i++) memo[i]=-1.0;
        return dfs(0,W,K,N);
        
    }

    double dfs(int cur, int W, int K, int N){
        if(cur==K-1){
            if(N-K+1>W) return 1.0;
            return 1.0*(N-K+1)/W;
        }
        if(cur>=K){
            if(cur<=N) return 1.0;
            else return 0.0;
        }
        if(memo[cur]!=-1.0) return memo[cur];
        double res=0.0;
        res=dfs(cur+1,W,K,N)+1.0/W*(dfs(cur+1,W,K,N)-dfs(cur+1+W,W,K,N));
        return memo[cur]= res;
    }
};