golang力扣leetcode 688.骑士在棋盘上的概率

package main
func knightProbabilityDP(n int, k int, row int, column int) float64 {
  var dirs = []struct{ i, j int }{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}}
  dp := make([][][]float64, k+1)
  for step := range dp {
    dp[step] = make([][]float64, n)
    for i := 0; i < n; i++ {
      dp[step][i] = make([]float64, n)
      for j := 0; j < n; j++ {
        if step == 0 {
          dp[step][i][j] = 1
        } else {
          for _, d := range dirs {
            prevX, pervY := i+d.i, j+d.j
            if prevX >= 0 && prevX < n && pervY >= 0 && pervY < n {
              dp[step][i][j] += dp[step-1][prevX][pervY] / 8
            }
          }
        }
      }
    }
  }
  return dp[k][row][column]
}
func knightProbabilityDfsAndMemory(n int, k int, row int, column int) float64 {
  var dirs = []struct{ i, j int }{{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}}
  memory := make([][][]float64, k+1)
  for i := range memory {
    memory[i] = make([][]float64, n)
    for j := range memory[i] {
      memory[i][j] = make([]float64, n)
    }
  }
  var dfs func(n int, k int, row int, column int) float64
  dfs = func(n int, k int, row int, column int) float64 {
    if k == 0 {
      return 1
    }
    if memory[k][row][column] != 0 {
      return memory[k][row][column]
    }
    for _, d := range dirs {
      prevX, prevY := row+d.i, column+d.j
      if prevX >= 0 && prevX < n && prevY >= 0 && prevY < n {
        memory[k][row][column] += dfs(n, k-1, prevX, prevY) / 8
      }
    }
    return memory[k][row][column]
  }
  return dfs(n, k, row, column)
}