780. 到达终点.md

780. 到达终点

题目传送门

点击这里

解题思路

这道题的难点在于这个推理运算，很容易想到从头开始进行dfs遍历所有情况，但是这样子情况太多，分支太多，容易超出时间复杂度，我们可以逆向推理，从结果向起始出发，具体的情况写在注释中。

代码

func reachingPoints(sx, sy, tx, ty int) bool {
    // 推理题
    // 从tx，ty开始推理，首先明确如果tx==ty的话，那么说明tx和ty是起始点，
    for tx > sx && ty > sy && tx != ty {
        // 如果tx > ty， 说明上一个状态时tx-ty，ty
        if tx > ty {
            tx %= ty
        } else {
            // 同理
            ty %= tx
        }
    }
    // 判断
    switch {
    // 如果tx == sx，ty == sy 则直接返回
    case tx == sx && ty == sy:
        return true
    // 如果知识tx == sx， 那有可能是sx，sx+sy的情况
    case tx == sx:
        return ty > sy && (ty-sy)%tx == 0
    // 同理
    case ty == sy:
        return tx > sx && (tx-sx)%ty == 0
    default:
        return false
    }
}