剑指--变态跳台阶

陷入了死局中。如果n级台阶有f(n)种跳法，那么可以先跳1级，再f(n-1),也可以f(n-1),再跳1级，还可以直接跳上去。
所以一开始求得f(n)=2f(n-1)+1;但是总感觉不对。为什么不对，因为先跳1级，再f(n-1),也可以f(n-1),再跳1级。有重复的情况。重复在前一种也可以最后只跳一级，后一种也可以一开始跳一级。想法不对应该及时推倒重建。
有很多思路可以避开这里：
1.因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+…+f(1),又因为f(n-1)=f(n-2)+f(n-3)+…+f(1)
所以f(n)=2f(n-1)
2.每个台阶都有跳与不跳两种情况，最后一个台阶必须跳上去。也可以用落脚点理解。所以共用2^(n-1)种情况。
如果这样，可以用幂函数。
#include
2^(n-1)=pow(2,n-1)；
3.同学说，n+1级台阶，去掉和不去掉第一级，都有f(n)种。也可以推出f(n)=2f(n-1)