LeetCode每日一题——808. 分汤

简介: 有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作:

题目

有 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。返回值在正确答案 10-5 的范围内将被认为是正确的。

示例

示例 1:

输入: n = 50

输出: 0.62500

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

示例 2:

输入: n = 100

输出: 0.71875

提示:

0 <= n <= 10^9

思路

动态规划:

首先,由于四种分配操作都是 25 的倍数,因此我们可以将 n 除以 25(如果有余数,则补 1),并将四种分配操作变为 (4,0),(3,1),(2,2),(1,3),且每种操作的概率均为 0.25。

  • dp数组定义为:dp[i][j]表示汤A还剩i份,汤B还剩j份求得答案的概率(也就是 汤A 先分配完的概率 + 汤A和汤B 同时分配完的概率 / 2)
  • 状态转移方程为

2345_image_file_copy_11.jpg

  • 边界条件为:

2345_image_file_copy_12.jpg

最后,通过计算和观察可以发现当n>179*25时,答案都和1十分接近,所以之后的所有答案都直接返回1即可。

题解

class Solution:
    def soupServings(self, n: int) -> float:
      # n做预处理
        n = (n + 24) // 25
        # 后面所有情况
        if n >= 179:
            return 1.0
        # 动态规划状态转移过程
        dp = [[0.0] * (n + 1) for _ in range(n + 1)]
        dp[0] = [0.5] + [1.0] * n
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] +
                            dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]) / 4
        return dp[n][n]


目录
相关文章
|
4天前
|
存储 机器学习/深度学习 人工智能
云栖 2025|阿里云 Qwen3 系列领衔:AI 模型全栈突破与开发者落地指南
阿里云发布Qwen3全栈AI体系,七大模型升级、性能全球领先,开源生态稳居第一。从底层基建到开发工具链全面优化,助力企业高效落地AI应用,共建超级AI云生态。
352 11
|
数据采集 安全
主动扫描和被动扫描
在扫描器中输入目标域名或者URL用爬虫模块爬取所有链接,对GET、POST等请求进行参数变形和污染,进行重放测试,然后依据返回信息中的状态码、数据大小、数据内容关键字等去判断该请求是否含有相应的漏洞。
1093 0
主动扫描和被动扫描
|
6月前
|
监控 安全 定位技术
企业安全生产培训,这么做才有效
安全培训是企业生存的底线,而非“面子工程”。2024年某企业因新员工未完成安全培训引发事故被罚1.2万元,凸显了安全培训的重要性。本文探讨了安全培训在预防事故、法律合规、提升自救能力及减少损失中的关键作用,并提出构建分层分类培训体系、利用技术手段(如二维码)提高效率、打造全员参与的安全文化等方法。通过低成本工具如草料二维码,企业可实现签到、课件学习、承诺书签署和安全宣教等功能,推动数字化转型与安全管理升级。
|
10月前
|
存储 缓存 算法
RAID 的镜像是一种冗余技术
镜像是冗余技术的一种,通过在不同磁盘上创建数据的完整副本,提供数据保护。这种方法无需额外计算和校验,故障恢复迅速,支持并发读取,提高读I/O性能,但写入性能受影响。镜像技术虽提供高数据安全性,却需双倍存储空间,成本较高,适用于关键数据保护。此外,镜像可通过“拆分”实现几乎零备份窗口的数据备份。
214 4
|
Docker Windows 容器
Windows 2016 安装 Docker
Windows 2016 安装 Docker
146 0
|
机器学习/深度学习 人工智能 自然语言处理
【A I 软件开发】一文讲清交互应用的实现原理
【A I 软件开发】一文讲清交互应用的实现原理
577 0
|
数据采集 机器学习/深度学习 算法
力扣79题:单词搜索
力扣79题:单词搜索
|
存储 Python Windows
轻松学会openpyxl库,Python处理Excel有如神助
轻松学会openpyxl库,Python处理Excel有如神助
545 0
|
开发工具 git
阿里云部署 ChatGLM2-6B 与 langchain+chatGLM
阿里云部署 ChatGLM2-6B 与 langchain+chatGLM
604 1
|
编解码 JavaScript PHP
文件上传绕过的常见方式
文件上传绕过的常见方式
294 0