题解 | #跳台阶扩展问题#
跳台阶扩展问题
https://www.nowcoder.com/practice/953b74ca5c4d44bb91f39ac4ddea0fee
注意题目要求时间复杂度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);
}
}
