DFS -> DP Progression with Explanation [82%/6%]
This problem is asking us to explore all possible combinations of moves the knight can make, and return the percentage of combinations that keeps the knight on 
This problem is asking us to explore all possible combinations of moves the knight can make, and return the percentage of combinations that keeps the knight on the board after `K` turns.  At each step, the knight has an equal probability of moving to one of its eight possible positions.  This leads to the following DFS solution\n```\ndef dfs(N, K, r, c):\n\tif r < 0 or r >= N or c < 0 or c >= N:    // Out of bounds\n\t\treturn 0\n\tif K == 0:   // In bounds after K turns\n\t\treturn 1\n\tleft_up = 0.125 * dfs(N, K - 1, r - 1, c - 2)\n\tleft_down = 0.125 * dfs(N, K - 1, r + 1, c - 2)\n\tdown_left = 0.125 * dfs(N, K - 1, r + 2, c - 1)\n\tdown_right = 0.125 * dfs(N, K - 1, r + 2, c + 1)\n\tright_down = 0.125 * dfs(N, K - 1, r + 1, c + 2)\n\tright_up = 0.125 * dfs(N, K - 1, r - 1, c + 2)\n\tup_right = 0.125 * dfs(N, K - 1, r - 2, c + 1)\n\tup_left = 0.125 * dfs(N, K - 1, r - 2, c - 1)\n\n\treturn sum([left_up, left_down, down_left, down_right, right_down, right_up, up_right, up_left])\nreturn dfs(N, K, r, c)\n```\nWe can think of each of the recursive calls as a move the knight can make from its current position.  If we draw out the DFS recursion tree, each node will have 8 branches, one for each possible move.  Moving down one branch signifies the knight making that move, and then we repeat the process given the knight\'s new position.\n\nHowever, the DFS solution takes too long and times out.  Why is this?  Again, think of every recursive call as the knight moving to one of its eight possible squares.  From the starting square, one possible path the knight could follow is `left_up -> up_left`.  Also from the starting square, another possible path the knight could follow is `up_left -> left_up`.  Both of these paths put the knight on the same square in the same amount of moves.  If we continue calculating both paths from this new position, we will see they result in the same answer.  Instead of just calculating this once, we have done it twice!  Now imagine how many times this happens if we increase the moves the knight can make, this gets exponentially worse.\n\nThis is where the DP solution comes in.  Let\'s look at the solution, and then I will explain the logic.\n```\ndef dp(N, K, r, c):\n\tA = [[[0] * N for _ in range(N)] for _ in range(K + 1)]\n\tfor i in range(N):\n\t\tfor j in range(N):\n\t\t\tA[0][i][j] = 1\n\tfor k in range(1, K + 1):\n\t\tfor i in range(N):\n\t\t\tfor j in range(N):\n\t\t\t\tif i - 1 >= 0 and j - 2 >= 0:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i - 1][j - 2]\n\t\t\t\tif i + 1 < N and j - 2 >= 0:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i + 1][j - 2]\n\t\t\t\tif i + 2 < N and j - 1 >= 0:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i + 2][j - 1]\n\t\t\t\tif i + 2 < N and j + 1 < N:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i + 2][j + 1]\n\t\t\t\tif i + 1 < N and j + 2 < N:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i + 1][j + 2]\n\t\t\t\tif i - 1 >= 0 and j + 2 < N:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i - 1][j + 2]\n\t\t\t\tif i - 2 >= 0 and j + 1 < N:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i - 2][j + 1]\n\t\t\t\tif i - 2 >= 0 and j - 1 >= 0:\n\t\t\t\t\tA[k][i][j] += 0.125 * A[k - 1][i - 2][j - 1]\n\n\treturn A[K][r][c]\nreturn dp(N, K, r, c)\n```\nYes a 3D array is daunting, but let\'s break it down by first looking at the subproblem we are trying to solve.  \n```\nA[k][i][j] = The probability of the knight remaining on the board from position (i, j) with k moves remaining\n```\nSo with `k == 0` moves left, every position on the board has a probability of 1 because the knight has no more moves to make.  Visualizing the 3D array, this builds the bottom layer, and now we start to fill the layers out going upwards.  At `K == 1`, notice that this is exactly the same as the DFS solution.  We have 8 possible moves, and for each recursive call that stays on the board we add (0.125 * 1).  For each recursive call that falls out of bounds, we simply don\'t add it (which is the same as adding 0 as we did in the DFS solution).  Continue doing this until we have filled in `K` slices of the array and we have our solution.\nSince we built this solution from the ground up, we are avoiding recalculating large portions of paths which is the problem that plagues the DFS solution.  This is why DP is optimal for this type of problem.\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\t
['Dynamic Programming', 'Depth-First Search', 'Python']