逆向思维|memo

正着不行就倒着，wa一次人之常情

lc3609

记忆化DFS从目标坐标反向递归，根据横竖坐标大小关系尝试减法或折半操作

统计从目标回到起始坐标的最少操作次数，无法到达则返回-1

class Solution {
public:
map<pair<int,int>,int> mp;
int dfs(int r,int c,int& tx,int& ty){
if(r < tx || c < ty) return -1;
if(r==tx && c==ty){
return 0;
}
int mi = 10000;
if(r >= c){
int d = r - c;
int p1 = -1,p2 = -1;
if(d <= c){
p1 = dfs(r-c,c,tx,ty);
}
int p = (r%2==0 ? r/2:-100);
if(p >= c){
p2 = dfs(r/2,c,tx,ty);
}

if(p1!=-1) mi = p1;
if(p2!=-1) mi=min(mi,p2);
}
if(c >= r){
int d = c - r;
int p1 = -1,p2 = -1;
if(d <= r){
p1 = dfs(r,c - r,tx,ty);
}
int p = (c%2==0 ? c/2:-100);
if(p >= r){
p2 = dfs(r,c/2,tx,ty);
}
if(p1!=-1) mi = min(mi,p1);
if(p2!=-1) mi=min(mi,p2);
}
if(mi == 10000) return -1;
return mi + 1;
}
int minMoves(int sx, int sy, int tx, int ty) {
if(sx==0&&sy==0){
if(tx==0&&ty==0) return 0;
return -1;
}
return dfs(tx,ty,sx,sy);
}
};