Bob 的生存概率問題

作者：Grey

原文地址：

題目描述

給定五個參數 n , m , i , j , k，表示在一個 n*m 的區域，Bob 處在 (i,j) 點，每次 Bob 等概率的向上、下、左、右四個方向移動一步，Bob 必須走 k 步。如果走完之後，Bob 還停留在這個區域上，就算 Bob 存活，否則就算 Bob 死亡。請求解 Bob 的生存概率，返回字元串表示分數的方式。

題目鏈接：牛客-Bob的生存概率

暴力解法

由於 Bob 可以向四個方向任意一個方向走 k 步，所以，Bob 可以選擇走的路線總數是：4^k，即：4 的 k 次方。

接下來就是要求在 4 ^ k 總數中，哪些是存活下來的路線，定義如下遞歸函數

long process(int i, int j, int k, int n, int m)

遞歸含義表示：目前在 (i，j) 位置，還有 k 步要走，走完了如果還在棋盤中就獲得1個生存點，返回總的生存點數。

接下來是 base case，如果越界了，直接返回 0，

        if (i < 0 || i == n || j < 0 || j == m) {
            return 0;
        }

表示沒有生存機會，

如果沒有越界，但是此時正好 k == 0，說明已經有一種存活路線了，返回 1，表示一種有效路線。

        if (i < 0 || i == n || j < 0 || j == m) {
            return 0;
        }
        // 沒有越界，說明還在棋盤中，沒有步數了，直接返回一種有效路線。
        if (k == 0) {
            return 1;
        }

接下來是普遍情況， Bob 在棋盤中，可以往四面八方走，即

        long up = process(i - 1, j, k - 1, n, m);
        long down = process(i + 1, j, k - 1, n, m);
        long left = process(i, j - 1, k - 1, n, m);
        long right = process(i, j + 1, k - 1, n, m);

上述表示四面八方走返回的有效路線，四個方向的有效路線之和，就是答案，即

return up + down + left + right;

遞歸函數的完整程式碼如下

    public static long process(int i, int j, int k, int n, int m) {
        if (i < 0 || i == n || j < 0 || j == m) {
            return 0;
        }
        // 還在棋盤中！
        if (k == 0) {
            return 1;
        }
        // 還在棋盤中！還有步數要走
        long up = process(i - 1, j, k - 1, n, m);
        long down = process(i + 1, j, k - 1, n, m);
        long left = process(i, j - 1, k - 1, n, m);
        long right = process(i, j + 1, k - 1, n, m);
        return up + down + left + right;
    }

由於最後的結果要返回最簡的分數形式，所以假設有效路線是 X 種，所有可能的走法是 Y 種，那麼返回的字元串是如下形式

return (X/gcd(X,Y)) + "/" + (Y/gcd(X,Y))

其中 gcd(X,Y) 就是利用輾轉相除法得到 X，Y 的最大公約數

    public static long gcd(long m, long n) {
        return n == 0 ? m : gcd(n, m % n);
    }

暴力解法的完整程式碼如下

import java.util.Scanner;

public class Main {

    public static String livePossibility1(int i, int j, int k, int n, int m) {
        return buildExp(process(i, j, k, n, m), (long) Math.pow(4, k));
    }

    // 目前在i，j位置，還有k步要走，走完了如果還在棋盤中就獲得1個生存點，返回總的生存點數
    public static long process(int i, int j, int k, int n, int m) {
        if (i < 0 || i == n || j < 0 || j == m) {
            return 0;
        }
        // 還在棋盤中！
        if (k == 0) {
            return 1;
        }
        // 還在棋盤中！還有步數要走
        long up = process(i - 1, j, k - 1, n, m);
        long down = process(i + 1, j, k - 1, n, m);
        long left = process(i, j - 1, k - 1, n, m);
        long right = process(i, j + 1, k - 1, n, m);
        return up + down + left + right;
    }

 
    public static String buildExp(long m, long n) {
        return m / gcd(m, n) + "/" + n / gcd(m, n);
    }

    public static long gcd(long m, long n) {
        return n == 0 ? m : gcd(n, m % n);
    }

 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int i = sc.nextInt();
        int j = sc.nextInt();
        int k = sc.nextInt();
        System.out.println(livePossibility1(i, j, k, n, m)); 
        sc.close();
    }
}

超時

動態規劃解（可 AC）

根據上述暴力遞歸過程可知，遞歸函數有三個可變參數：i，j，k；所以，定義一個三維數組 dp，就可以把所有遞歸過程的中間值存下，根據 i，j，k 的可變範圍，定義如下三維數組：

long[][][] dp = new long[n][m][k + 1];

根據暴力遞歸過程的 base case，可以初始化 dp 的某些位置的值

        long[][][] dp = new long[n][m][k + 1];
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                dp[row][col][0] = 1;
            }
        }

接下來是普遍情況，通過暴力遞歸過程可知，dp[i][j][k]依賴以下四個位置的值

dp[i-1][j][k-1]

dp[i+1][j][k-1]

dp[i][j-1][k-1]

dp[i][j+1][k-1]

即：三維數組的每一層只依賴上一層的數據結果，而第一層的值已經初始化好了，所以可以根據第一層求第二層，依次求到最後一層，這個動態規劃的思路類似：象棋中的馬跳步問題
，不贅述。

動態規劃的解完整程式碼如下

import java.util.Scanner;

public class Main {

    public static String livePossibility2(int i, int j, int k, int n, int m) {
        long[][][] dp = new long[n][m][k + 1];
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                dp[row][col][0] = 1;
            }
        }
        for (int rest = 1; rest <= k; rest++) {
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    dp[r][c][rest] = pick(dp, n, m, r - 1, c, rest - 1);
                    dp[r][c][rest] += pick(dp, n, m, r + 1, c, rest - 1);
                    dp[r][c][rest] += pick(dp, n, m, r, c - 1, rest - 1);
                    dp[r][c][rest] += pick(dp, n, m, r, c + 1, rest - 1);
                }
            }
        }
        return buildExp(dp[i][j][k], (long) Math.pow(4, k));
    }

    public static String buildExp(long m, long n) {
        return m / gcd(m, n) + "/" + n / gcd(m, n);
    }

    public static long gcd(long m, long n) {
        return n == 0 ? m : gcd(n, m % n);
    }

    public static long pick(long[][][] dp, int n, int m, int r, int c, int rest) {
        if (r < 0 || r == n || c < 0 || c == m) {
            return 0;
        }
        return dp[r][c][rest];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int i = sc.nextInt();
        int j = sc.nextInt();
        int k = sc.nextInt(); 
        System.out.println(livePossibility2(i, j, k, n, m));
        sc.close();
    }
}

演算法和數據結構筆記

Tags: 動態規劃數據結構牛客演算法演算法和數據結構