# Python solution is Time Out

• Someone can help why this got Time Out:

``````class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
f = []
f.append(1)
f.append(1)
for i in range(2, n + 1):
f.append(f[i - 1] + f[i - 2])

return f[n]
``````

Same algorithm but a bit different in implementation is AC:

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

return f[n]``````

• Time Out means the server is very busy, you may need to re-submit it.

Time Limit Exceed indicates your algorithm is not efficient enough.

Sorry for making this misunderstanding.

• ``````class Solution:
def climbStairs(self, n):
if n<=2:
return n
pre1=2
pre2=1
for i in range(3,n+1):
current=pre1+pre2
pre2=pre1
pre1=current
return current``````

• This post is deleted!

• ``````    o(log n) solution

int multiply( int mat1[2][2], int mat2[2][2] )
{
int i, j, k, l;
i = mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0];
j = mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1];
k = mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0];
l = mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1];

mat1[0][0] = i;
mat1[0][1] = j;
mat1[1][0] = k;
mat1[1][1] = l;
return 0;
}

int power( int F[2][2], int n )
{
if( n <= 1 )
return 0;
power( F, n/2 );
multiply( F, F );
if( n % 2 == 1 )
{
int M[2][2] = { {1, 1},{1, 0} };
multiply( F, M );
}
return 0;
}

int noOfWays( int n )
{
if( n <= 1 )
return 0;
int F[2][2] = { {1, 1},{1, 0} };
power( F, n );
return F[0][0];
}

class Solution {
public:
int climbStairs(int n) {
if( n == 0 || n ==1 )
return n;
else
return noOfWays(n);

}
};``````

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