LeetCode 799. 香槟塔：基于动态规划自上而下模拟的题解（leetcode 解题仓库实战解析）

LeetCode 799. 香槟塔基于动态规划自上而下模拟的题解leetcode 解题仓库实战解析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以开源仓库 leetcodeLeetCode 题解集中 problems/799.champagne-tower.md 为核心完整讲解 LeetCode 799「香槟塔」Champagne Tower的题目模型、动态规划思路与可运行的 Python 实现。读完本篇你将掌握一类「按行自上而下递推、溢流均分到下一层」的模拟型 DP 问题解法并能直接复用仓库中的代码模板进行验证与扩展。一、题目回顾香槟塔模型1.1 题目描述我们把玻璃杯摆成金字塔的形状其中第一层有 1 个玻璃杯第二层有 2 个依次类推到第 100 层。每个玻璃杯250ml将盛有香槟。从顶层的第一个玻璃杯开始倾倒一些香槟当顶层的杯子满了任何溢出的香槟都会立刻等流量地流向左右两侧的玻璃杯。当左右两边的杯子也满了就会等流量地流向它们左右两边的杯子依次类推当最底层的玻璃杯满了香槟会流到地板上。例如在倾倒一杯香槟后最顶层的玻璃杯满了。倾倒了两杯香槟后第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后第二层的香槟满了——此时总共有三个满的玻璃杯。在倒第四杯后第三层中间的玻璃杯盛放了一半的香槟它两边的玻璃杯各自盛放了四分之一的香槟。题目要求当倾倒了非负整数杯香槟后返回第i行第j个玻璃杯所盛放的香槟占玻璃杯容积的比例i和j都从 0 开始。1.2 示例说明示例 1输入poured倾倒香槟总杯数 1query_glass杯子的位置列 1query_row行数 1输出0.0解释我们在顶层下标是 (0, 0)倒了一杯香槟后没有溢出因此所有在顶层以下的玻璃杯都是空的。示例 2输入poured 2query_glass 1query_row 1输出0.5解释我们在顶层下标是 (0, 0)倒了两杯香槟后有一杯量的香槟将从顶层溢出位于 (1, 0) 的玻璃杯和 (1, 1) 的玻璃杯平分了这一杯香槟所以每个玻璃杯有一半的香槟。1.3 约束条件poured的范围[0, 10^9]query_glass和query_row的范围[0, 99]二、前置知识动态规划与杨辉三角在深入解题之前需要掌握两个基础知识点这也是原文档明确列出的前置知识动态规划将问题拆分为若干阶段通过阶段之间的状态转移来求解目标。仓库中的专题文章 thinkings/dynamic-programming.md 对 DP 有系统讲解其中明确指出「走楼梯问题」「杨辉三角」等都是可以用递归轻松写出的经典题目并且指出如果递归中存在重复计算重叠子问题那就是使用记忆化递归或动态规划解题的强有力信号。杨辉三角杨辉三角的每一行都是上一行相邻元素之和第i行第j个元素的值与相邻位置之间存在天然的递推关系。香槟塔的溢流均分结构与杨辉三角的数值传播结构高度相似——这也是本题采用二维数组从上到下递推的根本原因。三、解题思路自上而下的模拟3.1 核心思想这道题和杨辉三角问题类似实现的基本思路都是从上到下模拟。如果大家对杨辉三角问题不熟悉建议先复习经典杨辉三角的递推过程因为它同样是动态规划中很经典的问题。由题目可知杯子的数目是第一行一个、第二行两个……第i行i个i 1。因此建立一个二维数组即可。为了简单我们可以建立一个大小为R x R的二维矩阵A其中R为香槟塔的高度。虽然这样的建立方式会造成一半的空间浪费但是题目的条件是query_glass和query_row的范围[0, 99]因此即便如此问题也不大。当然你也可以直接开辟一个100 x 100的矩阵。说明用R x R的二维矩阵A进行模拟时矩阵中只有A[i][0..i]位置被实际使用第i行只有i1个杯子虚线下半部分的空间未被使用也就是「浪费」的空间。这是以空间换实现简单性的典型取舍。3.2 模拟过程接下来只需要按照题目描述进行模拟即可。具体来说先将第一行第一列的杯子注满香槟即A[0][0] poured接下来从上到下、从左到右进行模拟模拟的过程就是计算溢出的容量将溢出的容量平分到下一层的两个酒杯中。只需要平分到下一层即可不用关心下一层满之后的溢出问题因为之后会遍历到并处理下面的代码也会体现这一点。3.3 状态转移的数学表达用动态规划的视角可以这样理解本题的状态转移状态定义A[i][j]表示流入第i行第j个杯子的香槟总量可能超过 1因为包含后续溢流累积。转移方向只存在「上一层 → 下一层」的单向转移即状态只由上一层决定符合 DP 的「无后效性」——当前层如何溢流只取决于上一层分配给它的量。转移方程若A[i][j] 1则溢出的量为(A[i][j] - 1) / 2分别累加到A[i1][j]与A[i1][j1]。这与仓库 thinkings/dynamic-programming.md 中「状态转移方程」的公式化描述一脉相承给定第k阶段的状态以及决策第k1阶段的状态就完全确定。本题的决策就是「把超出 1 的部分均分给下一层的两个邻居」。四、关键点只需模拟一次本题最容易陷入的误区是在计算某一层的溢出时立刻递归地去模拟下一层乃至更下层的溢出即使用while循环持续处理。原文档强调的关键点在于不必模拟多步而是只模拟一次即可。也就是说我们无需在溢出到下一层之后继续追踪下一层的二次溢出因为外层遍历会在后续轮次自然处理它。体现在代码上只需要if判断无需while循环。这一观察使得实现变得极其简洁一次从上到下、从左到右的完整遍历就足以让所有溢流信息按照「逐层传播」的方式累积到每个杯子。五、代码实现语言支持Python3。class Solution: def champagneTower(self, poured, R, C): # 这种初始化方式有一半空间是浪费的 A [[0] * (R1) for _ in range(R1)] A[0][0] poured # 从上到下从左到右模拟每一行每一列 for i in range(R 1): for j in range(i1): overflow (A[i][j] - 1.0) / 2.0 # 不必模拟多步而是只模拟一次即可。也就是说我们无需溢出到下一层之后 # 下一层的杯子容量大于 1 的情况后面遍历时会处理这和直觉上或许有所不一样。 # 体现在代码上只需要 if 即可无需 while if overflow 0 and i R and j C: A[i1][j] overflow if j1C: A[i1][j1] overflow return min(1, A[R][C]) # 最后的结果如果大于 1说明流到地板上了需要和 1 取最小值。5.1 代码逐行解读代码片段作用A [[0] * (R1) for _ in range(R1)]开辟(R1) x (R1)的二维矩阵行号/列号均从 0 开始多出的第R1行用于承接最后一层的溢流A[0][0] poured把全部香槟一次性注入顶层杯子for i in range(R 1)/for j in range(i1)从上到下、从左到右遍历第i行只遍历i1个有效位置overflow (A[i][j] - 1.0) / 2.0计算当前杯子的溢流量- 1.0表示扣除杯子的满容量/ 2.0表示均分给左右两个杯子if overflow 0 and i R and j C只有溢流量为正才传播i R防止越界j C是只传播到查询列的小优化A[i1][j] overflow/A[i1][j1] overflow将溢流量分别加到下一层的左右两个杯子return min(1, A[R][C])查询位置若已满则返回 1多余的流到地板否则返回实际比例5.2 复杂度分析时间复杂度$O(R^2)$其中R为查询行号双层循环遍历三角形区域。空间复杂度$O(R^2)$用于存储整个二维 DP 矩阵。5.3 从源码结构看可优化方向本仓库中其他 DP 题解提供了可借鉴的优化模式。例如 problems/62.unique-paths.md不同路径展示了把二维 DP 压缩为一维数组、仅保留「上一行」信息的滚动数组做法dp[j] dp[j] dp[j - 1]。可以推断香槟塔的状态转移同样只依赖上一行的值因此理论上也能用一维数组按行滚动更新来把空间复杂度降到 $O(R)$同时由于只关心查询列C附近的杯子遍历列时可以进一步裁剪范围。仓库原题解出于直观与简洁考虑采用了二维矩阵版本这也是R 99约束下完全可行的方案。六、验证与运行你可以用以下方式验证代码的正确性运行示例 1poured 1, R 1, C 1输出0.0运行示例 2poured 2, R 1, C 1输出0.5边界情况poured 0时任意位置均为0.0poured极大如10^9且查询位置靠下时结果会稳定收敛到1.0由min(1, A[R][C])正确截断。完整题解文档见 problems/799.champagne-tower.md若想系统补齐动态规划基础可阅读仓库专题 thinkings/dynamic-programming.md仓库的整体目录结构可参考 SUMMARY.md。七、小结LeetCode 799「香槟塔」是一个将现实物理模型转化为模拟型动态规划的经典题目。核心要点有三建模用R x R二维数组存放每层每个杯子的香槟量第i行有效元素为i1个递推每个杯子把超出容量1的部分均分给下一层左右两个杯子严格自上而下、单向传播简化全程只需一次双层遍历即可完成所有溢流的模拟无需循环处理次级溢流最终结果与1取最小值以处理「流到地板」的边界。掌握这一「自上而下逐行模拟 溢流均分」的套路后类似的分层传播、逐级均摊类问题都可以套用同一思维框架快速求解。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考