-
Notifications
You must be signed in to change notification settings - Fork 0
/
climbing_stairs_bigint.ts
33 lines (33 loc) · 1006 Bytes
/
climbing_stairs_bigint.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
export function climbing_stairs_bigint(num: bigint): bigint {
if (num === 0n) return 1n;
if (num < 1) {
throw Error("must grater than one");
}
const bigInt = BigInt;
const cached = cacheClimbStairs.get(num);
if (typeof cached !== "undefined") {
return cached;
}
num = bigInt(num);
for (let e = 1n; e <= num; e++) {
if (cacheClimbStairs.has(e)) {
continue;
} else {
const r = cacheClimbStairs.get(e) ||
bigInt(
cacheClimbStairs.get(e - 1n) ||
climbing_stairs_bigint(e - 1n),
) +
bigInt(
cacheClimbStairs.get(e - 2n) ||
climbing_stairs_bigint(e - 2n),
);
cacheClimbStairs.set(e, r);
}
}
return climbing_stairs_bigint(num);
}
const cacheClimbStairs = new Map<bigint, bigint>([
[1n, 1n],
[2n, 2n],
]);