问题

一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级,求总共有多少总跳法。

思路

从一级台阶开始,台阶只有一级,只有一种方法;2 级台阶有两种方法;3 级台阶,每次只走一步、先走一步再走两步、先走两步再走一步三种方法;4 级台阶有五种方法,既:(1->1>1->1)、(1->2->1)、(1->1->2)、(2->1->1)、(2->2)。

 N  跳法  
 1  1
 2  2 11,12 
 3  3 111,12,21
 4  5 1111,121,112,211,22 

规律

斐波那契数列 :用文字来说,就是斐波那契数列由0和1开始,之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(OEIS中的数列A000045)

代码实现

1、递归

public int climbStairs(int stairsNum){
        int[] results = new int[]{0,1,2};
        if (stairsNum <= 2)
            return results[stairsNum];

        return climbStairs(stairsNum - 1) + climbStairs(stairsNum - 2);
    }

2、非递归

菲波那切数定义就是由之前两个数相加得出,所以具体计算中只会涉及到三个数,前两个数和第三个需要计算出的数。前两个数,可初始化为 1,计算过程中缓存前两个需要的数,这样就可做到不需要递归:

public int climbStairs1(int stairsNum){
        int[] results = new int[]{1,1, 0};
        if (stairsNum < 2)
            return 1;

        for (int i = 2; i <= stairsNum; i++) {
            results[2] = results[0] + results[1];
            results[0] = results[1];
            results[1] = results[2];
        }

        return results[2];
    }

总结

笨思路就是开始时提到的,从最简单的元素开始计算,弄个三四个示例,然后寻找规律。当然更好的方法应该是懂得基本原理,如 动态规划(占坑,后补),这样更好。