Climbing Stairs Algorithm
The Climbing Stairs Algorithm is a classic dynamic programming problem that deals with finding the number of distinct ways to reach the top of a staircase with a certain number of steps, given that one can climb either one or two steps at a time. This problem is a popular interview question and is often used to teach the fundamentals of dynamic programming, as it has a simple structure that can be solved using various techniques such as recursion, memoization, or bottom-up approach.
The basic idea behind the algorithm is to find the relationship between the number of ways to reach the current step and the number of ways to reach the previous steps. The key observation is that the number of distinct ways to reach the nth step is the sum of distinct ways to reach the (n-1)th step and the (n-2)th step, as we can only get to the nth step from these two previous steps. Using this relationship, one can formulate a recursive solution to the problem, which can then be optimized using memoization or a bottom-up approach to avoid redundant calculations and reduce the time complexity. Overall, the Climbing Stairs Algorithm is an excellent example to demonstrate the power of dynamic programming in solving problems with overlapping subproblems and optimal substructure.
class Matrix {
public:
int x00, x01;
int x10, x11;
Matrix() {}
Matrix(int _x00, int _x01, int _x10, int _x11)
: x00(_x00), x01(_x01), x10(_x10), x11(_x11) {}
Matrix operator * (const Matrix& o) {
Matrix m;
m.x00 = x00 * o.x00 + x01 * o.x10;
m.x01 = x00 * o.x01 + x01 * o.x11;
m.x10 = x10 * o.x00 + x11 * o.x10;
m.x11 = x10 * o.x01 + x11 * o.x11;
return m;
}
};
class Solution {
public:
int climbStairs(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (n <= 1) return 1;
Matrix m(1, 1, 1, 0);
Matrix e(1, 0, 1, 0);
while (n) {
if (n & 1)
e = e * m;
m = m * m;
n /= 2;
}
return e.x10;
}
};
