复试上机准备之跳台阶

Author Avatar
Patrick 3月 06, 2019

题目要求

超级青蛙跳台阶。一个台阶总共有 n 级,超级青蛙有能力一次跳到 n 阶台阶,也可以一 次跳 n-1 阶台阶,也可以跳 n-2 阶台阶……也可以跳 1 阶

分析

a[1] = 1, a[2] = 2.

对于三级台阶,可以第一步跳三步,方法为 1;可以第一步跳两步,还剩一步,方法和 a[3 - 2] 相同;也可以第一步跳一步,还剩两步,方法和 a[3 - 1] 相同。最终结果为 1 + 1 + 2 = 4 = 2^2

同理 a[4] = 1 + 1 + 2 + 4 = 8 = 2^3

a[n] = 2^(n - 1)