问题

　　一只青蛙一次可以跳上 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数列易懂，但是进行了太多的无谓的计算。