688. Knight Probability in Chessboard

在給定棋盤範圍n、可移動步數k、起始座標row,column下，找出騎士在移動k步後仍留在棋盤上的機率是多少，如果走出棋盤外就不再繼續移動，移動方式跟中國象棋的馬一樣走對角。

原本的想法是用動態規劃的方式記錄在k=1時的機率，全部相加後去乘上(1/8)^(k-1)，可以想像移動的路徑是像樹一樣，所以當k=1時會在leaf node，在不看移動到棋盤外的步數時，每個leaf node的深度都會是一樣，每往下走一層就乘上1/8，但後來submit發現會time limit exceeded。

class Solution {
public:
    typedef vector<vector<double>> board;
    
    // 回傳留在棋盤上的總步伐數目
    // dp 儲存該位置下一步會留在棋盤的數目
    double move(board& dp, int n, int k, int row, int column){
        int directions[8][2] = {
            {-2, -1}, {-1,-2},
            {2, -1}, {1, -2},
            {2, 1}, {1, 2},
            {-2, 1}, {-1, 2}};
        
        int step = 0;
        double prob_at_leaf = 0;
        for(auto dir: directions){
            if((row + dir[0] < n && row + dir[0] >= 0) &&
            (column + dir[1] < n && column + dir[1] >= 0)){
                step++;
                if(k > 1)
                    prob_at_leaf += move(dp, n, k-1, row + dir[0], column + dir[1]);
            }
        }

        dp[row][column] = (double)step/8;

        if(k==1){
            prob_at_leaf += dp[row][column];
        }
            
        return prob_at_leaf;
    }
    double knightProbability(int n, int k, int row, int column) {
        board dp = board(n, vector<double>(n, -1));
        
        double ans = move(dp, n, k, row, column);
        return k == 0 ? 1 : ans*pow(0.125, k-1);
    }
};

最後還是想不到所以看了解答，解答給了兩個方向top-down和bottom-up，上面的想法跟top-down有點類似，只是要多一個位置去儲存k=t時的機率，若k較大時可以有效率地省下一些計算時間。原本的想法比較接近top-down，其時間複雜度需要 O(k*n²)，而空間複雜度也需要O(k*n²)

但是bottom-up可以優化空間複雜度到O(n²)，其想法是把從棋子從該格(r,c)移動出去的機率和棋子從其他格子移動到該格(r,c)的機率是等價的，然後加總所有可以移動到(r,c)的其他格子的機率，加總後再除以8就是該格移動出去的機率了。

class Solution {
public:
    typedef vector<vector<double>> board;
    
    double knightProbability(int n, int k, int row, int column) {
        board previous = board(n, vector<double>(n, 1));
        board current = board(n, vector<double>(n, 0));

        int directions[8][2] = {
            {-2, -1}, {-1,-2},
            {2, -1}, {1, -2},
            {2, 1}, {1, 2},
            {-2, 1}, {-1, 2}};

        for(size_t i=0; i<k+1; i++){
            for(size_t r=0; r<n; r++){
                for(size_t c=0; c<n; c++){
                    double sum_prob = 0;
                    for(auto dir: directions){
                        int neighbor_row = r + dir[0];
                        int neighbor_col = c + dir[1];

                        if((neighbor_row < n && neighbor_row >= 0) &&
                        (neighbor_col < n && neighbor_col >= 0)){
                            sum_prob += previous[neighbor_row][neighbor_col];
                        }
                    }
                    current[r][c] = sum_prob/8;
                }
            }
            swap(previous, current);
        }
        return current[row][column];
    }
};

最後想法上有出入的地方在於，雖然可以在k=1時省下節省時間，但回到上一層的時候仍有2^(k-2)的格子需要計算，若要節省時間便需要在多k倍的記憶體空見去紀錄當k=t時的所有格子機率。而且雖然有想到bottom-up，但完全沒想法，這裡可以要多加思考DP既然有top-up也就會有bottom-up的方式。

bottom-up dynamic programming
Time Complexity: O(k*n²)
Space Complexity: O(n²)