题目：分汤

有A和B两种类型的汤。一开始每种类型的汤有N毫升。有四种分配操作：
提供 100ml 的汤A 和 0ml 的汤B。
提供 75ml 的汤A 和 25ml 的汤B。
提供 50ml 的汤A 和 50ml 的汤B。
提供 25ml 的汤A 和 75ml 的汤B。
当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为0.25的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。
注意不存在先分配100 ml汤B的操作。
需要返回的值：汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。

示例:

输入: N = 50
输出: 0.625
解释:
如果我们选择前两个操作，A将首先变为空。
对于第三个操作，A和B会同时变为空。
对于第四个操作，B将首先变为空。
所以A变为空的总概率加上A和B同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

注释:

0 <= N <= 10^9。
返回值在10^-6的范围将被认为是正确的。

来源：力扣（LeetCode）第808题

链接：https://leetcode-cn.com/problems/soup-servings

分析：

动态规划题,也可以用dfs。这道题使用dfs更加的好，因为不用判断数组越界的情况。
声明两个状态，一个是A的剩余量，一个是B的剩余量。

代码：

class Solution {
public double soupServings(int N) {
    if (N > 4450) return 1.0; // 如果不加，LeetCode会超出内存限制。
    int cnt = (int)Math.ceil(N / 25.0); // N太大了，由于每一个选择都是25的倍数，因此最多要分cnt次就能出现0的情况。
    double[][] dp = new double[cnt+1][cnt+1];// 左边是A汤剩余量，右边是B汤剩余量。
    Arrays.fill(dp[0], 1); // 如果A先到0，那么就加1次，同样如果B先到0，那么就是0。
    dp[0][0] = 0.5; // 如果同时到0，那么就是概率的一半。
    for (int i = 1; i <= cnt; i++) {
        // 除以25以后，100就是4,75就是3,50是2,25是1。
        int i1 = i - 4 > 0 ? i - 4 : 0, i2 = i - 3 > 0 ? i - 3 : 0;
        int i3 = i - 2 > 0 ? i - 2 : 0, i4 = i - 1 > 0 ? i - 1 : 0;
        for (int j = 1; j <= cnt; j++) {
            int j1 = j - 1 > 0 ? j - 1 : 0, j2 = j - 2 > 0 ? j - 2 : 0, j3 = j - 3 > 0 ? j - 3 : 0;
            //dp内存的是你当前的四种情况有几种是A先0,有几种是B先0,有几种是同时为0。
            //同时为0要除以2，所以dp[0][0]=0.5。B先0就是0，A先0就是1。四种情况加起来除以4就是要求的概率。
            dp[i][j] = 0.25 * (dp[i1][j] + dp[i2][j1] + dp[i3][j2] + dp[i4][j3]);
        }
    }
    return dp[cnt][cnt];
}
}

dfs + 记忆化搜索

class Solution {
double[][] memo;
public double soupServings(int N) {
    if (N > 4450) return 1.0;
    int cnt = (int)Math.ceil(N / 25.0);
    memo = new double[cnt+1][cnt+1];
    return dfs(cnt, cnt);
}

public double dfs(int A, int B) {
    if (A <= 0 && B <= 0) return 0.5;
    if (A <= 0) return 1;
    if (B <= 0) return 0;
    if (memo[A][B] != 0) return memo[A][B];
    double ans = 0;
    ans = 0.25 * (dfs(A - 4, B) + dfs(A - 3, B - 1) + dfs(A - 2, B - 2) + dfs(A - 1, B - 3));
    memo[A][B] = ans;
    return ans;
}
}