[LintCode]Eat The Beans

又是算概率的问题，和New 21 Game这道题很像，如果我们打算直接用数学的方法来算是不好做的，我们还是要分解成subproblem来解决。假设有w个白豆子，r个红豆子，我们用(w, r)表示这个状态：

1. 第一次取豆子之后
• 有w / (w + r)的概率变为(w - 1, r);
• r / (w + r)的概率仍为(w, r)
2. 第二次取豆子之后
• 有w / (w + r) * (w - 1) / (w + r - 1)的概率变为(w - 2, r)
• 有w / (w + r) * r / (w + r - 1)的概率变为(w - 1, r - 1)
• 有r / (w + r) * w / (w + r)的概率变为(w - 1, r)
• 有r / (w + r) * r / (w + r)的概率变为(w , r - 1)

一次类推，我们可以用递归的方法求出(1, 0)的概率。这是top-down的思路，如果我们用bottom-up加dp的思路的话。我们用dp[i][j][k]表示第i次操作之后状态变为(j, k)的概率的话，我们有递推公式：

1. dp[i][j][k] = dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k) + dp[i - 1][j][k] * k / (j + k), if i is odd
2. dp[i][j][k] = dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k) + dp[i - 1][j][k + 1] * (k + 1) / (j + k + 1), if i is even
3. 注意处理一下边界情况，比如j == w, k == r和i == 0 && j == 0 的情况

因为我们每两次至少可以吃掉一个豆子，所以最多2 * (w + r)次操作之后我们可以吃掉全部的豆子。时间复杂度和空间复杂度为O(w * r * (w + r))，代码如下：

	class Solution {
	public:
	/**
	* @param w: The W
	* @param r: The R
	* @return: The answer
	*/
	double eatTheBeans(int w, int r) {
	if (!w)return 0;
	int n = 2 * (w + r);
	//dp[i][j][k] represent the probability we have j white beans and k red beans left
	//after step i
	//dp[i][j][k] = dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k) + dp[i - 1][j][k] * k / (j + k), if i is odd
	//dp[i][j][k] = dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k) + dp[i - 1][j][k + 1] * (k + 1) / (j + k + 1), if i is even
	vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(w + 1, vector<double>(r + 1, 0)));
	dp[0][w][r] = 1.0;
	for (int i = 1; i <= n; ++i)
	{
	for (int j = w; j >= 0; --j)
	{
	for (int k = r; k >= 0; --k)
	{
	if (j == w && k == r)
	{
	dp[i][j][k] = i % 2 ? dp[i - 1][j][k] * k / (j + k) : 0;
	continue;
	}
	if (j == w)
	{
	dp[i][j][k] = i % 2 ? dp[i - 1][j][k] * k / (j + k) : dp[i - 1][j][k + 1] * (k + 1) / (j + k + 1);
	continue;
	}
	if (k == r)
	{
	dp[i][j][k] = i % 2 ? dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k) + (!j && !k ? 0 : dp[i - 1][j][k] * k / (j + k)) :
	dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k);
	continue;
	}
	dp[i][j][k] = i % 2 ? dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k) + (!j && !k ? 0 : dp[i - 1][j][k] * k / (j + k)) :
	dp[i - 1][j + 1][k] * (j + 1) / (j + 1 + k) + dp[i - 1][j][k + 1] * (k + 1) / (j + k + 1);
	}
	}
	}
	double res = 0;
	for (int i = 0; i <= n; ++i)res += dp[i][1][0];
	return res;
	}
	};

view raw Eat The Beans.cpp hosted with ❤ by GitHub