水壶问题：数学解法与DFS双视角剖析

题目

https://leetcode-cn.com/problems/water-and-jug-problem/

有两个容量分别为 x 升和 y 升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z 升的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z 升水。

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

1. 题目深度解析

问题本质

题目等价于存在无限水源，通过两个容器（x升和y升）的操作，能否组合出z升水。关键操作包括：装满、倒空、相互倒水。最终z升水可以存在于任一或两个容器中。

易错点澄清

题目没有明确说明是否允许容器部分装满，但实际操作允许任意水量状态
原题描述存在歧义，正确理解应为：最终总水量（两个容器水量之和）等于z即可

2. 数学解法精讲

贝祖定理应用

若存在整数 a, b 使得 ax + by = z，则 z 是 x 和 y 最大公约数（GCD）的倍数。具体判断条件如下：

容量总和限制：z ≤ x + y
特殊情况处理：
- 任一容器为0时，只能得到0或另一容器容量的水
- z=0 时总是成立
最大公约数判断：z % gcd(x, y) == 0

示例分析

python
x=3, y=5 → gcd(3,5)=1
z=4 → 4%1=0 → 可行

x=2, y=6 → gcd(2,6)=2
z=5 → 5%2=1 → 不可行

数学解法代码

python
import math

def can_measure_water(x: int, y: int, z: int) -> bool:
    if z == 0:
        return True
    if x + y < z:
        return False
    if x == 0 or y == 0:
        return z == max(x, y)
    return z % math.gcd(x, y) == 0

3. DFS解法全面解析

算法思路

通过状态空间搜索，枚举所有可能的水量组合：

状态表示：(remain_x, remain_y) 表示当前两容器中的水量
状态转移：定义6种基本操作：
- 装满X/Y
- 倒空X/Y
- X→Y倒水（至Y满或X空）
- Y→X倒水（至X满或Y空）
终止条件：任一容器或总水量等于z
剪枝优化：使用集合记录已访问状态，避免重复计算

时间复杂度分析

最坏情况：O(xy)（状态总数为xy种）
实际效率：适合x,y较小时使用，大数值时效率急剧下降

DFS代码详解

python
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        stack = [(0, 0)]  # 初始状态：两容器皆空
        visited = set()    # 记录已探索状态
        
        while stack:
            rx, ry = stack.pop()
            
            # 终止条件检测
            if rx == z or ry == z or rx + ry == z:
                return True
            
            # 状态剪枝
            if (rx, ry) in visited:
                continue
            visited.add((rx, ry))
            
            # 生成所有可能状态
            # 操作1：装满X
            stack.append((x, ry))
            # 操作2：装满Y
            stack.append((rx, y))
            # 操作3：倒空X
            stack.append((0, ry))
            # 操作4：倒空Y
            stack.append((rx, 0))
            # 操作5：X→Y倒水
            transfer = min(rx, y - ry)
            stack.append((rx - transfer, ry + transfer))
            # 操作6：Y→X倒水
            transfer = min(ry, x - rx)
            stack.append((rx + transfer, ry - transfer))
        
        return False

操作过程示例（x=3, y=5, z=4）

初始状态：(0,0)
倒满Y → (0,5)
Y→X倒3升 → (3,2)
倒空X → (0,2)
Y→X倒2升 → (2,0)
倒满Y → (2,5)
Y→X倒1升 → (3,4) → 总水量7，超过z值
倒空X → (0,4) → ry=4符合条件

4. 方法对比与选择建议

方法	时间复杂度	空间复杂度	适用场景
数学解法	O(log(min(x,y)))	O(1)	任意规模，最优选择
DFS/BFS	O(xy)	O(xy)	小规模数据，需要具体操作路径时

5. 进阶思考

如何记录具体操作路径？
- 使用字典保存状态转移路径
- BFS更适合路径记录，可保证最短操作序列
三容器问题扩展？
- 数学解法不再适用
- 需使用图搜索算法
- 状态复杂度升至 O(xyz)
存在测量误差时的容错处理？
- 引入模糊判断机制
- 设定允许误差范围（如±0.5升）

目录