Eat The Beans.cpp

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;
    }
};