[LeetCode]Knight Probability in Chessboard

递归的方法很容易想，思路如下:

• 如果当前超出board，return 0
• 如果当前剩余0步并且在board里，return 1
• 否则八个方向分别递归，结果乘以0.125累加

纯dfs很慢，我们用memorization优化即可。时间复杂度O(N^2 * K)，空间复杂度O(N^2 * K)。代码如下：

bottom up的方法一样也可以做。DP[i][j][k]代表位于[i, j]位置并且还剩k步的时候位于board内的概率，我们有递推方程:

• DP[i][j][k] = sum(0.125 * DP[x][y][k - 1]), where we can move from i, j to x, y

时间复杂度O(N^2 * K)，空间复杂度可以用滚动数组优化到O(N^2)。代码如下: