Accepted c dp solution with an extra recursive solution


  • 0
    R

    basic idea is about think reversely. when I need to reach step n,I may come from n-1 or n-2.so we got a formula, f(n) = f(n-1) + f(n-2). which is the Fibonacci Sequence.

    int climbStairs(int n) {
    	if(n<=2) return n;
    
    	int p1=2;
    	int p2=1;
    	int s =3;
    	while( s<=n ){
    		int t = p1;
    		p1 += p2;
    		p2 = t;
    		++s;
    	}
    
    	return p1;
    }
    

    the way of dp is about current result is base on the result of last 2 steps.
    but we use recursion to solve Fibonacci Sequence like problems more commonly.

    int climbStairsR(int n) {
    	if(n<=2) return n;
    	
    	int res = climbStairsR(n-1) +
    		climbStairsR(n-2);
    	return res;
    }

Log in to reply
 

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