LintCode题解|Twitter 面试题：Eat the Beans

题目描述

一个袋子里有W个白豆子，R个红豆子。第一步：随机摸一个豆子，摸到白豆子直接吃，摸到红豆子，放回去。第二步：随机再摸一豆子，不管是红是白，都吃。然后重复第一步和第二步，问最后一个豆子是白豆子的概率。

思路点拨

考虑dp[i][j]表示剩下i个白豆子，j个红豆子的概率，则根据题意有两种转移。

考点分析

dp[i][j]表示当前剩下i颗白豆子j颗红豆子的概率，dp[w][r] =1，由于第二步必定会吃一颗豆子，所以执行(w + r) * 2步一定可以把所有的豆子吃完，考虑再加一维，dp[i][j][k]表示当前执行到第i步，剩下j颗白豆子k颗红豆子的概率，然后对应对于每一步就可以转移了。

九章参考程序

www.jiuzhang.com/solution/ea…

/**
* 本参考程序来自九章算法，由 @斌助教 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param w: The W
     * @param r: The R
     * @return: The answer
     */
    public double eatTheBeans(int w, int r) {
        // Write your code here
        double[][][] dp = new double[281][71][71];
        int n = (w + r) * 2;
        for(int i = 0; i <= n; i++) {
            dp[i] = new double[71][71];
            for(int j = 0; j <= w; j++) {
                dp[i][j] = new double[71];
                for(int k = 0; k <= r; k++) {
                    dp[i][j][k] = 0;
                }
            }
        }
        dp[0][w][r] = 1;
        if(w == 1 && r == 0) {
            return dp[0][w][r];
        }
        for(int i = 1; i <= n; i++) {
            for(int j = w; j >= 0; j--) {
                for(int k = r; k >= 0; k--) {
                    if(j + k == 0) {
                        continue;
                    }
                    if(dp[i - 1][j][k] != 0) {
                        if(i % 2 == 1) {
                            if(j - 1 >= 0) {
                                dp[i][j - 1][k] += 1.0 * j / (j + k) * dp[i - 1][j][k];
                            }
                            dp[i][j][k] += 1.0 * k / (j + k) * dp[i - 1][j][k];
                        } else {
                            if(j - 1 >= 0) {
                                dp[i][j - 1][k] += 1.0 * j / (j + k) * dp[i - 1][j][k];
                            }
                            if(k - 1 >= 0) {
                                dp[i][j][k - 1] += 1.0 * k / (j + k) * dp[i - 1][j][k];
                            }
                        }
                    }
                }
            }
        }
        double ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += dp[i][1][0];
        }
        return ans;
    }
}