C++ 70. Climbing Stairs(Leet Code)

Leet Code_70. Climbing Stairs

Dynamic Programming

 

https://leetcode.com/problems/climbing-stairs/

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

n번째 계단을 올라가는 최대 방법 수 구하기

​

방법

1. 1 또는 2 steps로만 올라갈 수 있다.

 

결과

n번째 계단을 올라가는 최대 방법 수 리턴

 

통과한 코드

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 3)
            return n;
        vector<int> arr;
        int step2 = 2;
        int step3 = 3;
        arr.push_back(step2);
        arr.push_back(step3);
        
        for(int i = 2 ; i < n-1 ; i++)
        {
            arr.push_back(arr[i-2] + arr[i-1]);
        }
        return arr.back();
    }
};

통과는 했지만 push를 쓰고 for문의 Index가 헷갈려서 3번 실패를 하였다.

 

다른 사람의 코드

class Solution {
public:
    int climbStairs(int n) {
        int prev_prev = 1;
        int prev = 1;
        int res = 1;
        for(int i = 2; i <= n; i++){
            res = prev_prev + prev;
            prev_prev = prev;
            prev = res;
        }
        return res;
    }
};

이전값들과 결과값을 for문에서 갱신하면서 처리하였다.

갱신 하는 방법이 떠오르지않아 vector를 쓴건데 머리가 굳었나 보다.