问题描述：
假设有个楼梯，每次只能走3步或者5步，问到达第N节会有几种组合？
思路分析：
这个问题需要反过来思考才能比较容易的找到规律。总共有N级台阶，因为每次要么上3阶要么上5阶，因此对于第N级台阶来说，它的前一步要么是在N-3阶处要么是在N-5阶处。在N-3阶处时上3阶到N级台阶，在N-5阶处时上5级到N级台阶。因此，可以用公式表示为f(n)=f(n-3)+f(n-5)，这就变成了一个典型的递归了。像这种公式，在数列中有一个比较著名的数列叫做“斐波那契数列”，当然这里是3和5可以看做是一种变形的“斐波那契数列”；如果把3和5变成1/2就是完美的斐波那契数列了；
补充：斐波那契数列是满足F(n)=F(n-1)+F(n-2) 的数列
好了既然分析出规律了，那么我们用代码实现以下
方法一：递归实现
时间复杂度：O(!n)
public static int countStep(int n) {
if (n < 3) { //当n小于最小阶数时，没有可能的方案
return 0;
} else if (n == 3) { //当前值等于3时.只有一种可能
return 1;
} else if (n > 3 && n < 5) {//当前值大于3并且者小于5时.没有可能的方案
return 0;
} else if (n == 5) { //当n==5时只有一种可能
return 1;
} else { //n>5时，采用递归的方式进行计算
return countStep(n - 3) + countStep(n - 5);
}
}
方法二：动态规划
方法一种的单纯递归的时间复杂度过高，我们可以将之前计算过的结果存放到map中，如果之后map中存在则直接获取；
public static int climbStairs(int n, Map<Integer, Integer> map) {
if (n < 3) { //当n小于最小阶数时，没有可能的方案
return 0;
} else if (n == 3) { //当前值等于3时.只有一种可能
return 1;
} else if (n > 3 && n < 5) {//当前值大于3并且者小于5时.没有可能的方案
return 0;
} else if (n == 5) { //当n==5时只有一种可能
return 1;
} else if (map.containsKey(n)) {//若Map中已经存在之前的计算结果，则直接从map中获取
return map.get(n);
} else { //n>5时，采用递归的方式进行计算
int temp = climbStairs(n - 3, map) + climbStairs(n - 5, map);
map.put(n, temp);
return temp;
}
}
上述动态规划在n比价小的时候并不能体现其优势，但当n较大时，就有可一避免出现多处的重复计算的情况，较少时间复杂度；
拓展思考：
变形一：每次能走3阶、5阶、7阶时，有多少种可能？
思路：F(n)=F(n-3)+F(n-5)+F(n-7)
变形二：每次最多走M阶，问走到N阶有多少种可能？
思路：F(n)=F(n-1)+F(n-2)+F(n-3)……F(n-m)
代码实现
public static int countM(int n, int m, Map<Integer, Integer> map) {
int count = 0;
if (n == 0) {
return 1;
}
if (map.containsKey(n)) {
return map.get(n);
} else if (n >= m) {
for (int i = 1; i <= m; i++) {
count += countM(n - i, m, map);
}
} else {
count += countM(n, n, map);
}
map.put(n, count);
return count;
}
总结：该算法是对菲波那切数列的应用，一般情况下,一旦能用数列的形式表示某种关系那么最先想到的就是递归。该题的难点是能够找到递归规律以及在递归中各种数值的划分。
参考链接：N级台阶，一次上1级或2级或3级或M级，总共有多少种走法
标签：map,return,数列,递归,int,else,斐波,那契 From： https://www.cnblogs.com/lsgspace/p/16894372.html