A simple combinatorial solution without DP :


  • 0
    R

    class Solution {
    public:

    long long int C(int n , int k ) {
      long long int res = 1;
      for(int i=1;i<=k;i++){
        res*=n;
        res/=i;
        n--;
      }
      return res;
    }
    long long int climbStairs(int n) {
        int up  = 0;
        long long int  ans  = 0;
        int twos = 0;
        int  all = 0;
        while(up<n){
          up+=2;
          if(up>n) break;
          twos = up/2;
          all = (n - up) + twos;
          ans+=C(all,twos);
        }
        return ans+1;
    }
    

    };


Log in to reply
 

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