python每日一题【剑指 Offer 10- I. 斐波那契数列】

day12-2022.11.06

题目信息来源
作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm
来源：力扣（LeetCode）

动态规划知识点

参考链接：

算法-动态规划 Dynamic Programming–从菜鸟到老鸟_HankingHu的博客-CSDN博客_动态规划

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

动态规划问题的两个特点：

重叠子问题，只计算一次，记住运算的结果。记住求解的方式有两种：自顶向下的备忘录法（记忆化递归，运行过一次就保存，后面再需要，就直接查找）和自底向上（递归是自顶向下）。因为递归还会有额外的开销，所以动态规划要好一点。

最优子结构，子问题可以独立求解，且子问题最优解组合可得整个问题的最优解。所以是先解决子问题，再由子问题往上计算父问题，自底向上。

1. 状态定义DP： 构建问题最优解模型，包括问题最优解的定义、有哪些计算解的自变量；
2. 初始状态： 确定基础子问题的解（即已知解），原问题和子问题的解都是以基础子问题的解为起始点，在迭代计算中得到的；
3. 转移方程： 确定原问题的解与子问题的解之间的关系是什么，以及使用何种选择规则从子问题最优解组合中选出原问题最优解；
4. 返回值： 确定应返回的问题的解是什么，即动态规划在何处停止迭代；

剑指 Offer 10- I. 斐波那契数列

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

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
1
2

题解

class Solution:
    def fib(self, n: int) -> int:
        if n==0:return 0
        if n==1:return 1
        dpi_1 = 1
        dpi_2 = 0
        for i in range(2, n+1):
            dpi = (dpi_2 + dpi_1)%1000000007
            dpi_2 = dpi_1
            dpi_1 = dpi
            if i==n:return dpi
1
2
3
4
5
6
7
8
9
10
11