Python3 fastest solution (88ms, beats 100%), O(KN^2) time O(N^2) space, with explanation
It\'s not quite as pretty/elegant as I\'d like it to be, but it beats the fastest visible solution (currently 96ms) in the submissions histogram; maybe someone 
It\'s not quite as pretty/elegant as I\'d like it to be, but it beats the fastest visible solution (currently 96ms) in the submissions histogram; maybe someone better at Python can make it prettier and still retain the speed:\n```python\ndef knightProbability(self, N, K, r, c): # 88ms, beats 100%\n    if not K: return 1.\n    def helper(i, j):\n        if not 0 <= i < N or not 0 <= j < N: return 0\n        if N - 1 < 2 * i: i = N - 1 - i\n        if N - 1 < 2 * j: j = N - 1 - j\n        if j < i: i, j = j, i\n        return back[i][j]\n    moves = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))\n    half = N + 1 >> 1\n    back = [[1 for j in range(half)] for i in range(half)]\n    front = [[0 for j in range(half)] for i in range(half)]\n    for k in range(K - 1):\n        for i in range(half):\n            for j in range(i, half):\n                front[i][j] = sum(helper(i + di, j + dj) for di, dj in moves) / 8\n        front, back = back, front\n    return sum(helper(r + di, c + dj) for di, dj in moves) / 8\n```\n---\n\n### Explanation\n\nMy original solution:\n```python\ndef knightProbability(self, N, K, r, c): # 144ms, beats 99%\n    def helper(i, j):\n        if not 0 <= i < N or not 0 <= j < N: return 0\n        i, j = sorted((min(i, N - 1 - i), min(j, N - 1 - j)))\n        return back[i][j]\n    moves = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))\n    half = N + 1 >> 1\n    back = [[1 for j in range(half)] for i in range(half)]\n    front = [[0 for j in range(half)] for i in range(half)]\n    for k in range(K):\n        for i in range(half):\n            for j in range(i, half):\n                front[i][j] = sum(helper(i + di, j + dj) for di, dj in moves) / 8\n        front, back = back, front\n    return helper(r, c)\n```\nThere\'s no real deep insight, honestly. The first optimization is just to exploit the symmetry of the board to cut the work down by a factor of approximately 8. Example: For `N = 6`, we don\'t actually need to figure out the probabilities for all 36 spots on the board; it suffices to figure out the probabilities in this little triangle, which is approximately 1/8 the size of the entire board:\n```abc\n+---+---+---+---+---+---+\n| x | x | x |   |   |   |\n+---+---+---+---+---+---+\n|   | x | x |   |   |   |\n+---+---+---+---+---+---+\n|   |   | x |   |   |   |\n+---+---+---+---+---+---+\n|   |   |   |   |   |   |\n+---+---+---+---+---+---+\n|   |   |   |   |   |   |\n+---+---+---+---+---+---+\n|   |   |   |   |   |   |\n+---+---+---+---+---+---+\n```\nOnce we figure out the probabilites for the spots marked `x` above, the probabilities for the rest of the board can be deduced from symmetry:\n```abc\n+---+---+---+---+---+---+      +---+---+---+---+---+---+\n| A | B | C |   |   |   |      | A | B | C | C | B | A |\n+---+---+---+---+---+---+      +---+---+---+---+---+---+\n|   | D | E |   |   |   |      | B | D | E | E | D | B |\n+---+---+---+---+---+---+      +---+---+---+---+---+---+\n|   |   | F |   |   |   |      | C | E | F | F | E | C |\n+---+---+---+---+---+---+  =>  +---+---+---+---+---+---+\n|   |   |   |   |   |   |      | C | E | F | F | E | C |\n+---+---+---+---+---+---+      +---+---+---+---+---+---+\n|   |   |   |   |   |   |      | B | D | E | E | D | B |\n+---+---+---+---+---+---+      +---+---+---+---+---+---+\n|   |   |   |   |   |   |      | A | B | C | C | B | A |\n+---+---+---+---+---+---+      +---+---+---+---+---+---+\n```\n`helper`\'s job is to take an arbitrary `(i, j)` coordinate on the board, normalize it to one of the coordinates in the little triangle, then return its probability.\n\nThe second optimization is a pretty common trick: Use double-buffering (`front`, `back`) to reduce space usage from O(KN^2) to O(N^2).\n\nThe third micro-optimization (used only in the 88ms code) is that we don\'t have to compute the probabilities for all slots on the board for the `K`th step. We only need the probability for the `(r, c)` slot, so we terminate our main loop after `K - 1` steps, then compute the probability for just the `(r, c)` slot for the `K`th step.
[]