70. Climbing Stairs

LeetCode
,

Backtracking (time exceeded)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int count = 0;

    public int climbStairs(int n) {
        dfs(0, n);
        return count;
    }

    private void dfs(int current, int n) {
        if (current > n) return;
        if (current == n) {
            count++;
            return;
        }

        dfs(current + 1, n);
        dfs(current + 2, n);
    }
}

Remarks:

  1. TC: $O(2^n)$, SC: $O(n)$.

Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int first = 1, second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

Remarks:

  1. TC: $O(n)$, SC: $O(1)$.
  2. Ideas:
    This is exactly same as a fibonacci sequence.
    To achieve a position $n$ ($n\geq2$), we have to ways: (a) reach $n$ from $n-1$ by increasing 1; (b) reach $n$ from $n-2$ by increasing 2. Each method have only one choice, so all paths that can reach $n$, noted as $f(n)$, is the sum of $f(n-1)$ and $f(n-2)$, i.e.,
    $$
    f(n) = f(n-1) + f(n-2)
    $$
    This is the State Transition Equation (状態方程式) for this problem.
    Additioanlly, $f(1) = 1$, $f(2)=2$.