70. Climbing Stairs
Tags:
Easy
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bạn leo cầu thang với n bậc. Mỗi lần bạn có thể bước 1 bậc hoặc 2 bậc. Hỏi có bao nhiêu cách khác nhau để lên đến đỉnh
Approach - DP
ways(n) = ways(n - 1) + ways(n -2)
Solution - Top down dp
1function climbStairs(n: number):number {
2 const memo: Map<number, number> = new Map();
3
4 function helper(n: number): number {
5 if(n <= 2) {
6 return n;
7 }
8
9 if(!memo.has(n)) {
10 memo.set(n, helper(n - 1), helper(n - 2));
11 }
12
13 return memo[n]
14
15 }
16
17 return helper(n);
18
19}Solution - Bottom up DP
1function climbStairs(n: number):number {
2 if(n <= 2) {
3 return n;
4 }
5
6 const dp: number[] = new Array(n + 1).fill(0);
7 dp[1] = 1
8 dp[2] = 2;
9
10 for(let i = 3; i <= n; i++) {
11 dp[i] = dp[i - 1] + dp[i - 2];
12 }
13
14 return dp[n]
15}Solution - Bottom up DP - optimize
1function climbStairs(n: number): number {
2 if (n <= 2) return n;
3 let first = 1;
4 let second = 2;
5 for (let i = 3; i <= n; i++) {
6 let third = first + second;
7 first = second;
8 second = third;
9 }
10 return second;
11};first, second để lưu số cách lên bậc i - 2 và i - 11function fibonacciOptimized(n: number): number {
2 if (n <= 1) return n;
3 let a = 0, b = 1;
4 for (let i = 2; i <= n; i++) {
5 const temp = a + b;
6 a = b;
7 b = temp;
8 }
9 return b;
10}