题解 | #跳台阶#

思路

这是一个斐波那契数列。以3为例:

F(3) = F(2) + F(1)

F(1) = 1

F(2) = 2

所以F(3) = 1 + 2 = 3

可以用递归法求解。

这种题目的关键就是找通项公式。

代码

public class Solution {
    public int jumpFloor(int target) {
        if (target == 1) return 1;
        if (target == 2) return 2;
        return jumpFloor(target - 2) + jumpFloor(target - 1);
    }
}

当然这样解题虽然很简单，却很浪费空间。这种类型的题其实和斐波那契数列是一类问题，都可以用动态规划算法来做：

/**
 * 
 * @param number int整型 
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    if (number == 1) return 1;
    if (number == 2) return 2;

    int dp[number+1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= number; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[number];
}

利用了C语言快而小的特性，以及动态规划算法之后，此时的时间消耗仅5ms，内存占用不过542KB。同样的算法，用Go来写，速度上与C持平，但是空间占用还是略大,1200KB：

package main

/**
 * 
 * @param number int整型 
 * @return int整型
*/
func jumpFloor( number int ) int {
    // write code here
    if number == 1 {
        return 1
    }
    if number == 2 {
        return 2
    }
    dp := make([]int, number+1)
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2

    for i := 3; i <= number; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }

    return dp[number]
    
}