爬楼梯问题-从暴力递归到动态规划(java)-Toy模板网

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

爬楼梯–题目描述

一个总共N 阶的楼梯（N > 0）
每次只能上一阶或者两阶。问总共有多少种爬楼方式。

示例1：
N = 1，
一步上去了，返回1.

示例2：
N = 2时。
可以第一次上一阶，再上一阶，这是一种方式，
也可以一次直接上两阶，这也是一种方式，
返回 2；

示例3：
N = 3：
可以选择， 1 1 1，
1 2
2 1
三种方式上楼，
返回3.

暴力递归

解题思路：
先确认base case:
只有一层台阶时有1种方式，
只有两层台阶时有两种方式，
当N 层台阶时，
当前这一步能选择上一层或者上两层两种可能性
因此f(N) = f(N - 1) + f(N - 2)
代码已经呼之欲出了：

代码演示：

  /**
     * 暴力递归。
     * @param N
     * @return
     */
    public static int paLouTi(int N){
        if (N <= 0){
            return 0;
        }
        return process(N);
    }
    /**
     * N层测楼梯 每次只能上一步或者两步，
     * 总共有多少种爬楼的方式。
     * @param N
     */
    public static int process(int N){
        //base case
        if (N == 1 || N == 2){
            return N;
        }
        return process(N - 1) + process(N - 2);
    }

递归+缓存

解题思路：
第一先找到重复计算的地方。
第二步把重复计算的放进缓存里，记忆化搜索
这个里面的重复计算我们举个例子：
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
这里面f(3）就在重复计算，
我们把他加进缓存里

代码演示

  /**
     * 递归加缓存的方式
     * @param N
     * @return
     */
    public static int paLouTi2(int N){
        if (N <= 0){
            return 0;
        }
        int[] ans = new int[N + 1];
        return process2(N,ans);
    }

    /**
     * 带缓存的递归  记忆化搜索
     * @param N
     * @param ans
     * @return
     */
    public static int process2(int N,int[]ans){
        //如果有值 直接返回 不在计算
        if(ans[N] != 0){
            return ans[N];
        }
        if(N == 1 || N == 2){
            ans[N] = N;
        }else{
            ans[N] = process2(N - 1,ans)+process2(N - 2,ans);
        }
        return ans[N];
    }

动态规划

动态规划就是在递归加缓存的基础上，做的改进，我们提前把缓存表计算出来，然后直接从缓存表里取值。

代码演示：

    /**
     * 动态规划
     * @param N
     * @return
     */
    public static int paLouTi3(int N ){
        if (N < 1){
            return 0;
        }
        //缓存表
        int[] dp = new int[N + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= N;i++ ){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }