Problem statement

https://binarysearch.com/problems/Knight-Moves-to-Target-Coordinate/

Solution

Equal to Leetcode 1197 Minimum Knight Moves, but here to get AC we need a bit more efficient algorithm. We can use dp. If (r, c) == (0, 0) then answer is 0. If we have (2, 0), (1, 1), (0, 2) then we have 2 steps. In other cases, we can make step in direction 1, 2 or 2, 1.

Complexity

It is O(rc) for time and space.

Code

class Solution:
    def solve(self, r, c):
        @lru_cache(None)
        def dp(x, y):
            if x + y == 0: return 0
            if x + y == 2: return 2
            return min(dp(abs(x - 1), abs(y - 2)), dp(abs(x - 2), abs(y - 1))) + 1
        return dp(r, c)

Remark

There is also O(1) math solution using greedy strategy and a lot of edge cases.