我想到的是迭代法，从底向上的方法：先得到f(0)、f(1)的值，然后根据这两个值计算序列后面的值。
package Chap2; public class Fibonacci { /** * 推荐迭代法 */ public int fib(int n) { if (n <= 0) { return 0; } int a = 0; int b = 1; while (n > 0) { b = a + b; a = b - a; // a + b -a -> a = b也就是原来的b赋值给a n--; } return a; } }当然还有递归法，时空开销较大，不推荐。
public int fib2(int n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } return fib2(n-1) +fib(n-2); }到达1级台阶只有1种可能，到达2级台阶有2种可能；可记为f(1) = 1,f(2) = 2。要到达3级台阶，可以选择在1级台阶处起跳，也可以选择在2级台阶处起跳，所以只需求到达1级台阶的可能情况 + 到达2级台阶的可能情况，即f(3) = f(2) +f(1)
同理到达n级台阶，可以在n-1级台阶起跳，也可在n-2级台阶起跳，f(n) = f(n-2)+f(n-1)
可以看做是斐波那契数列。
package Chap2; public class JumpFloor { /** * @param target 要到达的第n级台阶 * @return 到达n级台阶总共的跳法可能 */ public int jumpFloor(int target) { if (target <= 0) { return 0; } if (target == 1) { return 1; } int a = 1; int b = 2; while (target > 1) { b = a + b; a = b - a; target--; } return a; } }这道题还有扩展，如下
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。注意和上题的区别。
到达1级台阶只有1种可能，到达2级台阶有2种可能；可记为f(1) = 1,f(2) = 2。要到达3级台阶，可以选择在1级台阶处起跳，也可以选择在2级台阶处起跳，也可直接跳到3级，所以只需求到达1级台阶的可能情况 + 到达2级台阶的可能情况 + 1，即f(3) = f(2) +f(1) + 1同理到达n级台阶，可以在n-1级台阶起跳，可在n-2、n-1、n-3…级台阶起跳，f(n) = f(n-1)+f(n-2)+f(n-3)…+1,如果令f(n-n) = f(0) = 1,上式可表示为f(n) = f(n-1)+f(n-2)+f(n-3)…+f(n-n)，有了通项公式找出规律也不是难事了，不过还有种更好理解的思路：前n-1级台阶，每级台阶都有两种选择——跳到此或不跳到此，对于最后一级n级，没得选择，必须跳到这里，所以总共有有2^(n-1)种跳法。
这个问题本质还是斐波那契数列…
覆盖2*n的矩形的方法记为f(n)。
当最后一步是竖着放时候，说明前一步已经覆盖了2*(n-1)，记为f(n - 1)当最后一步是横着放的时候，倒数第二次也必然是横着放的。这个状态已经覆盖了2* (n-2)，记为f(n - 2)因为最后一步只有横竖放两种可能，所以将上述两种方法可能性加起来即可。
覆盖2*1的矩形只有1种方法，覆盖2*2的矩形有横竖2种方法。于是f(1) = 1, f(2) = 2
这和能跳1级也能跳2级的青蛙是一样的。代码直接copy过来就行！
本文参考文献： [1]github.com/haiyusun/data-structures
快乐李同学(李俊德-大连理工大学) 认证博客专家 数据结构 Java Android B站/微博/微信公众号:快乐李同学。大连理工大学软件工程2020毕业学生。大连理工大学2018-2019学年科技创新奖学金。2个国家级项目，2个国家级奖项，5个省级奖项，8个校级奖项（总项目经费和竞赛奖金达2万2千元）。2018-2019年在中国核心期刊《现代计算机》发表2篇项目相关论文，分别署名第一、第二作者（知网可查）。2018-2019年申请2份项目软件著作权，并发布软件(编程乐园、编程学院)到Google,腾讯,百度,华为,小米等应用商店。大学英语六级568分。