[LeetCode - C] 70. Climbing Stairs

Climbing Stairs - LeetCode

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

---

Solution 1

 

뭔가 형태가 피보나치로 나올 것 같아서

 

피보나치로 풀었는데 풀렸다.

 

int climbStairs(int n)
{
    int p;
    int s;
    int ret;
    
    if (n == 1)
        return (1);
    if (n == 2)
        return (2);
    p = 1;
    ret = 2;
    n--;
    while (--n)
    {
        s = ret;
        ret = p + ret;
        p = s;
    }
    return (ret);
}

---

Solution 2

 

이번에는 재귀로 풀었다.

 

시간 복잡도에서 걸리길래

 

rec 추가해서 진행했다.

static rec[45];

int climbStairs(int n)
{
    if (n <= 1)
        return (1);
    else if (rec[n - 1])
        return (rec[n - 1]);
    else
        rec[n - 1] = climbStairs(n - 1) + climbStairs(n - 2);
    return (rec[n - 1]);
}