Climbing Stairs


  • 0

    Click here to see the full article post


  • 0
    A

    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]

  • 0

    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;
    }
    

    }


  • 0
    Y

    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.


  • 0
    I

    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;
    }
    };


  • 0
    H

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


  • 0
    W

    //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;
    }
    

    }


  • 0
    W

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


  • 0
    W

    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


  • 0
    T

    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
    

  • 0
    P

    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.


Log in to reply
 

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