Python short and clean. Multiple solutions. Functional programming.
Approach 1:\n###### Top-Down, Recursive, Functional DP\nGiven a board n * n. Let on_board_prob be a function which returns the probability of knight to stay on 
# Approach 1:\n###### Top-Down, Recursive, Functional DP\nGiven a board `n * n`. Let `on_board_prob` be a function which returns the probability of knight to stay on the board after `k` steps, starting from row `i` and column `j`. (Exactly what the problem asks)\n\nIf `k > 0`, i.e some moves are left: Try out the `8` equivi-probable `moves` from `i, j` that are `on_board` and add `1/8 th` of the probabilities from each of them.\n\nIf `k == 0`, return `prob = 1 if (i, j) is on_board else 0`\n\nMake sure to memoize `on_board_prob` to exploit overlapping subproblems and optimal substructure of the problem.\n\nNote: The first 3 lines defining `on_board`, `moves`, `next_positions` are copy pasted in all solutions.\n\n# Complexity\n- Time complexity: $$O(k \\cdot n^2)$$\n\n- Space complexity: $$O(k \\cdot n^2)$$\n\n# Code\n```python\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        on_board = lambda i, j: 0 <= i < n and 0 <= j < n\n        moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))\n        next_positions = lambda i, j: ((i + di, j + dj) for di, dj in moves)\n\n        @cache\n        def on_board_prob(k: int, i: int, j: int) -> float:\n            return sum(on_board_prob(k - 1, ni, nj) for ni, nj in next_positions(i, j) if on_board(ni, nj)) / 8 if k else on_board(i, j)\n        \n        return on_board_prob(k, row, column)\n\n\n```\n\n---\n\n# Approach 2:\n###### Bottom-Up, Imperative DP\nUse explicit `probs` 3-dimensional `k * n * n` DP array to replace `on_board_prob(k, i, j)` function above.\n\n# Complexity\n- Time complexity: $$O(k \\cdot n^2)$$\n\n- Space complexity: $$O(k \\cdot n^2)$$\n\n# Code\n```python\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        on_board = lambda i, j: 0 <= i < n and 0 <= j < n\n        moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))\n        next_positions = lambda i, j: ((i + di, j + dj) for di, dj in moves)\n\n        probs = [[[1] * n for _ in range(n)] for _ in range(k + 1)]\n        for k, i, j in product(range(1, k + 1), range(n), range(n)):\n            probs[k][i][j] = sum(probs[k - 1][ni][nj] for ni, nj in next_positions(i, j) if on_board(ni, nj)) / 8\n        \n        return probs[k][row][column]\n\n\n```\n\n---\n\n# Approach 3:\n###### Bottom-Up, Imperative, Space optimized DP\nNotice, we only ever use `probs[k - 1][..][..]` to calculate `probs[k][..][..]`.\nReduce `probs` to 2-dimensional `n * n` DP array by keeping only the previous values of first dimension.\n\n# Complexity\n- Time complexity: $$O(k \\cdot n^2)$$\n\n- Space complexity: $$O(n^2)$$\n\n# Code\n```python\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        on_board = lambda i, j: 0 <= i < n and 0 <= j < n\n        moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))\n        next_positions = lambda i, j: ((i + di, j + dj) for di, dj in moves)\n\n        probs = [[1] * n for _ in range(n)]\n        for k in range(1, k + 1):\n            probs = [[sum(probs[ni][nj] for ni, nj in next_positions(i, j) if on_board(ni, nj)) / 8 for j in range(n)] for i in range(n)]\n        \n        return probs[row][column]\n\n\n```\n\n---\n\n# Approach 4:\n###### Bottom-Up, Declarative, Functional, Space optimized DP\nUse `functools.reduce` to eliminate imperative coding in the above solution.\n\nNote: At this point, the code is purely functional and can technically also be written as a 1-liner, albeit a very long one!\n\n# Complexity\n- Time complexity: $$O(k \\cdot n^2)$$\n\n- Space complexity: $$O(n^2)$$\n\n# Code\n```python\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        on_board = lambda i, j: 0 <= i < n and 0 <= j < n\n        moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))\n        next_positions = lambda i, j: ((i + di, j + dj) for di, dj in moves)\n\n        next_probs = lambda prob, k: [[sum(prob[ni][nj] for ni, nj in next_positions(i, j) if on_board(ni, nj)) / 8 for j in range(n)] for i in range(n)]\n        probs = reduce(next_probs, range(1, k + 1), [[1] * n for _ in range(n)])\n        return probs[row][column]\n\n\n```
['Dynamic Programming', 'Recursion', 'Python', 'Python3']