《剑指offer》面试题9 斐波那契数列 Java版

书中方法一：递归，这种方法效率不高，因为可能会有很多重复计算。

	public long calculate(int n){

		if(n<=0){

			return 0;

		}

		if(n == 1){

			return 1;

		}

		return calculate(n-1) + calculate(n-2);

	}

书中方法二：更好的方法是将这个斐波那契数列的计算理解成动态规划，第n步的结果依赖于第n-1步和第n-2步的结果，状态转移方程很容易写出来。

	public long calculate2(int n){

		if(n <= 0)return 0;

		if(n == 1)return 1;

		long preLast = 0;

		long last = 1;

		long result = 0;

		for(int i=2; i<=n; i++){

			result = preLast + last;

			preLast = last;

			last = result;

		}

		return result;

	}

扩展：青蛙跳阶，一次可以跳1阶或2阶，问跳上n阶台阶有多少种跳法。

依旧可以利用动态规划的思想，第m阶的跳法总数可由第m-1阶的跳法总数加上第m-2阶的跳法总数得到。从头开始遍历到n就可以求出第n阶的跳法总数。

巴特西

《剑指offer》面试题9 斐波那契数列 Java版

最新文章

热门文章