题解 | #跳台阶#

fibonacci 数列 【数学】的使用哈 我的笨方法

int jumpFloor(int number ) {
    // write code here
    if(number ==1 )
    return 1;
    if(number == 2)
    return 2;
    
    return jumpFloor(number-1)+jumpFloor(number-2);
    
}

递归开销，有重复计算

用空间省时间

int f[100]={0}; //空间在这里
/**
 * 
 * @param number int整型 
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    if(number <= 1 )
    return 1;
    if(f[number] >0)
        return f[number];
    
    return f[number] = jumpFloor(number-1) + jumpFloor(number-2);
    
}

第三种 空间和效率最好 还简单的方法

int f[100]={0};
/**
 * 
 * @param number int整型 
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    if(number <= 1 )
    return 1;
    // if(f[number] >0)
    //     return f[number];
    
    // return f[number] = jumpFloor(number-1) + jumpFloor(number-2);

    int a = 1 ,b =1 , c=1;
    for(int i= 2 ; i<= number ;i++){
        c = a + b;

        b = a; //这个顺序重要【】
        a = c ;//bigger 

    }    

    return c;
}

参考：https://blog.nowcoder.net/n/bd31ad8896db41a6882756245cc3930b