Why my combination solution is wrong?


  • 1
    C

    In this question, I want to use combination.
    For example, n=5, we can select :

    0 two-step from 5 steps; 
    1 two-step from 4 steps; 
    2 two-steps from 3 steps;
    

    then

    f(5)=C(0,5)+C(1,4)+C(2,3)=1+4+3=8.

    So

    f(n)=C(0,n)+C(1,n-1)+C(2,n-2)+...+C(m,n-m) (m < n-m)

    But the answer is wrong, I don't understand.

    Anybody help me?

    Thank you!

    What is weirder is if n<=26, the answer is right.

       int climbStairs(int n){
            int m=0;
            int ways=0;
            while (m<=n) {
                ways+=Com(n, m);
                n--;
                m++;
            }
            return ways;
        }
        int Com(int n,int m){
            if (m>n/2) {
                m=n-m;
            }
            
            int res=1;
            for (int i=0; i<m; i++) {
                res*=n;
                n--;
            }
            for (int i=m; i>0; i--) {
                res/=i;
            }
            return res;
        }

  • 0
    L

    Your answer is same with me.

    But the result may overflows.
    In here

        int res=1;
        for (int i=0; i<m; i++) {
            res*=n; //here
    

    INT_MAX is 2147483647.
    See My answer


Log in to reply
 

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