[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))，代码如下：