注意题目要求时间复杂度O(1)，那么肯定有一个公式可以直接得出答案。

第 1 级台阶，0 级基础上跳 1 级
第 2 级台阶，第 1 级基础上跳，0 级基础上跳 2 级
第 3 级台阶，第 1 级基础上跳，第 2 级基础上跳，0 级基础上跳 3 级
第 4 级台阶，第 1 级基础上跳，第 2 级基础上跳，第 3 级基础上跳，0 级基础上跳 4 级
......
第 n 级台阶，第 1 级基础上跳，第 2 级基础上跳，......，第 n-1 级基础上跳，0 级基础上跳 n 级

可得 f(n) = f(n-1)+f(n-2)+...+f(1)+1。
由于 f(n-1) = f(n-2)+f(n-3)+...+f(1)+1。
因此 f(n) = f(n-1)+f(n-1) = 2f(n-1)
所以 {fn} 是等比数列，公比 q 等于2。
根据等比数列公式 fn = f(1)*q^(n-1)。
所以就有 fn = 2^(n-1)。

完整 Java 版代码 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(new Solution().solution(n));
    }
}

class Solution {
    public int solution(int n) {
        return (int)Math.pow(2, n-1);
    }
}