70:Climbing Stairs【DP】

/*题意：n阶的台阶，每次只能上一步或两步，共有多少种方法 */

/**
 *思路：简单递推，d[i] = d[i-1] + d[i-2]
 *      两种方法，一种空间复杂度O(1),另一种O(n)
 */


//O(1)
class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) return n;
        int d1 = 1, d2 = 2, d3;
        for(int i = 3; i <= n; i ++) {
            d3 = d1+d2;
            d1 = d2;
            d2 = d3;
        }
        return d3;
    }
};


/* O(n)
class Solution {
public:
    int climbStairs(int n) {
        int *d = new int[n+1];
        if(n <= 2) return n;
        d[1] = 1, d[2] = 2;
        for(int i = 3; i <= n; i++)
            d[i] = d[i-1] + d[i-2];
        return d[n];
    }
};
*/