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

更多算法和数据结构笔记