力扣链接：509.斐波那契数

难度：⭐

解题关键词：动态规划、斐波那契

解题思路：当前数 = 前两个数的和。

function fib(n: number): number {
  if (n === 0) return 0;

  let p = 0,
    q = 0,
    r = 1;
  for (let i = 2; i <= n; i++) {
    p = q;
    q = r;
    r = p + q;
  }
  return r;
}