Bob 的生存概率问题

时间:2022-10-30 22:09:24

作者: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))

其中 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]依赖以下四个位置的值

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();
    }
}

更多

算法和数据结构笔记