top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int climbStairs(int n) {
        /*
        ways(n-1, n) = 1                            -- one step to n
        ways(n-2, n) = 1 + 1                        -- 1x two-step + 2x one-step
        ways(  k, n) = ways(k-1, n) + ways(k-2, n)
        */
        if (n == 1) return 1;
        if (n == 2) return 2;

        int ways_n_1 = 1; // ways(n-1, n)
        int ways_n_2 = 2; // ways(n-2, n)
        for (int i = n-3; i >= 0; --i) {
            const int ways_n_3 = ways_n_1 + ways_n_2;
            // Update
            ways_n_1 = ways_n_2;
            ways_n_2 = ways_n_3;
        }
        return ways_n_2;
    }
};