Golang | Leetcode Golang题解之第365题水壶问题

题目：

题解：

type pair struct {x, y int
}func canMeasureWater(jug1Capacity int, jug2Capacity int, targetCapacity int) bool {//剪枝if jug1Capacity+jug2Capacity < targetCapacity {return false}var (dfs func(x, y int) bool   // jug1有x水，jug2有y水 能否达到targetvis = make(map[pair]bool) // 记忆化)dfs = func(x, y int) bool {//记忆化p := pair{x, y}if vis[p] {return false}vis[p] = true//x、y组合就是答案if x == targetCapacity || y == targetCapacity || x+y == targetCapacity {return true}//x、y分别装满、倒空if dfs(jug1Capacity, y) || dfs(0, y) || dfs(x, jug2Capacity) || dfs(x, 0) {return true}//x、y分别倒对方里x2y := min(x, jug2Capacity-y)y2x := min(y, jug1Capacity-x)return dfs(x-x2y, y+x2y) || dfs(x+y2x, y-y2x)}return dfs(0, 0)
}