餓死抬頭(as title)，抬頭就starving所以要round robin。就算今天再累也要來刷刷題唷，今天來寫寫機率的題目吧～

Exercise 43: Leetcode 688 - Knight Probability in Chessboard

題目連結

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

題目敘述

有一隻西洋棋盤上的騎士在 (r, c) 的位置。而棋盤大小是 N x N 的。請問這只騎士隨機走 K 個馬步之後，仍然留在棋盤上的機率為何？每一個馬步都有 8 個方向可以選，因此往任何一方向的機率都是 1/8=0.125。

解題思考

我們可以紀錄盤面上行走 i 步之後，留在每一個格子上頭的機率為何。因此轉移的時候就把這個機率乘上八分之一然後加到下一個格子囉！有趣的是，這題用 python 寫可以用 generator 生出下一步可以踏到哪些地點～

參考程式碼 (Python3)

from collections import defaultdict

class Solution:
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        dp = {}
        dp[(r, c)] = 1.0

        def get_valid_next_places(x, y):
            dlist = [(-2, -1), (-1, -2), (1, 2), (2, 1),
                     (-1, 2), (-2, 1), (1, -2), (2, -1)]
            for dx, dy in dlist:
                if 0 <= x + dx < N and 0 <= y + dy < N:
                    yield x + dx, y + dy

        for step in range(K):
            nxt = defaultdict(lambda: 0.0)
            for state, prob in dp.items():
                x, y = state
                for p, q in get_valid_next_places(x, y):
                    nxt[(p, q)] += prob / 8.0
            dp = nxt

        return sum(dp.values())

大部分在處理機率題目的時候，往往都會遇到精確度的問題。不過這題基本上因為每一次都是除以 1/8 因此相對誤差可以少一點（因為1/8 是 2 的整數次方，處理起來精確度比較不會掉）如果真的要認真處理的話可能要在同一個位置上，精確地計算有多少路徑從原點走到該處。

此外，我們也可以把這個轉移關係，利用矩陣的方式儲存下來，而走 K 步就相當於矩陣的 K 次方。當 K 遠大於 N 的時候，我們可以僅用 O(log K) 次矩陣乘法達到我們要的目標。這個方法也較為有效。