My solution using combinatorics (java)


  • 0
    C
    public class Solution {
        public int climbStairs(int n) {
            int result=0;
            
            for(int i=0;i<=n/2;i++){
                result+=select(n-i,i);
            }
            return result;
        }
    

    The select function calculate C(big,small). The tradtional way to calculate C(big,small) is big!/(small!*(big-small)!). At first, I coded as that as well. But I found that even using long, it is still out of the range. So I did some improvement on the calculation to avoid out of the long range:

    1. compare small and big-small, use the biger one to calculate
      C(big,small)

    2. Instead of calculating any factorial in the method, calculate
      big*(big-1)(big-2)....*(small+1) which equals big!/(big-small)!.
      But it is still out of range.... So more changes are needed.

    3. divide the small! when it can be divided without remainder. I use a
      int called record to divide the aa, and decrease record when the
      previous record has calculated.

      public int select(int big,int small){
          int another=big-small;
          if(another>small){
              return select(big,another);
          }
          else{
              long aa=1;
              int record=another;
              for(int i=big;i>small;i--){
                  aa*=i;
                  if(aa%record==0 && record>0){
                      aa=aa/record;
                      record--;
                  }
              }
      			  
              if(record>1){
                  while(record!=0){
                      aa=aa/record;
                      record--;
                  }
              }
              return (int) aa;
          }
      	   
      }
      

    }

    And my runtime is 168 ms. Yeah! I think this is the benefit to be patient with calculations. :)


  • 0
    T

    Time complexity is O(N^2). Very slow. Try to make it linear or better.


  • 0
    C

    To simplify the algorithm, I need to think through it again. I found actually the answer=select(n,0)+select(n-1,1)+select(n-2,2).....+ select(n-i,i) until i<=n/2. So I use an array to store each result from select(n-i,i). Array[i]=select(n-i,i).


    And I found that there are some relation between select(big,small) and slect(big-1,small+1).
    Select(big,small)=(big-small+2)(big-small+1)/small/(big+1) * slect(big-1,small+1).
    because array[small]=Select(big,small), so selectvalues[small]=selectvalues[small-1](big-small+2)/(big+1)(big-small+1)/small;


    now the updated code has O(n) complixity no matter in time or space.

    public class Solution {
    long[] selectvalues;
    public int climbStairs(int n) {
        selectvalues=new long[n/2+1];
        int result=0;
    
        for(int i=0;i<=n/2;i++){
            result+=select(n-i,i);
        }
        return result;
    }
    
    public int select(int big,int small){
        if(small==0){
            selectvalues[small]=1;
        }
        else if(small==big){
            selectvalues[small]=1;
        }
        else{
            selectvalues[small]=selectvalues[small-1]*(big-small+2)/(big+1)*(big-small+1)/small;
        }
        return (int)selectvalues[small];
    }
    

    }


Log in to reply
 

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