This problem looks busy at first, but the accepted solution is built around one steady invariant. For 70. Climbing Stairs, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming.
The notes already sitting in the source point us in the right direction:
- DP
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are climbStairs, steps, multiply, pow.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n)O(n). Single loop upto nn is required to calculate n^{th}n
- Space: O(1)O(1). Constant space is used.
Guide
C++ Solution
Your submission
The accepted solution
01//DP
02/**
03Complexity Analysis
04Time complexity : O(n)O(n). Single loop upto nn.
05Space complexity : O(n)O(n). dpdp array of size nn is used.
06**/
07//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Climbing Stairs.
08//Memory Usage: 8.5 MB, less than 55.79% of C++ online submissions for Climbing Stairs.
09class Solution {
10public:
11 int climbStairs(int n) {
12 if(n == 1) return 1;
13 vector<int> steps(n);
14
15 // cout << "size: " << steps.size() << endl;
16
17 steps[0] = 1; //1+0 step from the top
18 steps[1] = 2; //1+1 step from the top
19
20 for(int i = 2; i < n; i++){
21 steps[i] = steps[i-1] + steps[i-2];
22 // cout << steps[i] << endl;
23 }
24
25 return steps[n-1];
26 }
27};
28
29//Fibonacci number
30/**
31Complexity Analysis
32Time complexity : O(n)O(n). Single loop upto nn is required to calculate n^{th}n
33th fibonacci number.
34Space complexity : O(1)O(1). Constant space is used.
35**/
36
37//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Climbing Stairs.
38//Memory Usage: 8.2 MB, less than 97.68% of C++ online submissions for Climbing Stairs.
39class Solution {
40public:
41 int climbStairs(int n) {
42 if(n <= 2) return n;
43
44 int last = 1, last2 = 2;
45
46 for(int i = 2; i < n; i++){
47 int tmp = last2;
48 last2 = last + last2;
49 last = tmp;
50 // cout << last << " " << last2 << endl;
51 }
52 // cout << endl;
53
54 return last2;
55 }
56};
57
58//DP and Fibonacci, no edge case
59//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Climbing Stairs.
60//Memory Usage: 5.9 MB, less than 100.00% of C++ online submissions for Climbing Stairs.
61class Solution {
62public:
63 int climbStairs(int n) {
64 // vector<int> dp(n+1, 0);
65
66 //0: padding, used when dp[2] = dp[1] + dp[0]
67 // dp[0] = dp[1] = 1;
68 int last1 = 1, last2 = 1;
69
70 for(int i = 2; i <= n; i++){
71 // dp[i] = dp[i-1] + dp[i-2];
72 last2 += last1;
73 swap(last1, last2);
74 }
75
76 // return dp[n];
77 return last1;
78 }
79};
80
81/**
82Approach 5: Binets Method
83**/
84
85/**
86Complexity Analysis
87Time complexity : O(\log n)O(logn). Traversing on \log nlogn bits.
88Space complexity : O(1)O(1). Constant space is used.
89**/
90
91/**
92class Solution {
93public:
94 void multiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b, vector<vector<long long>>& c){
95 for(int i = 0; i < 2; i++){
96 for(int j = 0; j < 2; j++){
97 c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
98 }
99 }
100 }
101
102 void pow(vector<vector<long long>>& a, int n, vector<vector<long long>>& r){
103 vector<vector<long long>> tmp = {{0,0}, {0,0}};
104 while(n > 0){
105 //if(n%2 == 1){
106 if((n&1) == 1){
107 multiply(r, a, tmp);
108 r = tmp;
109 }
110 //n/=2;
111 n >>= 1;
112 multiply(a, a, tmp);
113 a = tmp;
114 }
115 }
116
117 int climbStairs(int n) {
118 vector<vector<long long>> q = {{1,1}, {1,0}};
119 vector<vector<long long>> r = {{1,0}, {0,1}};
120 pow(q, n, r);
121 return r[0][0];
122 }
123};
124**/
125
126/**
127Approach 6: Fibonacci Formula
128**/
129
130/**
131Complexity Analysis
132
133Time complexity : O(\log n)O(logn). powpow method takes \log nlogn time.
134
135Space complexity : O(1)O(1). Constant space is used.
136**/
137
138/**
139class Solution {
140public:
141 int climbStairs(int n) {
142 double sqrt5 = sqrt(5);
143 double fibn = pow((1+sqrt5)/2, n+1) - pow((1-sqrt5)/2, n+1);
144 return (int)(fibn/sqrt5);
145 }
146};
147**/Cost