# Climbing Stairs

• class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
returnLst = []

``````    if(n == 1):
return 1
returnLst.append(1)
returnLst.append(2)
for i in range(3, n+1):
returnLst.append(returnLst[i - 2] + returnLst[i - 3])

return returnLst[n-1]``````

• You may also calculate the possible combinations and sum them up...

But Fibonacci is MUCH better (for this particular case)

Here is my code...

public class Solution {
public int ClimbStairs(int n) {
double combinations = 0;

``````    int doubles = n / 2;
for (int i = 0; i < (doubles + 1); i++)
{
combinations += Combination((n - i), (n - (i * 2)));
}

return (int)combinations;
}

public double Combination(int n, int p)
{
if (n.Equals(p))
return 1;

return PartFactorial(n, (n - p)) / PartFactorial((n - p), -1);
}

public double PartFactorial(int n, int take = -1)
{
double result = 1;

if (n.Equals(0))
return result;

if (take.Equals(-1))
{
take = n;
}

for(int i = 0; i < take;  i++)
{
result *= (n - i);
}

return result;
}
``````

}

• Might no easy to understand the fibonacci formula. Even I learned linear algebra method to solve fibonacci way, however I still can not understand the explain above of fibonacci solution.

• I don't know why I was wrong.
When I check the number. I just find if n=6,it could write as 4 groups {all 1, one 2 step, two 2 step, three 2 step}.
And the first group just provides 1 way,
The second group provides 51,
The third group provides 4
3/2
The fourth group provides 1.

It seems as C(n-i)(i) for each group.
So I use the below code.

class Solution {
public:
int climbStairs(int n) {
int kind = n/2;
int result = 1;
for (int i=1;i<=kind;i++)
{
result +=Combination(n-i,i);
}
return result;
}
int Combination(int n, int m)
{
int ans = 1;
for(int i=n; i>=(n-m+1); --i)
ans *= i;
while(m)
ans /= m--;
return ans;
}
};

• Who the duck asks these retarded questions? put the name of company so that we can avoid those companies.

• //I don't know why i was wrong eg:n =3 ans=C(3)(0)+C(2)(1)=1+2=3
//eg:n=4 ans=C(4)(0)+C(3)(1)+C(2)(2)=1+3+1=5
class Solution {
public int climbStairs(int n) {
int two =n/2;
int ans =0;
for(int k = 0;k<=two; k++) {
ans +=countC(n-k, k);
}
return ans;
}
private int countC(int m,int k) {
int molecule = 1;
int denominator = 1;

``````	for(int i = m;i>m-k;i--) {
molecule *= i;
}
for(int i = k;i>0;i--) {
denominator *= i;
}
return molecule/denominator;
}
``````

}

• I know why i was wrong! n=24,molecule *= i Beyond the scope of the integer

• transition matrix：
Xn=Xn-1+Xn-2
Xn-1=Xn-1
So transition matri Q =[ 1, 1 ]
1, 0
Q=Q^(n-1)*Q1 Q 1=[ 1, 1 ]
1, 0
A=Q^n =[ 1, 1 ]n we can calculate P，and A=P-1 B P and A[0][0] is Fn
0] 1, 0

• ## Easy Python Solution: Fibonacci

T-C: O(N), S-C: O(1)

``````def climbStairs(self, n):
# Fibonacci Approach
a = b = 1
for _ in range(n - 1):
temp = a + b
a = b
b = temp
return b
``````

• Correnction on Approach #2 Recursion with memorization

int[] memo = new int[n+1]; should be int[] memo = new int[n+2];

for the reason that i + 2 is called in the recursion.

• Please, correct the title of Approach #2. It is memoization, not memorization.
Thank you.

• B is (sqrt5 - 1)/2sqrt5, not (1-sqrt5)/2sqrt5.

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