Level 1 Unique Paths
A knight waits in the top-left square of an m x n board, and the castle stands in the bottom-right square. The road is strict: every move goes one square right or one square down, never up, left or diagonally.
Write unique_paths(m: int, n: int) -> int: how many different routes take the knight from its square to the castle. m is the number of rows and n the number of columns.
unique_paths(7, 7) # 924
unique_paths(3, 2) # 3 right-down-down, down-right-down, down-down-right
unique_paths(2, 3) # 3
unique_paths(1, 5) # 1 one row: only right, right, right, right
unique_paths(1, 1) # 1 the knight is already at the castle
Constraints:
1 <= m, n <= 100.- The answer can be huge (
unique_paths(100, 100)has 59 digits). Python ints don't overflow, so return the exact count.
Walking every route one by one is hopeless: a 16 x 16 board already has over 155 million of them. Aim for one pass over the board, O(m·n).
Show hint
the last move into a square came from the square above it or from the square on its left. So how do the counts of those two squares give the count of this one?