1. 首頁 > 生活百科 > >

Bob 的生存概率問題

生活百科

Bob 的生存概率問題作者：Grey
原文地址：
博客園：Bob 的生存概率問題
CSDN：Bob 的生存概率問題
題目描述給定五個參數 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))【Bob 的生存概率問題】其中 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();}}超時

Bob 的生存概率問題

文章插圖
動態規劃解 （可 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]依賴以下四個位置的值

推薦閱讀