斐波那契动态规划

动态规划

说明

保存前两个状态避免重复递归；时间 O(n)、空间 O(1)。

分析

朴素递归会重复计算大量相同子问题；滚动变量 a、b 分别保存前两个结果。每轮前进一项，既不需要递归栈也不需要完整数组。

图解推演

以 F(0)=0、F(1)=1 为边界，滚动状态从 (F(0),F(1)) 前移到 (F(1),F(2))。更新必须同时使用旧 a、b；先覆盖 a 再计算 b 会把同一个新值加两次。F(8)=21，使用固定宽度整数时仍要限定 n。

查看图表代码

适用前提与边界

Go 的 int 会在数值过大时溢出，超大 n 应改用 math/big。

示例输入与调用

fmt.Println(Fibonacci(8))

运行输出

21

完整 Go 示例

package main

import "fmt"

func Fibonacci(n int) int {
	a, b := 0, 1
	for range n {
		a, b = b, a+b
	}
	return a
}

func main() {
	fmt.Println(Fibonacci(8))
}