509. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function fib(n: number): number {
const dpTable: Record<number, number> = {};
dpTable[0] = 0;
dpTable[1] = 1;
const handleFib = (target: number) => {
if (dpTable[target] !== undefined) {
return dpTable[target];
}
const result = handleFib(target - 1) + handleFib(target - 2);
dpTable[target] = result;
return result;
};
return handleFib(n);
};
|
