问题描述:
假设有个楼梯,每次只能走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