分汤000

题目链接

分汤

题目描述

注意

• 没有提供 0ml 的 汤A 和 100ml 的 汤B 这种操作
• 如果汤的剩余量不足以完成某次操作，我们将尽可能分配

解答思路

• 由题意得，首先想到的是动态规划，关键是规律以及终止条件是怎样的
• 由于分汤都是在25的倍数上进行的，所以将n以及分汤的数量上都除以25，方便后续计算
• 定义 f[i][j]为 汤A 剩余 i 毫升，汤B 剩余 j 毫升时的最终概率，如果i和j同时为0，则汤A和汤B同时被分配完，f[i][j]为0.5，如果i为0，则汤A被分配完，f[0][j]为1，如果j为0，则汤B被分配完，f[i][0]为0
• 动态规划由少到多推出n为x时分汤的概率，由于每次分汤都会分4ml，所以在n为1-4、5-8、9-12…的范围内，分汤概率都是相同的。当n为1-4，分汤概率为0.25 * （1 + 1 + 0.5 + 0），其对应着分汤的四种方式，当n为5-8，分汤概率f[i][j]= 0.25×(f[i−4][j]+f[i−3][j−1]+f[i−2][j−2]+f[i−1][j−3])，以此类推，最终可以推出f[n][n]的分汤概率
• 由于返回值在正确答案 0.00001的范围内将被认为是正确的，通过推理可得，当n大于某个值时，汤B先被分配完的概率极低，与1的误差小于 0.00001，所以当n大于某个值时，可以直接返回概率为1.0

代码

方法一：

class Solution {
    public double soupServings(int n) {
        n = (int) Math.ceil((double) n / 25);
        // 当n很大的时候，汤B先被分配完的概率基本为0
        if (n >= 179) {
            return 1.0;
        }
        double[][] dp = new double[n + 1][n + 1];
        // 汤A和汤B同时分配完的dp为0.5
        dp[0][0] = 0.5;
        // 将汤A先被分配完的dp都设置为1
        for (int i = 1; i <= n; i++) {
            dp[0][i] = 1.0;
        }
        // 从1开始，若i为0则汤A已经被分配完，dp值为1
        for (int i = 1; i <= n; i++) {
            // 从1开始，若j为0则汤B已经被分配完，dp值为0
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[Math.max(0, i - 4)][j] + dp[Math.max(0, i - 3)][Math.max(0, j - 1)] + dp[Math.max(0, i - 2)][Math.max(0, j - 2)] + dp[Math.max(0, i - 1)][Math.max(0, j - 3)]) / 4.0;
            }
        }
        return dp[n][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

关键点

• 找到求分汤概率的规律
• 返回值在正确答案 0.00001的范围内将被认为是正确的，找到在某个临界点处可以认为汤A先被分配完的概率一定为0
• 动态规划的思路