浅谈：算法中的斐波那契数（五）

方法四：自底向上进行迭代

算法：

• 若 N <= 1，则返回 N。
• 若 N == 2，则返回 fib(2-1) + fib(2-2) = 1。
• 使用迭代的方法，我们至少需要三个变量存储 fib(N), fib(N-1) 和 fib(N-2)。
• 预置初始值：

1. current = 0。
2. prev1 = 1，代表 fib(N-1)。
3. prev2 = 1，代表 fib(N-2)

• 我们从 3 计算到 N；0，1，2对应的斐波那契数是预先计算。
• 设置 current = fib(N-1) + fib(N-2)，因为 current 代表的是当前计算的斐波那契数。
• 设置 prev2 = fib(N-1)。
• 设置 prev1 = current。
• 当我们到达 N+1，将退出循环并返回 current。

Java 实现

class Solution { public int fib(int N) { if (N <= 1) { return N; } if (N == 2) { return 1; } int current = 0; int prev1 = 1; int prev2 = 1; for (int i = 3; i <= N; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return current; } }

Python 实现

class Solution: def fib(self, N: int) -> int: if (N <= 1): return N if (N == 2): return 1 current = 0 prev1 = 1 prev2 = 1 # Since range is exclusive and we want to include N, we need to put N+1. for i in range(3, N+1): current = prev1 + prev2 prev2 = prev1 prev1 = current return current