Leetcode斐波那契数列问题

Z时代
2024-01-10
分类：综合

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

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

这道题我们可以用递归或者动态规划来完成。

递归思路——根据给出的斐波那契数列公式，将F(N)视为一个函数，函数求值的过程中不断调用自身。

动态规划——将公式中的F视为一个数组，F(N)即数组中下标为N的值。

递归解法：

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function fib($n) {
        if($n<2){
		return $n;
	}else{
	return $this->fib($n-1)+$this->fib($n-2);
	}
        return $dp[$n];
    }
}

动态规划解法：

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function fib($n) {
        // if($n<2){
        //     return $n;
        // }
        $dp = ["0"=>0,"1"=>"1"];
        for($i=2;$i<=$n;$i++){
            $dp[$i] = ($dp[$i-1]+$dp[$i-2]) % 1000000007;
        }
        return $dp[$n];
    }
}