• Time:O(xy)
• Space:O(xy)

## C++

``````class Solution {
public:
int minKnightMoves(int x, int y) {
return dp(abs(x), abs(y));
}

private:
struct pairHash {
size_t operator()(const pair<int, int>& p) const {
return p.first ^ p.second;
}
};

unordered_map<pair<int, int>, int, pairHash> memo;

int dp(int x, int y) {
if (x + y == 0)  // (0, 0)
return 0;
if (x + y == 2)  // (0, 2), (1, 1), (2, 0)
return 2;
if (memo.count({x, y}))
return memo[{x, y}];

return memo[{x, y}] = min(
dp(abs(x - 2), abs(y - 1)),
dp(abs(x - 1), abs(y - 2))) + 1;
}
};
``````

## JAVA

``````class Solution {
public int minKnightMoves(int x, int y) {
return dp(Math.abs(x), Math.abs(y));
}

private Map<Pair<Integer, Integer>, Integer> memo = new HashMap<>();

private int dp(int x, int y) {
if (x + y == 0) // (0, 0)
return 0;
if (x + y == 2) // (0, 2), (1, 1), (2, 0)
return 2;
Pair<Integer, Integer> key = new Pair<>(x, y);
if (memo.containsKey(key))
return memo.get(key);

final int minMove = Math.min(
dp(Math.abs(x - 2), Math.abs(y - 1)),
dp(Math.abs(x - 1), Math.abs(y - 2))) + 1;
memo.put(key, minMove);
return minMove;
}
}
``````