recursion and DP does the job
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ndef fun(n,k,i,j,memo):\n    if(i<0 or i>=n or j<0 or j>=n):\n        return 0\n    if(k==0):\n        return 1\n    if((i,j,k) in memo):\n        return(memo[(i,j,k)])\n    a=0\n    a+=fun(n,k-1,i+2,j+1,memo)\n    a+=fun(n,k-1,i+2,j-1,memo)\n    a+=fun(n,k-1,i-2,j+1,memo)\n    a+=fun(n,k-1,i-2,j-1,memo)\n    a+=fun(n,k-1,i+1,j+2,memo)\n    a+=fun(n,k-1,i+1,j-2,memo)\n    a+=fun(n,k-1,i-1,j+2,memo)\n    a+=fun(n,k-1,i-1,j-2,memo)\n    memo[(i,j,k)]=a\n    return a\nclass Solution:\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        p=[0]\n        ng=[0]\n        x=fun(n,k,column,row,{})\n        return x/(8**k)\n```
['Python3']