Description Link to heading

70.climbing-stairs

Solution Link to heading

Actually, it’s the same with 509.fibonacci-number. Let $dp_n$ be the number of ways to get to the top, then we have: $$dp_n = dp_{n - 1} + dp_{n - 2}$$ So we can write the traversal code of for loop.

Code Link to heading 

class Solution {
  public:
    int climbStairs(int n) {
        int cnt[2] = {1, 1};
        if (n == 1)
            return 1;
        for (int i = 1; i < n; i++) {
            int sum = cnt[0] + cnt[1];
            cnt[0] = cnt[1];
            cnt[1] = sum;
        }
        return cnt[1];
    }
};