Leetcode # 688. Knight Probability in Chessboard

https://leetcode.com/problems/knight-probability-in-chessboard

Solution: Top-down Dynamic Programming (Memoization)

Time Complexity: O(k * n * n)
Space Complexity: O(k * n * n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
    moves = [
      [ 1, -2], [ 2, -1], 
      [ 2,  1], [ 1,  2], 
      [-1, -2], [-2, -1], 
      [-1,  2], [-2,  1]
    ]
    p = [[[1 if _k == 0 else -1] * n for _ in range(n)] for _k in range(k + 1)]
    
    def knight_prob(_k, r, c):
      if p[_k][r][c] == -1:
        remains_on_the_board_p = 0
        for my, mx in moves:
          y, x = r + my, c + mx
          if x >= 0 and x < n and y >= 0 and y < n:
            remains_on_the_board_p += knight_prob(_k - 1, y, x)
        p[_k][r][c] = remains_on_the_board_p / len(moves)
      return p[_k][r][c]

    return knight_prob(k, row, column)

疏忽 / 錯誤

Correct Way to Initialize a Multidimensional List

 p = [[[1 if _k == 0 else -1] * n] * n for _k in range(k + 1)]
p = [[[1 if _k == 0 else -1] * n for _ in range(n)] for _k in range(k + 1)]
原因說明請參閱：[Python] List Comprehensions

忘記應記錄 p[_k][r][c] = remains_on_the_board_p / len(moves)

Solution: Bottom-up Dynamic Programming with Optimized Space Complexity

不使用 dp[_k] (_k = 0, 1, …, k + 1)
只使用 prev_dp 和 curr_dp

Time Complexity: O(k * n * n)
Space Complexity: O(k * n * n)
(The input and output generally do not count towards the space complexity.)

Last Updated on 2023/08/16 by A1go