难度: Hard
给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。
每一步 ，你可以从点 (x, y) 移动到以下点之一：
(x, y - x)(x - y, y)(2 * x, y)(x, 2 * y)给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。
示例 1：
输入：targetX = 6, targetY = 9 输出：false 解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。
示例 2：
输入：targetX = 4, targetY = 7 输出：true 解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。
提示：
1 <= targetX, targetY <= 109运行时间: 21 ms
内存: 15.9 MB
class Solution:
def isReachable(self, targetX: int, targetY: int) -> bool:
return self.dfs(targetX,targetY,targetX,targetY)
@cache
def dfs(self,x,y, targetX, targetY):
if x==1 and y==1: return True
if x==y and x%2!=0 and y%2!=0: return False
if x%2==0: return self.dfs(x//2,y,targetX,targetY)
if y%2==0: return self.dfs(x,y//2,targetX,targetY)
return self.dfs(x+y,min(x,y),targetX,targetY)
return False
该题解使用了逆向思维的深度优先搜索（DFS）方法。从目标点 (targetX, targetY) 开始，尝试反向追溯到起点 (1, 1)。反向操作包括：如果当前坐标的 x 或 y 是偶数，则将其除以 2；如果坐标 x 和 y 不相等，则尝试通过减法操作逆向推回。这里的思路是从目标点反推到初始点，而非正向从起点搜索到终点，因为反向操作可以更直接地缩小搜索空间。递归中，如果 x 和 y 相等而且都是奇数，则无法继续操作，因为不可能通过以上操作生成两个相等的奇数。最终，如果能反向递归到 (1, 1)，说明目标点可达，返回 true；否则返回 false。通过使用 @cache 装饰器，优化了重复子问题的求解过程，提高了效率。
时间复杂度: O(log(max(targetX, targetY)))
空间复杂度: O(log(max(targetX, targetY)))
class Solution:
def isReachable(self, targetX: int, targetY: int) -> bool:
# 开始逆向搜索从目标点到起点
return self.dfs(targetX,targetY,targetX,targetY)
@cache
def dfs(self,x,y, targetX, targetY):
# 如果到达起点，返回 True
if x==1 and y==1: return True
# 如果 x 和 y 相等且都是奇数，无法继续操作，返回 False
if x==y and x%2!=0 and y%2!=0: return False
# 如果 x 是偶数，尝试 x 除以 2 的操作
if x%2==0: return self.dfs(x//2,y,targetX,targetY)
# 如果 y 是偶数，尝试 y 除以 2 的操作
if y%2==0: return self.dfs(x,y//2,targetX,targetY)
# 尝试通过加法逆向操作
return self.dfs(x+y,min(x,y),targetX,targetY)
# 此行代码永远不会执行，可以删除
return False
在递归函数中，当 x 和 y 都是偶数时，实际上对 x 或 y 进行除以 2 的操作是互相独立的。这意味着，在任何给定的递归步骤中，我们可以选择对 x 或 y 进行操作，而不会遗漏可能的路径。由于这两种操作是条件互斥的（即进行一种操作后，另一种操作的条件就不再满足），因此在一个递归调用中只需要选择一种操作。此外，同时对 x 和 y 进行除以 2 的操作在逻辑上不会同时出现，因为我们总是可以通过多次递归来达到相同的结果。
当 x 和 y 都是奇数且相等时，无法通过给定的操作（除以 2 或减法）来改变它们的状态，使得其中一个成为偶数或不相等。因为减法操作 (x - y, y) 或 (x, y - x) 在 x 和 y 相等时不会改变任何值，而除以 2 的操作也无法应用于奇数。因此，如果 x 和 y 在任何递归步骤中都是奇数且相等，就无法通过进一步的操作到达 (1, 1)。
使用 @cache 装饰器可以缓存递归函数的中间结果，避免重复计算相同参数的结果，从而显著提高效率。空间复杂度主要取决于缓存中存储的不同参数组合的数量。在最坏情况下，每个参数 (x, y) 可能都是从 targetX 和 targetY 出发可能达到的任何值。因此，空间复杂度依赖于从目标点到起点可能的路径数量。在这种情况下，空间复杂度可能接近 O(targetX * targetY)，因为每个点可能至少被访问一次。但实际上，由于操作的限制性，访问的状态通常远少于此理论上限。