剑指Offer算法题-青蛙跳台阶的问题

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？

答题思路

1. 如果只有1级台阶，那显然只有一种跳法
2. 如果有2级台阶，那么就有2种跳法，一种是分2次跳。每次跳1级，另一种就是一次跳2级
3. 如果台阶级数大于2，设为n的话，这时我们把n级台阶时的跳法看成n的函数，记为,第一次跳的时候有2种不同的选择：一是第一次跳一级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为,二是第一次跳二级，此时跳法的数目等于后面剩下的n-2级台阶的跳法数目，即为,因此n级台阶的不同跳法的总数为，不难看出就是斐波那契数列

数学函数表示如下

code

这里需要注意一下溢出的问题，因为在swift里若相加溢出，则会直接crash，所以这里相加使用了 &+，溢出后返回nil

func fibonacci(number: UInt64) -> UInt64? {
    if number == 1 {
        return 1
    }else if number == 2 {
        return 1
    }
    var fibNMinusOne:UInt64 = 1
    var fibNMinusTwo:UInt64 = 1
    var fibN:UInt64 = 0
    for _ in 3...number {
        fibN = fibNMinusOne &+ fibNMinusTwo
        if(fibN < fibNMinusOne) {
            return nil
        }
        fibNMinusTwo = fibNMinusOne
        fibNMinusOne = fibN
    }
    return fibN
}

若把条件修改成一次可以跳一级，也可以跳2级...也可以跳上n级呢？

思路

1. 如果台阶级数为n的话，这时我们把n级台阶时的跳法看成n的函数，记为,第一次跳的时候有n种不同的选择：若是第一次跳一级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为,若是第一次跳m(m<n)级，此时跳法的数目等于后面剩下的n-m级台阶的跳法数目，即为,若是第一次跳n级，此时跳法的数目等于1.所以
2. 因此
3. 两式相减得到
4. 因此可以得到下面的结果
   

答案

若把条件修改成一次可以跳一级，也可以跳2级...也可以跳上n级呢，则