Java rolling array solution, easy to understand and only 4 lines


  • 4
    Y

    I initialized an array dp with size 3, this way we don't need boundary check. As for the dynamic programming part, it is essentially fibonacci. I mod 3 to the index each time to take use the size 3 array.

    public int climbStairs(int n) {
        int[] dp = {0, 1, 2};
        for(int i = 3; i <= n; i++) {
            dp[i%3] = dp[(i-1)%3] + dp[(i-2)%3];
        }
        return dp[n%3];
    }

  • 0
    R

    Your method is great and it actually save space! Brilliant!


  • 1
    W

    A better way is just use two, and when calculate a new stair just add them without caring about where they are in array.


  • 0
    H

    Could you explain why you use 0, 1, 2 as initial values, please? Thank you~


Log in to reply
 

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