題目描述

一個袋子里有W個白豆子，R個紅豆子丧没。第一步： 隨機摸一個豆子鹰椒，摸到白豆子直接吃，摸到紅豆子呕童，放回去漆际。第二步：隨機再摸一豆子，不管是紅是白夺饲，都吃奸汇。然后重復第一步和第二步施符，問最后一個豆子是白豆子的概率。

思路點撥

考慮dp[i][j]表示剩下i個白豆子擂找，j個紅豆子的概率戳吝，則根據(jù)題意有兩種轉移。

考點分析

dp[i][j]表示當前剩下i顆白豆子j顆紅豆子的概率贯涎，dp[w][r] =1听哭，由于第二步必定會吃一顆豆子，所以執(zhí)行(w + r) * 2步一定可以把所有的豆子吃完柬采，考慮再加一維欢唾，dp[i][j][k]表示當前執(zhí)行到第i步，剩下j顆白豆子k顆紅豆子的概率粉捻，然后對應對于每一步就可以轉移了。

參考程序

http://www.jiuzhang.com/solution/eat-the-beans/

/**
* 本參考程序來自九章算法斑芜，由 @斌助教 提供肩刃。版權所有，轉發(fā)請注明出處杏头。
* - 九章算法致力于幫助更多中國人找到好的工作，教師團隊均來自硅谷和國內(nèi)的一線大公司在職工程師。
* - 現(xiàn)有的面試培訓課程包括：九章算法班优训，系統(tǒng)設計班搁吓，算法強化班，Java入門與基礎算法班寓娩，Android 項目實戰(zhàn)班叛氨，
* - Big Data 項目實戰(zhàn)班，算法面試高頻題班, 動態(tài)規(guī)劃專題班
* - 更多詳情請見官方網(wǎng)站：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;
    }
}