剑指Offer面试题10：斐波那契数列

一、题目

示例：

输入：4
返回值：3
说明：
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。

二、题解

2.1解法一：迭代相加

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

斐波那契数列初始化第1项与第2项都是1，则根据公式第0项为0，可以按照斐波那契公式累加到第项。

具体做法：

• step 1：低于2项的数列，直接返回n。
• step 2：初始化第0项，与第1项分别为0，1.
• step 3：从第2项开始，逐渐按照公式累加，并更新相加数始终为下一项的前两项。

Java实现代码：

public class Solution {
    public int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if(n 

解法二：递归法

知识点：递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

思路：

我们也可以根据公式倒推：

• 终止条件：当递归到数列第1项或是第0项的时候，可以直接返回数字。
• 返回值：返回这一级子问题的数列值。
• 本级任务：获取本级数列值：即前两项相加。

具体做法：

• step 1：低于2项的数列，服务器托管网直接返回n。
• step 2：对于当前n，递归调用函数计算两个子问题相加。

Java实现代码：

public class Solution {
    public int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if (n 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fw服务器托管网qtg.net

相关推荐: Vue中组件之间通信的-六大方式-总结方式一：props/$emit
{{title}} 方式二：eventBus（$emit/$on）方式三：Vuex方式四：$attrs/$listeners
方式五：provide/injectA 组件

方式一：props/$emit 父组件向子组件传值 通过一个例子，说明父组件如何向子组件传递值：在子组件Users.vue中如何获取父组件App.vue中的数据 users:[“Henry”,”Bucky”,”Emily”] 注：父组件通过props向下传递数…