Bob 的生存概率问题( 二 ) _生活百科

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();}}更多算法和数据结构笔记

Bob 的生存概率问题( 二 )

推荐阅读

护士节的来历

白城到长春白城到长春客车时间表

好听的双胞胎男孩名字

炒猪肚用什么配菜好吃炒猪肚用什么配菜

立秋后的第一杯奶茶是什么意思?

请评教是什么意思网上评教是什么意思

依维柯宝迪edc灯消不掉怎么回事依维柯宝迪提示灯

怎么自制减肥营养餐

冰箱里放三天的饭菜还可以吃吗饭菜放冰箱三天能吃吗

西梅可以冷冻保存吗怎么吃西梅可以冷冻保存吗

三国程普怎么死的

绝地求生怎么跑绝地求生快速跑动按键详解

2020年07月14日双子座事业爱情运势

快手小店上传商品审核多久快手商品审核多长时间

汽车用品买什么是必备的买车以后有哪些重要的车用品

狮子座生日狮子座是几月份

机动车检验去哪里办理

十二星座专属配套服装

关于感恩节的作文600字

人生自古谁无死出自哪首诗人生自古谁无死