Categorygithub.com/szhou12/leetcode-goleetcode0509-Fibonacci-Number
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
0
Dependents
0

# README

509. Fibonacci Number

Solution idea

DP

  • 比较经典 & 简单的 DP 题
Definition:
    dp[i] = F(i) from 0 to i
Base Cases:
    dp[0] = 0
    dp[1] = 1
Recurrence:
    dp[i] = dp[i-2] + dp[i-1]
  • 也可以用 滚动数组 只保留前两个元素，来优化算法

Time complexity = $O(n)$