咱们昨天给了一个青蛙跳台阶的题，和一个参考答案，今天我们详细的讲一下。
f(1)=1
f(2)=f(2-1)+f(2-2)
f(3)=f(3-1)+f(3-2)+f(3-3)
以此类推....
到n个台阶的时候f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-(n-1))+f(n-n)——①
当n=1的时候，只有一种跳法，当n=2的时候，有一次跳一阶或者两阶两种方法，以此类推
当n=n的时候，f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-(n-1))+f(n-n)
那么n=n-1的时候呢？
f(n-1)=f(0)+f(1)+f(2)+f(3)+...+f((n-1)-1)=f(0)+f(1)+f(2)+f(3)+...+f(n-2)——②
比较①②，可以得出：f(n)=2*f(n-1)
然后我们总结一下：一次有1、2、...n阶的跳的方式时，总得跳法为：
当n=0或者n=1的时候，f(n)=1,当n≥2时，f(n)=2*f(n-1)。
这种思想比较好理解，但是当n取很大的时候，往往这种效率会降低，那么有没有更好的办法呢？
这里给出一种，我们假如再每一个台阶都放上一个虫子，青蛙蹦上一个台阶就默认吃掉虫子,让青蛙跳上去,n个台阶有n只虫子（细思恐极）,最后一只虫子位于第n阶，是青蛙到达的位置,必须要有一只虫子，其他n-1个台阶就可以随意的设置有没有虫子给青蛙吃了，每一个台阶虫子存不存在有两种可能，,n-1个虫子就有2^(n-1)种（因为最后一个台阶必须存在）,然后我们就可以直接得到结果了。
明天我们继续数据结构与算法教程，我们先来讲一下，学习数据结构与算法，需要哪些数学知识来支撑，今天就到这里，喜欢的点个赞。
喜欢我就点我吧
赞赏
人赞赏
白癜风治疗最好的医院刘云涛