70. 爬楼梯 – Blog of Aspirer

题目链接：https://leetcode.cn/problems/climbing-stairs/

这道题不会做，看官方题解才明白。

class Solution {
public:
/* 记忆递归法
    unordered_map<int, int> mymap;
    int climbStairs(int n) {
        if (n < 1) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;

        if (mymap.count(n) > 0) {
            return mymap[n];
        }
        int total = climbStairs(n - 1) + climbStairs(n - 2);
        mymap[n] = total;
        return total;
    }
*/

    // 动态规划法
    int climbStairs(int n) {
        int a = 1, b = 2;
        int total = 0;
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return a;
        } else if (n == 2) {
            return b;
        }

        for (int i = 3; i <= n; i++) {
            total = a + b;
            a = b;
            b = total;
        }
        return total;
    }
};

class Solution {

public:

/* 记忆递归法

unordered_map<int, int> mymap;

int climbStairs(int n) {

if (n < 1) return 0;

if (n == 1) return 1;

if (n == 2) return 2;

if (mymap.count(n) > 0) {

return mymap[n];

}

int total = climbStairs(n - 1) + climbStairs(n - 2);

mymap[n] = total;

return total;

}

// 动态规划法

int climbStairs(int n) {

int a = 1, b = 2;

int total = 0;

if (n <= 0) {

return 0;

} else if (n == 1) {

return a;

} else if (n == 2) {

return b;

}

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

total = a + b;

a = b;

b = total;

}

return total;

}

};