int fib( int n ){

    if( n == 0 )
        return 0;

    if( n == 1 )
        return 1;

    return fib(n-1) + fib(n-2);
}

vector<int> memo;

// 记忆化搜索 from top to bottom
int fib( int n ){

    if( n == 0 )
        return 0;

    if( n == 1 )
        return 1;

    if( memo[n] == -1 )
        memo[n] = fib(n-1) + fib(n-2);

    return memo[n];
}

// 动态规划 from bottom to top
int fib( int n ){

    vector<int> memo(n+1, -1);

    memo[0] = 0;
    memo[1] = 1;
    for( int i = 2 ; i <= n ; i ++ )
        memo[i] = memo[i-1] + memo[i-2];

    return memo[n];
}