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

文章插图
动态规划解（可 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]依赖以下四个位置的值

Bob 的生存概率问题

推荐阅读

教你如何使用迅雷离线下载[新发布]

在“再见阿郎”中的刘金虎怎么又是金鹏？

如何通过女人面相看婚姻哪些面相的女人婚姻好

梦见和当官的同学在一起商人梦见当官的同学

皮蛋是生的还是熟的怎么判断皮蛋是生的还是熟的

梦见水里有黑鱼在游

一斤几克重，一斤等于多少千克

我们好像在哪见过歌词我们好像在哪见过歌词歌谱

商业承兑汇票是什么意思商业承兑汇票的理解

煤炭公司起名大全免费煤炭行业起名大全

天麻能泡白酒吗天麻可以和虫草花一起煲汤吗

etc不抬杆可以倒回吗 etc不抬杆可以倒回会被扣分吗

节日由来英语节日由来

瑜伽入门动作图解瑜伽入门动作图解上

五岳奇险天下第一山是哪座山天下第一山是哪座山

孕妇梦见和别人吵架孕妇梦见别人挣了很多钱

喝番茄汁有什么好处番茄汁的好处有哪些

忙碌了多少天辛苦了多少年是啥歌快去听一下吧

关于洛阳昊远机械设备有限公司简述洛阳昊远机械设备有限公司

“八岐之术”是什么？