# 变态跳台阶


## 题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

## 解题思路

设共有m种不同跳法

- 如果n=1，那么m=1
- 如果n=2，那么m=2

对于n阶台阶：

- case1：第一次跳了1个台阶，就有f（n-1）种跳法
- case2：第一次跳个2个台阶，就有f（n-2）种跳法
- ...
- case n:第一次跳了n个台阶，就有0中跳法



将所有情况加起来，对于n级台阶，有：`f(n)=f(1)+f(2)+f(3)+..+f(n-1)+1`种跳法，如果直接用该式进行计算，每次计算f(n)时需要计算`n-1`个`f`，会有很多重复计算，考虑：

```
f(1)=1 
f(2)=2 
f(3)=f(2)+f(1)+1
f(4)=f(3)+f(2)+f(1)+1
f(5)=f(4)+f(3)+f(2)+f(1)+1
      =f(4)+f(4)

f(6)=f(5)+f(4)+f(3)+f(2)+f(1)+1
      =f(5)+f(5)

```

可以发现：    
   ` f(n)=2*f(n-1)`

利用该式即可解决此问题。


## 代码

[这里](../Code/8.py)