斐波那契数列

找寻数字规律

// O(2的N次方)
public int f(int n){
    if(n < 1){
        return 0;
    }
    
    if(n == 1 || n == 2){
        return 1;
    }
    return f1(n - 1) + f1(n - 2)
    
}

//O(N )
public int f2(int n){
    if(n < 1){
        return 0;
    }
    if(n == 1 || n == 2){
        return 1;
    }
    
    int result = 1;
    int pre = 1;
    int tmp = 0;
    
    for(int i = 3; i <= n; i++){
        tmp = result;
        result = pre + res;
        pre = tmp;
    }
    return res;
}


public int c1 (int n){
    if(n < 1){
        return 0;
    }
    if(n = 1 || n = 2 || n = 3){
        return n;
    }
    return c1(n - 1) + c2(n - 3);
}


public int c2(int n){
    if(n < 1){
        return 0;
    }
    if(n = 1 || n = 2 || n = 3){
        return n;
    }
    
    int res = 3;
    int pre = 2;
    int prepre = 1;
    int tmp1 = 0;
    int tmp2 = 0;
    for(int i = 4; i <= n; i++){
        tmp1 = res;
        tmp2 = pre;
        res = res + prepre;
        pre = tmp1;
        prepre = tmp2;
    }
    return res;
    
}