题目描述

给你一个长为N，宽为M的迷宫，现在，随机给你一个Bob的位置【a，b】，然后让Bob走k步，Bob每次都只能随机向上下左右走一步，如果出了迷宫范围就算死亡，请你求出Bob走k步以后存活的概率？

暴力递归

递归出口
当bob出了迷宫范围，bob死亡，返回0
当k为0，说明走完了，如何没出范围，返回1，获取一种存活策略。
递归函数
当bob没有死亡也没有走完，此时，bob需要等概率向四个方向走，递归依次调用四个方向就能模拟等概率事件。
代码

    public static String bob(int N,int M,int a,int b,int k){
        int live=f2(N,M,a,b,k);
        return String.format("%.2f",(double)100*live/Math.pow(4,k))+"%";
    }
    
    public static int f2(int N,int M,int a,int b,int k){
        if(a>N||a<0||b>M||b<0){
            return 0;
        }
        if(k==0){
            return 1;
        }
        int live=0;
        live+=f2(N,M,a+1,b,k-1);
        live+=f2(N,M,a-1,b,k-1);
        live+=f2(N,M,a,b+1,k-1);
        live+=f2(N,M,a,b-1,k-1);
        return live;
    }

三维动态规划

三个可变参数，因此是一个三维数组。
然后根据递归的base case，k=0时，全是1
然后根据递归过程，k从1开始向上的每一层，都需要调用下一层的四个方向，如果越界就是0
代码

    public static String bob2(int N,int M,int a,int b,int k){
    	//出来就死了
        if(a>N||a<0||b>M||b<0||k<0){
            return "死定个球了";
        }
        //三维数组表示表格
        int[][][] dp=new int[N+2][M+2][k+1];
        //k=0时这一层全是1
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                dp[i][j][0]=1;
            }
        }
        for (int h = 1; h <= k ; h++) {
            for (int i = 0; i <= N; i++) {
                for (int j = 0; j <= M; j++) {
                    dp[i][j][h]=get(dp,i+1,j,N,M,h-1);
                    dp[i][j][h]+=get(dp,i-1,j,N,M,h-1);
                    dp[i][j][h]+=get(dp,i,j+1,N,M,h-1);
                    dp[i][j][h]+=get(dp,i,j-1,N,M,h-1);
                }
            }
        }
        return  String.format("%.2f",(double)100*dp[a][b][k]/Math.pow(4,k))+"%";
    }