Bài toán: 688. Xác suất tồn tại của mã tế trên bàn cờ

Cách tiếp cận: Có tối đa k * n * n trạng thái, đáp ứng yêu cầu về thời gian. Phương pháp 1: Đệ quy + Tìm kiếm theo chiều sâu (DFS). Độ phức tạp thời gian là O(k * n²), chi tiết xem trong chú thích.

Phiên bản C++:

class Solution {
public:
    // tám hướng di chuyển
    int huongDiChuyenX[8]={-2,-2,-1,-1,1,1,2,2};
    int huongDiChuyenY[8]={-1,1,-2,2,-2,2,-1,1};
    double dfs(int kichThuocBanCo, int buocDi, int hang, int cot, vector<vector<vector<double>>> &trangThai){
        // kiểm tra ngoài biên
        if(hang<0||hang>=kichThuocBanCo||cot<0||cot>=kichThuocBanCo) return 0;
        // trạng thái đã được tính toán
        if(trangThai[buocDi][hang][cot]!=-1) return trangThai[buocDi][hang][cot];
        // bước cuối cùng vẫn trên bàn cờ
        if(buocDi==0) return 1;
        // tích lũy xác suất
        double ketQua=0;
        for(int i=0;i<8;i++){
            ketQua+=dfs(kichThuocBanCo,buocDi-1,huongDiChuyenX[i]+hang,huongDiChuyenY[i]+cot,trangThai);
        }
        // chia 8 vì mỗi hướng có xác suất 1/8
        return trangThai[buocDi][hang][cot]=ketQua/8;
    }
    double tinhXacSuat(int n, int k, int hang, int cot) {
        // mảng nhớ
        vector<vector<vector<double>>> trangThai(k+1,vector<vector<double>>(n,vector<double>(n,-1)));
        // gọi hàm đệ quy
        return dfs(n,k,hang,cot,trangThai);
    }
};

Phiên bản Java:

class Solution {
    // tám hướng di chuyển
    int[] huongDiChuyenX={-2,-2,-1,-1,1,1,2,2};
    int[] huongDiChuyenY={-1,1,-2,2,-2,2,-1,1};
    double dfs(int kichThuocBanCo, int buocDi, int hang, int cot,double[][][] trangThai){
        // kiểm tra ngoài biên
        if(hang<0||hang>=kichThuocBanCo||cot<0||cot>=kichThuocBanCo) return 0;
        // trạng thái đã được tính toán
        if(trangThai[buocDi][hang][cot]!=-1) return trangThai[buocDi][hang][cot];
        // bước cuối cùng vẫn trên bàn cờ
        if(buocDi==0) return 1;
        // tích lũy xác suất
        double ketQua=0;
        for(int i=0;i<8;i++){
            ketQua+=dfs(kichThuocBanCo,buocDi-1,huongDiChuyenX[i]+hang,huongDiChuyenY[i]+cot,trangThai);
        }
        // chia 8 vì mỗi hướng có xác suất 1/8
        return trangThai[buocDi][hang][cot]=ketQua/8;
    }
    public double tinhXacSuat(int n, int k, int hang, int cot) {
        // mảng nhớ
        double[][][] trangThai = new double[k+1][n][n];
        for(int i=0;i<k+1;i++){
            for(int j=0;j<n;j++){
                Arrays.fill(trangThai[i][j],-1);
            }
        }
        // gọi hàm đệ quy
        return dfs(n,k,hang,cot,trangThai);
    }
}

Phương pháp 2: Phi đệ quy, sử dụng quy hoạch động. Độ phức tạp thời gian là O(k * n²), chi tiết xem trong chú thích.

Phiên bản C++:

class Solution {
public:
    // hướng di chuyển
    int huongDiChuyenX[8]={-2,-2,-1,-1,1,1,2,2};
    int huongDiChuyenY[8]={-1,1,-2,2,-2,2,-1,1};
    
    double tinhXacSuat(int kichThuocBanCo, int soBuocDi, int hang, int cot) {
        // mảng trạng thái, +4 để tránh lỗi truy cập ngoài mảng
        vector<vector<vector<double>>> trangThai(soBuocDi+1,vector<vector<double>>(kichThuocBanCo+4,vector<double>(kichThuocBanCo+4)));
        // khởi tạo trạng thái hợp lệ
        for(int i=2;i<kichThuocBanCo+2;i++){
            for(int j=2;j<kichThuocBanCo+2;j++){
                trangThai[0][i][j]=1;
            }
        }
        // quy hoạch động
        for(int z=1;z<=soBuocDi;z++){
            for(int i=2;i<kichThuocBanCo+2;i++){
                for(int j=2;j<kichThuocBanCo+2;j++){
                    // tám hướng
                    for(int c=0;c<8;c++){
                        trangThai[z][i][j]+=trangThai[z-1][i+huongDiChuyenX[c]][j+huongDiChuyenY[c]];
                    }
                    trangThai[z][i][j]/=8;
                }
            }
        }
        return trangThai[soBuocDi][hang+2][cot+2];
    }
};

Phiên bản Java:

class Solution {
    // hướng di chuyển
    int[] huongDiChuyenX={-2,-2,-1,-1,1,1,2,2};
    int[] huongDiChuyenY={-1,1,-2,2,-2,2,-1,1};
    public double tinhXacSuat(int kichThuocBanCo, int soBuocDi, int hang, int cot) {
        // mảng trạng thái, +4 để tránh lỗi truy cập ngoài mảng
        double[][][] trangThai = new double[soBuocDi+1][kichThuocBanCo+4][kichThuocBanCo+4];
        // khởi tạo trạng thái hợp lệ
        for(int i=2;i<kichThuocBanCo+2;i++){
            Arrays.fill(trangThai[0][i],2,kichThuocBanCo+2,1);
        }
        // quy hoạch động
        for(int z=1;z<=soBuocDi;z++){
            for(int i=2;i<kichThuocBanCo+2;i++){
                for(int j=2;j<kichThuocBanCo+2;j++){
                    // tám hướng
                    for(int c=0;c<8;c++){
                        trangThai[z][i][j]+=trangThai[z-1][i+huongDiChuyenX[c]][j+huongDiChuyenY[c]];
                    }
                    trangThai[z][i][j]/=8;
                }
            }
        }
        return trangThai[soBuocDi][hang+2][cot+2];
    }
}