JAVA程序设计：到达终点（LeetCode：780）

从点 (x, y) 可以转换到 (x, x+y)  或者 (x+y, y)。

给定一个起点 (sx, sy) 和一个终点 (tx, ty)，如果通过一系列的转换可以从起点到达终点，则返回 True ，否则返回 False。

示例:

输入: sx = 1, sy = 1, tx = 3, ty = 5

输出: True

解释:

可以通过以下一系列转换从起点转换到终点：

(1, 1) -> (1, 2)

(1, 2) -> (3, 2)

(3, 2) -> (3, 5)

输入: sx = 1, sy = 1, tx = 2, ty = 2

输出: False

输入: sx = 1, sy = 1, tx = 1, ty = 1

输出: True

注意:

sx, sy, tx, ty 是范围在 [1, 10^9] 的整数。

思路：这么一个题竟然是过一点点人的困难题~~~，思路很简单，因为正着考虑会导致分叉处很多情况，因为我们首先要想到的是倒着考虑问题，也就是如何让最终要到达的结果通过相减变成初始值，我们知道肯定不能小的减大的啊，所以我们每次只能大减小，这样这道题就解决了，遇到x和y相同时再分叉，当然我们不能乖乖的一点点的减，n有10^9这么大，这样一定会导致超时的，优化非常简单，每次尽可能大的减，但是要保证不能减到小于初始值！

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
    	
    	if(tx<sx || ty<sy) return false;
    	if(tx==sx && ty==sy) return true;
    		
    	if(tx>ty) {
    		int num=(tx-sx)/ty*ty;
    		return reachingPoints(sx,sy,tx-Math.max(num, ty),ty);
    	}
    	else if(tx<ty) {
    		int num=(ty-sy)/tx*tx;
    		return reachingPoints(sx,sy,tx,ty-Math.max(num, tx));
    	}
    	else return reachingPoints(sx, sy, tx-ty, ty)
    			|| reachingPoints(sx, sy, tx, ty-tx);
    }
}