# My Solution, is there any better solution?

• ``````class Solution {
public:
int climbStairs(int n) {
if (aux[n] == 0) {
if (n == 0 || n == 1) aux[n] = 1;
else aux[n] = climbStairs(n-1) + climbStairs(n-2);
}
return aux[n];
}
private:
int aux[10000] = {0};
};``````

• Well one improvement is to make it constant memory. You dont need to store all 'n' solutions in aux.
You just need to remember the last two.

• I think you can change the recursively call. below is my python solution.

``````class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
if n < 2:
return 1
ways = [0] * (n+1)
ways[0] = 0
ways[1] = 1
ways[2] = 2
for i in range(3, n+1):
ways[i] = ways[i-2] + ways[i-1]
return ways[n]``````

• This post is deleted!

• I have other idea we can use constant memory like upload guy said. below is my new solution.after modify.

``````class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
if n == 1:
return 1
if n == 2:
return 2

first   = 1
second  = 2
for i in range(n-2):
first, second = second, second + first

return second``````

• ``````class Solution {
public:
int climbStairs(int n) {
if(n<=0)return 0;
if(n==1)return 1;
if(n==2)return 2;
int result[3];

result[0]=0;
result[1]=1;
result[2]=2;

for(int i=3;i<=n;i++){
result[i%3]=result[(i-1)%3]+result[(i-2)%3];
}
return result[n%3];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.