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

问题描述：

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