70. Climbing Stairs

四刷 06/2022

Version #1 DP with Constant space

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Climbing Stairs.

Memory Usage: 40.9 MB, less than 41.40% of Java online submissions for Climbing Stairs.

class Solution {

    public int climbStairs(int n) {

        // standing at one stair i, the result is ways to reach stair i - 2 + ways to reach stair i - 1

        // count 1 = 1

        // coutn 2 = 2

        if (n <= 2) {

            return n;

        }

        int prevprev = 1;

        int prev = 2;

        for (int i = 3; i <= n; i++) {

            int curr = prev + prevprev;

            prevprev = prev;

            prev = curr;

        }

        return prev;

    }

}

三刷
100.00 % 
class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        int prevprev = 1; // 0
        int prev = 1; // 1
        for (int i = 2; i <= n; i++) {
            int curr = prevprev + prev;
            prevprev = prev;
            prev = curr;
        }
        return prev;
    }
}

一刷
public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return n;
        }
        int lastlast = 1;
        int last = 1;
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            temp = lastlast + last;
            lastlast = last;
            last = temp;
        }
        return temp;
     
    }
}

二刷
这次纯自己写的
不如一刷的标答简洁
用了额外O(n) 的space complexity
其实可以直接通过2个 variable rolling的方式实现

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        if (n <= 1) return 1;
        int[] ways = new int[n + 1];
        ways[0] = 1;
        ways[1] = 1;
        for (int i = 2; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }
        return ways[n];
    }
}