爬楼梯问题-从暴力递归到动态规划(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 caseif (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];}

暴力递归到动态规划专题

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

零钱兑换,凑零钱问题,从暴力递归到动态规划（java）

斐波那契数列-从暴力递归到动态规划