70. Climbing Stairs

/*
 * @lc app=leetcode id=70 lang=cpp
 *
 * [70] Climbing Stairs
 *
 * https://leetcode.com/problems/climbing-stairs/description/
 *
 * algorithms
 * Easy (53.10%)
 * Likes:    22131
 * Dislikes: 862
 * Total Accepted:    3.5M
 * Total Submissions: 6.7M
 * Testcase Example:  '2'
 *
 * You are climbing a staircase. It takes n steps to reach the top.
 *
 * Each time you can either climb 1 or 2 steps. In how many distinct ways can
 * you climb to the top?
 *
 *
 * Example 1:
 *
 *
 * Input: n = 2
 * Output: 2
 * Explanation: There are two ways to climb to the top.
 * 1. 1 step + 1 step
 * 2. 2 steps
 *
 *
 * Example 2:
 *
 *
 * Input: n = 3
 * Output: 3
 * Explanation: There are three ways to climb to the top.
 * 1. 1 step + 1 step + 1 step
 * 2. 1 step + 2 steps
 * 3. 2 steps + 1 step
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= n <= 45
 *
 *
 */

// @lc code=start
class Solution {
public:
    int climbStairs(int n)
    {
        if(n < 2) return n;

        vector<int> dp(n + 1);

        dp[0] = 1, dp[1] = 1;

        for(int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
// @lc code=end

• T: $O(N)$

• S: $O(N)$

• DP improved

class Solution {
public:
    int climbStairs(int n)
    {
        int first = 1, second = 1;
        for(int i = 2; i <= n; i++)
        {
            int temp = first;
            first = first + second;
            second = temp;
        }
        return first;
    }
};

• T: $O(N)$
• S: $O(1)$