My solution considering odd and even


  • 7
    I
    public int climbStairs(int n){
    	if(n <= 0) return 0;
    	int [] stairs = {1,2};
    	for(int i = 2;i < n;i++){
    		stairs[i%2] = stairs[0]+stairs[1];
    	}
    	
    	return n % 2 == 0 ? stairs[1]:stairs[0];
    }
    

    considing f(n) = f(n-1)+f(n-2),that is:


    f(1) = 1


    f(2) = 2


    f(3) = f(2)+f(1)


    f(4) = f(3)+f(2)


    ...


    and the values before f(2) will never use again,so we can use an array with two elements to store the tmp values


  • 0
    B

    class Solution {

    public:

    int climbStairs(int n) {
    
        int sum[n];
    
        sum[0]=1;
    
        sum[1]=2;
    
        for(int i=2;i<n;i++){
    
            sum[i]=sum[i-1]+sum[i-2];
    
        }
    
        return sum[n-1];
    }
    

    };


  • 0
    C

    interesting solution! you use the lowest space.


Log in to reply
 

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