Super simple recursive Python solution, beats 98%
We set 2 super simple base cases: if we\'re already outside the grid, the probability of staying inside is 0. If we\'re inside the grid and have no moves left t
We set 2 super simple base cases: if we\'re already outside the grid, the probability of staying inside is 0. If we\'re inside the grid and have no moves left to make, the probability of staying inside is 1. Otherwise, we make 8 recursive calls and average them. We use Python\'s built-in lru_cache for memoization.\n\nFinal code: \n\n```\ndef knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n\t@functools.lru_cache(None)\n\tdef travels(xcurr, ycurr, k):\n\t\tif xcurr < 0 or xcurr >= N or ycurr < 0 or ycurr >= N: \n\t\t\t# We\'re already outside the grid, so probability of staying inside is 0\n\t\t\treturn 0\n\t\telif k == 0:\n\t\t\t# We\'re inside the grid and have no more moves to make\n\t\t\treturn 1\n\t\telse:\n\t\t\t# Otherwise, we make one of 8 possible moves and find the probability of staying inside after \n\t\t\t# k - 1 more moves. Because each move is equally likely, we average all of these probabilities.\n\t\t\treturn (travels(xcurr + 2, ycurr + 1, k - 1) + \n\t\t\t\t\ttravels(xcurr + 1, ycurr + 2, k - 1) + \n\t\t\t\t\ttravels(xcurr - 1, ycurr + 2, k - 1) + \n\t\t\t\t\ttravels(xcurr - 2, ycurr + 1, k - 1) + \n\t\t\t\t\ttravels(xcurr - 2, ycurr - 1, k - 1) + \n\t\t\t\t\ttravels(xcurr - 1, ycurr - 2, k - 1) + \n\t\t\t\t\ttravels(xcurr + 1, ycurr - 2, k - 1) +   \n\t\t\t\t\ttravels(xcurr + 2, ycurr - 1, k - 1)) / 8\n\n\treturn travels(r, c, K)\n```\n\n\n\n
['Python', 'Python3']