剑指offer面试题10：斐波那契数列（java代码）

题目一&＃xff1a;求斐波那契数列的第n项
写一个函数&＃xff0c;输入 n &＃xff0c;求斐波那契&＃xff08;Fibonacci&＃xff09;数列的第 n 项&＃xff08;即 F(N)&＃xff09;。斐波那契数列的定义如下&＃xff1a;

F(0) &＃61; 0, F(1) &＃61; 1
F(N) &＃61; F(N - 1) &＃43; F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始&＃xff0c;之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9&＃43;7&＃xff08;1000000007&＃xff09;&＃xff0c;如计算初始结果为&＃xff1a;1000000008&＃xff0c;请返回 1。

思路

使用动态规划

• 1&＃xff09;定义dp数组&＃xff0c;dp[i]即F(N)
• 2&＃xff09;状态转移方程&＃xff1a;dp[i] &＃61; dp[i - 1] &＃43; dp[i - 2]
• 3&＃xff09;初始化数组&＃xff1a;dp[0] &＃61; 0&＃xff0c;dp[1] &＃61; 1

class Solution {public int fib(int n) {if (n &＃61;&＃61; 0) return 0;if (n &＃61;&＃61; 1) return 1;int p1 &＃61; 0, p2 &＃61; 1, p3 &＃61; 0;for (int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;) {p3 &＃61; (p1 &＃43; p2) % 1000000007;p1 &＃61; p2;p2 &＃61; p3;}return p3;}
}


复杂度分析

• 时间复杂度O(N)
• 空间辅助度O(1)

题目二: 青蛙跳台问题
一只青蛙一次可以跳上1级台阶&＃xff0c;也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9&＃43;7&＃xff08;1000000007&＃xff09;&＃xff0c;如计算初始结果为&＃xff1a;1000000008&＃xff0c;请返回 1。

输入&＃xff1a;n &＃61; 0
输出&＃xff1a;1

思路

当n为1的时候&＃xff0c;有1种走法&＃xff0c;n为2的时候有两种走法&＃xff0c;n为3的时候有3种&＃xff0c;n为4的时候有5种

1: 1

2: 2

3: f(1) &＃43; f(2)

4: f(3) &＃43; f(2)

f(n): f(n-1) &＃43; f(n-2)

分析完之后就是一个斐波拉契数列

• 那么就可以用迭代的方法来解&＃xff1a;

  class Solution {public int numWays(int n) {if (n &＃61;&＃61; 0) return 1;if (n &＃61;&＃61; 1) return 1;if (n &＃61;&＃61; 2) return 2;int p1 &＃61; 1, p2 &＃61; 2, p3 &＃61; 0;for (int i &＃61; 3; i <&＃61; n; i&＃43;&＃43;) {p3 &＃61; (p1 &＃43; p2) % 1000000007;p1 &＃61; p2;p2 &＃61; p3;}return p3;}
}


class Solution {public int numWays(int n) {int p &＃61; 0, q &＃61; 0, r &＃61; 1;for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {p &＃61; q; q &＃61; r; r &＃61; (p &＃43; q) % 1000000007;}return r;}
}


复杂度分析

• 时间复杂度O(n)
• 空间复杂度O(1)