算法系列:斐波那契数列问题

问题描述:

  假设有个楼梯,每次只能走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级,总共有多少种走法

发表评论

相关文章