[LeetCode]New 21 Game

给定一堆范围为[1, W]的牌，每张等概率抽到。每次抽一张，记录累加和s。如果s大于等于K的话我们停止抽牌，求最后s小于等于N(N >= K)的概率。乍一看是数学题，其实会发现算起来并不容易。或者我们可以用模拟的方法，比如模拟10000次这个过程看小于等于N的概率是多少，但显然不准确。所以我们还是回到分析子问题上来，首先递归的方法很容易想，假设当前和为sum:

• 如果sum > N, return 0
• 如果sum >= K && sum <= N, return 1
• 如果小于K，我们遍历所有的W，那么probability(sum) = 1 / W * probability(sum + 1) + 1 / W * probability(sum + 2) + 1 / W * probability(sum + 3) + ... + 1 / W * probability(sum + W)   

可以看出来这是一个天然的递归。但是时间复杂度太高，为O(W^K)，过不了大的test case。代码如下：

	class Solution {
	public:
	double new21Game(int N, int K, int W) {
	return getProb(0, N, K, W);
	}
	private:
	double getProb(int curr, int N, int K, int W)
	{
	if(curr >= K && curr <= N)return 1.0;
	if(curr > N)return 0;
	double prob = 0;
	for(int i = 1; i <= W; ++i)
	prob += (1.0 / W) * getProb(curr + i, N, K, W);
	return prob;
	}
	};

view raw New 21 Game_recursion.cpp hosted with ❤ by GitHub

一个优化就是用memorization，避免重复的计算。对于每一个sum我们存下来计算的结果，空间复杂度O(N)，时间复杂度理应也是O(N)但是并过不了全部的test case。代码如下：

	class Solution {
	public:
	double new21Game(int N, int K, int W) {
	return getProb(0, N, K, W);
	}
	private:
	unordered_map<int, double> memo;
	double getProb(int curr, int N, int K, int W)
	{
	if(curr >= K && curr <= N)return 1.0;
	if(curr > N)return 0;
	if(memo.find(curr) != memo.end())return memo[curr];
	double prob = 0;
	for(int i = 1; i <= W; ++i)
	prob += (1.0 / W) * getProb(curr + i, N, K, W);
	memo[curr] = prob;
	return prob;
	}
	};

view raw New 21 Game_recursion_memo.cpp hosted with ❤ by GitHub

DP的方法可以解决这道问题，假设我们计算s = x的概率，那么有以下两种情况：

• 如果x <= W, 那么除了我们可以通过x - 1, x - 2 ... 1抽取1, 2 ... x - 1到达x之外，我们还可以直接抽到x。但是注意x - 1不能大于K，否则我们最大只取到K，因为大于等于K的时候我们停止抽牌
• 如果x > W, 我们不可能直接抽到x。所以我们只能通过x - 1, x -2...x - Wd到达x。同样x - 1不能大于K。

我们用dp[i]表示和为i的概率。所以我们根据这个得到dp公式：

• dp[i] = dp[1] / W + dp[2] / W + ... + dp[min(K - 1, i - 1)] / W + 1.0 / W, if i <= W
• dp[i] = dp[i - W] / W + dp[i - W + 1] / W + ... + dp[min(i - 1, K - 1)] / W, if i > W

我们不用每次去找i的前W个，我们动态地维护区间和即可。时间空间复杂度均为O(n)，代码如下：

	class Solution {
	public:
	double new21Game(int N, int K, int W) {
	if (!K)return 1.0;
	if (N < K || N >= K + W)return 0;
	//dp[i] represent the possibility that the sum is equal to i
	//dp[i] = dp[1] / W + dp[2] / W + ... + dp[min(K - 1, i - 1)] / W + 1.0 / W, if i <= W
	//dp[i] = dp[i - W] / W + dp[i - W + 1] / W + ... + dp[min(i - 1, K - 1)] / W, if i > W
	//res = sum(dp[K]...dp[N])
	vector<double> dp(N + 1, 0);
	double sum = 0, res = 0;
	for (int i = 1; i <= N; ++i)
	{
	dp[i] = i <= W ? sum / W + 1.0 / W : sum / W;
	if (i >= K)res += dp[i];
	if (i < K)sum += dp[i];
	if (i - W > 0)sum -= dp[i - W];
	}
	return res;
	}
	};

view raw New 21 Game.cpp hosted with ❤ by GitHub