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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**
 * Calculate the number of distinct ways to climb to the top of a staircase.
 * Dynamic Programming approach.
 *
 * @param {number} n - Number of steps in the staircase
 * @return {number} - Number of distinct ways to climb to the top
 */
function climbStairs(n) {
  // Base cases
  if (n === 1) {
    return 1;
  }
 
  // Initialize DP array
  const dp = new Array(n + 1);
  dp[1] = 1;  // There is 1 way to climb 1 step
  dp[2] = 2;  // There are 2 ways to climb 2 steps: 1+1 or 2
 
  // Fill the DP array
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
 
  return dp[n];
}
 
/**
 * Calculate the number of distinct ways to climb to the top of a staircase.
 * Space-Optimized Dynamic Programming approach.
 *
 * @param {number} n - Number of steps in the staircase
 * @return {number} - Number of distinct ways to climb to the top
 */
function climbStairsOptimized(n) {
  // Base case
  if (n === 1) {
    return 1;
  }
 
  // Initialize variables for the first two steps
  let prev2 = 1;  // Ways to climb 1 step
  let prev1 = 2;  // Ways to climb 2 steps
 
  // Iterate from step 3 to n
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
 
  return prev1;
}
 
/**
 * Calculate the number of distinct ways to climb to the top of a staircase.
 * Matrix Exponentiation approach.
 *
 * @param {number} n - Number of steps in the staircase
 * @return {number} - Number of distinct ways to climb to the top
 */
function climbStairsMatrix(n) {
  // Base case
  if (n === 1) {
    return 1;
  }
 
  // Define the base matrix
  const base = [
    [1, 1],
    [1, 0]
  ];
 
  // Compute base^(n-1)
  const result = matrixPower(base, n - 1);
 
  // The answer is in the top-left element of the resulting matrix
  // For n = 2, we want F(2) = 2, which is the top-left element of base^1
  // For n = 3, we want F(3) = 3, which is the top-left element of base^2
  // And so on...
  return result[0][0] + result[0][1];
}
 
/**
 * Compute the power of a 2x2 matrix using binary exponentiation.
 *
 * @param {number[][]} matrix - The base matrix
 * @param {number} n - The exponent
 * @return {number[][]} - The resulting matrix
 */
function matrixPower(matrix, n) {
  // Base case: matrix^0 = identity matrix
  if (n === 0) {
    return [
      [1, 0],
      [0, 1]
    ];
  }
 
  // If n is odd, compute matrix^(n-1) * matrix
  if (n % 2 === 1) {
    const result = matrixPower(matrix, n - 1);
    return multiplyMatrices(result, matrix);
  }
 
  // If n is even, compute (matrix^(n/2))^2
  const half = matrixPower(matrix, Math.floor(n / 2));
  return multiplyMatrices(half, half);
}
 
/**
 * Multiply two 2x2 matrices.
 *
 * @param {number[][]} a - First matrix
 * @param {number[][]} b - Second matrix
 * @return {number[][]} - The product of the two matrices
 */
function multiplyMatrices(a, b) {
  return [
    [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
    [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
  ];
}
 
// Test cases
console.log(climbStairs(2));  // 2
console.log(climbStairs(3));  // 3
console.log(climbStairs(4));  // 5
console.log(climbStairs(5));  // 8
 
console.log(climbStairsOptimized(2));  // 2
console.log(climbStairsOptimized(3));  // 3
console.log(climbStairsOptimized(4));  // 5
console.log(climbStairsOptimized(5));  // 8
 
console.log(climbStairsMatrix(2));  // 2
console.log(climbStairsMatrix(3));  // 3
console.log(climbStairsMatrix(4));  // 5
console.log(climbStairsMatrix(5));  // 8