70. Climbing Stairs (1D-dp)

DP

time: O(n)

space: O(n)

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

use fib

time: O(n)

space: O(1)

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        int first = 1;
        int second = 2;
        
        for (int i = 3; i <= n ; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

why return second? because our goal is to use 2 varibles to rotate the value, so

first = second

second = third(outcome)

at last second is the result (third)

ex: n = 3

-> ans. = 3 = 2 + 1

first = second = 2

second = outcome = 3

-> ans = second = 3