[Golang]| Dynamic programming | beats 100% of runtime and memory
Intuition\nJust for every step and for every cell count probability.\n\n# Approach\nWe can count probability for every cell after $k$ steps. \nLet $dp[k][i][j]$
# Intuition\nJust for every step and for every cell count probability.\n\n# Approach\nWe can count probability for every cell after $k$ steps. \nLet $dp[k][i][j]$ is probability for cell $i,j$ after $k$ steps.\nThen to count probability for some cell $X$ on step $k+1$ it is enough to sum $\\frac{1}{8}*Prop(\\text{cell } Y | Y \\text {can be reached from X})$\nor $dp[k][i][j]=sum ( \\frac{1}{8}*dp[k-1][is][js])$ where cell $[is,js]$ can be reached from $[i,j]$ and valid borad cell.\nAs counting for step $k+1$ is depends only from counting for step $k$ it is enough to keep in memory only two states: previous and current.So instead of $dp[k][i][j]$ enough to have $dp0[i][j]$ and $dp1[i][j]$\n\n\n# Complexity\n- Time complexity:\n $$O(k*n^2)$$ because from every $k$ we should traverse over all board.\n\n- Space complexity:\n$$O(n^2)$$ to keep 2 states\n\n# Code\n```\nfunc knightProbability(n int, k int, row int, column int) float64 {\n    moves:=[][]int{[]int{1,2},[]int{2,1},[]int{-1,2},[]int{2,-1},[]int{1,-2},[]int{-2,1},[]int{-2,-1},[]int{-1,-2}}\n\n    dp0:=make([][]float64,n)\n    for i:=0;i<n;i++{\n        dp0[i]=make([]float64,n)\n        for j:=0;j<n;j++{\n            dp0[i][j]=1.0\n        }\n    }\n    var dp1 [][]float64\n    for move:=1;move<=k;move++{\n        dp1=make([][]float64,n)\n        for i:=0;i<n;i++{\n            dp1[i]=make([]float64,n)\n            for j:=0;j<n;j++{\n                for _,s:=range moves{\n                    is,js:=i+s[0],j+s[1]\n                    if is>=0 && is<n && js>=0 && js<n{\n                        dp1[i][j]+=0.125*dp0[is][js]\n                    }\n                }\n            }\n        }\n        dp0=dp1\n    }\n    return dp0[row][column]\n}\n```
['Dynamic Programming', 'Go']