Java recursive solution and dp solution


  • 1
    R

    First I used recursion and found that it cost too much time. The recursive version is like this:

    public int climbStairs(int n) {
    		if (n <= 1)
    			return 1;
    		return climbStairs(n - 1) + climbStairs(n - 2);
    	}
    

    I found that recursion will count the previous results every time and cost too much time. Therefore, I was wondering if I can save the previous results in an array and then I came out this method:

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

    It is quite effective and I compare it with the recursive version. When n=44, the recursive one cost 4653ms to finish while this method cost less than 0ms.


  • 0
    W

    In dp solution ,why you set the length of array a (n + 1)?


  • 0
    R

    @wangchunhe In java, array starts from 0


  • 0
    S

    @Rhodey I think the purpose of this question is to prove the superiority of math over code. lol.


  • 0
    S

    @sinix said in Java recursive solution and dp solution:

    @Rhodey I think the purpose of this question is to prove the superiority of math over code. lol.

    Derivation of series is the best solution!


Log in to reply
 

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