问题
一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
思路
当n=1时，只有一种跳法，及f(1)=1，当n=2时，有两种跳法，及f(2)=2，当n=3时，可以从n=1直接跳到n=3，也可以从n=2直接跳到n=3，及f(3)=f(1)+f(2)=3...，所以可以使用递归，自顶向下，一步一步求解，但是仔细分析一下，如果n=10，需要求得f(9)和f(8)，而f(9)=f(8)+f(7)，f(8)=f(7)+f(6)，可以很明显看到，求了重复的f(8)和f(7)，随着n增大，这种复杂度是呈指数倍增长。
package offer009; import java.util.Scanner;
import java.util.concurrent.TimeUnit; /**
* @Title: Main.java
* @Package: offer009
* @Description 青蛙跳台阶，递归实现（计算量大）
* @author Han
* @date 2016-4-18 下午1:24:17
* @version V1.0
*/ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in);
int n = 0; while(scanner.hasNext()){ n = scanner.nextInt();
//开始时的纳秒
long start = System.nanoTime();
long steps = getSteps(n);
//花费的纳秒数
long during = System.nanoTime() - start;
//将纳秒转换为毫秒
long seconds = TimeUnit.MILLISECONDS.convert(during, TimeUnit.NANOSECONDS); System.out.println(steps);
System.out.println("当n为" + n + "时，花费时间为" + seconds + "毫秒");
}
} private static long getSteps(int n) { if(n < 1)
throw new RuntimeException("Error Input"); if(n == 1)
return 1;
else if(n == 2)
return 2;
else
return getSteps(n - 1) + getSteps(n - 2);
}
}
测试
当n>40的时候，就会发现计算已经开始变慢了。
思路
另一种解法，子底向上方法，类似于动态规划，此次的结果为下回计算的使用，大量减少计算时间。
package offer009other; import java.util.Scanner;
import java.util.concurrent.TimeUnit; /**
* @Title: Main.java
* @Package: offer009other
* @Description 青蛙跳台阶，动态规划实现（计算量大）
* @author Han
* @date 2016-4-18 下午1:38:17
* @version V1.0
*/ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in);
int n = 0; while(scanner.hasNext()){ n = scanner.nextInt();
//开始时的纳秒
long start = System.nanoTime();
long steps = getSteps(n);
//花费的纳秒数
long during = System.nanoTime() - start;
//将纳秒转换为毫秒
long seconds = TimeUnit.MILLISECONDS.convert(during, TimeUnit.NANOSECONDS); System.out.println(steps);
System.out.println("当n为" + n + "时，花费时间为" + seconds + "毫秒");
}
} private static long getSteps(int n) { long forgStepMinusOne = 2;
long forgStepMinusTwo = 1;
long steps = 0; for(int i = 3; i <= n; i++){ //当前n步有的跳法
steps = forgStepMinusOne + forgStepMinusTwo;
//为下一次的计算做准备，此次求得是n+1-2步的跳法个数
forgStepMinusTwo = forgStepMinusOne;
//为下一次的计算做准备，此次求得是n+1-1步的跳法个数
forgStepMinusOne = steps;
} return steps;
}
}
测试
总结
递归实现Fibonacci数列易懂，但是进行了太多的无谓的计算。