走到指定位置有多少种方式-从暴力递归到动态规划(java)-Toy模板网

这篇具有很好参考价值的文章主要介绍了走到指定位置有多少种方式-从暴力递归到动态规划(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

假设有排成一行的N个位置记为1~N，
N一定大于或等于2
每次只能走一个位置
开始时机器人在其中的M位置上(M一定是1~N中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到N-1位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；规定机器人必须走K步，
最终能来到P位置(P也是1~N中的一个)的方法有多少种给定四个参数 N、M、K、P，
返回方法数

暴力递归

解题思路:
类似爬楼梯的递归,每当选择一个位置时,步数会减一,
然后继续去递归别的可能性
一直到步数为0
如果刚好此时在指定位置,这种方法有效,返回1,否则返回0.
注意在1位置和终点位置时,只能单向选择.

代码演示,

  /**
     * 求有多少种走法
     * @param M
     * @param K
     * @param P
     * @param N
     * @return
     */
    public static int goWay(int M,int K,int P,int N){
        //边界条件,也可以再题意中限制掉,
        if(N < 2 || M < 1 || K < 1 || P < 1 || P > N || M > N){
            return -1;
        }
        return process(M,K,P,N);
    }

    /**
     *  机器人走到目标位置的有多少种方式的递归
     * @param M 机器人当前所在位置
     * @param K 还有K 步要走
     * @param P 目标位置
     * @param N 总共有多少位置.
     */
    public static int process(int M ,int K ,int P ,int N){
    	//base case 剩余0步,走完了,
    	//查看此时如果在指定位置,一种有效走法,返回1,
    	//否则返回0
        if(K == 0){
            return M == P ? 1 : 0;
        }
        //在1位置时 只能向右走
        if (M == 1){
            return process(M + 1,K - 1,P,N);
        }
        //在N 位置时 只能向左走
        if(M == N ){
            return process(N - 1,K - 1,P,N);
        }
        //z中间时可以向走也可以向右.
        return process(M - 1,K - 1,P,N) + process(M + 1,K - 1,P,N);
    }

递归+缓存

思路;
缓存是为了解决重复计算的问题,
思考下这个递归种的重复计算是什么,
就是在相同位置还剩相同步数的情况,
我们可以用缓存把这个记录下来,
位置和剩余步数两个参数,因为要用二维数组.

代码演示:

  /**
     * 递归加压缩
     * @param M
     * @param K
     * @param P
     * @param N
     * @return
     */
    public static int goWay2(int M ,int K ,int P ,int N){
        //边界条件,也可以再题意中限制掉,
        if(N < 2 || M < 1 || K < 1 || P < 1 || P > N || M > N){
            return -1;
        }
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N ;i++){
            for (int j = 0; j <= K;j++){
                dp[i][j] = -1;
            }
        }
        return process2(M,K,P,N,dp);
    }

    /**
     *  递归加缓存
     * @param M 机器人当前所在位置
     * @param K 还有K 步要走
     * @param P 目标位置
     * @param N 总共有多少位置.
     * @param dp 缓存.
     */
    public static int process2(int M ,int K ,int P,int N,int[][]dp){
    //记忆化搜索,已经有了 就直接返回
        if(dp[M][K] != -1){
            return dp[M][K];
        }
        int ans = 0;
        if (K == 0){
            ans = M == P ? 1 : 0;
        } else if (M == 1) {
            ans = process2(M + 1,K - 1,P,N,dp);

        } else if (M == N) {
            ans = process2(M - 1,K - 1,P,N,dp);

        }else{
            ans = process2(M - 1,K - 1,P,N,dp)+process2(M + 1,K - 1,P,N,dp);
        }
        //将结果保存起来
        dp[M][K] = ans;
        return ans;
    }

动态规划

思路:
动态规划和第二种递归加缓存大致相同,
不同的是,动态规划是要根据规则先把缓存表填满.
然后调用时直接从表中取.

代码演示

 /**
     * 动态规划
     * @param M 机器人当前所在位置
     * @param K 还有K 步要走
     * @param P 目标位置
     * @param N 总共有多少位置.
     * @return
     */
    public static int goWay3(int M ,int K ,int P,int N){

        int[][] dp = new int[N + 1][K + 1];
        dp[P][0] = 1;
        //i 所要走的步数
        for (int i = 1; i <= K;i++){
            dp[1][i] = dp[2][i - 1] ;
            //j 现在所在的位置.
            for(int j = 2;j < N ;j++){
                dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
            }
            dp[N][i] = dp[N - 1][i - 1];
        }
        return dp[M][K];
    }