[LeetCode] 688. Knight Probability in Chessboard

😎풀이

1. 메모이제이션이 수행될 DP 배열 선언
2. 백트레킹 수행
   2-1. k회 이동하고 보드 내 위치해 있을 경우 1 반환(100%)
   2-2. 영역을 벗어난 경우 0 반환(0%)
   2-3. 그 외의 경우, 현재 셀에서 8 방향으로 이동하여 보드 내에 위치시킬 수 있을 확률 반환
3. k번의 기회로 row행의 col열에서 보드내에 위치시킬 수 있는 확률 반환

function knightProbability(n: number, k: number, row: number, column: number): number {
    const memo = Array.from({ length: k + 1 }, () => 
        Array.from({ length: n }, () => Array(n).fill(-1))
    )
    function backTrack(remainK: number, y: number, x: number) {
        if(y >= n || y < 0 || x >= n || x < 0) return 0
        if(remainK <= 0) return 1
        if(memo[remainK][y][x] !== -1) return memo[remainK][y][x]
        const nextK = remainK - 1
        let probability = 0
        probability += backTrack(nextK, y - 2, x - 1)
        probability += backTrack(nextK, y - 2, x + 1)
        probability += backTrack(nextK, y - 1, x - 2)
        probability += backTrack(nextK, y - 1, x + 2)
        probability += backTrack(nextK, y + 1, x - 2)
        probability += backTrack(nextK, y + 1, x + 2)
        probability += backTrack(nextK, y + 2, x - 1)
        probability += backTrack(nextK, y + 2, x + 1)
        memo[remainK][y][x] = probability / 8
        return memo[remainK][y][x]
    }
    return backTrack(k, row, column)
};