[알고리즘문제] 릿코드 Climbing Stairs

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

Climbing Stairs - LeetCode

주어진 숫자 n 만큼 계단을 올라가야 된다.

계단은 1칸 또는 2칸 올라갈 수 있다.

나올 수 있는 모든 경우의 수를 구하여 반환 한다.

문제에는 규칙이 있다.

// 0 => 0
// 1 => 1
// 2 => 2
// 3 => 3
// 4 => 5
// 5 => 8
// 6 => 13
// 7 => 21
// 8 => 34
// 9 => 55

n의 경우에 대한 숫자 = (n-1에 나온 경우의 수) + (n-2에 나온 경우의 수) 이렇게 계산하면 풀린다.

 

typescript 코드

function climbStairs(n: number): number {
    if(n === 0) return 0;
    if(n === 1) return 1;
    if(n === 2) return 2;
    let tmp1 : number = 1;
    let tmp2 : number = 2;
    let answer : number = 0;
    for(let i : number = 2; i < n; i++){
        answer = tmp1 + tmp2;
        tmp1 = tmp2;
        tmp2 = answer;
    }
    return answer;
};

rust 코드

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        if n == 0 { return 0;}
        else if n == 1 { return 1; }
        else if n == 2 { return 2; }

        let mut tmp1 = 1;
        let mut tmp2 = 2;
        let mut answer = 0;

        for i in 2..n{
            answer = tmp1 + tmp2;
            tmp1 = tmp2;
            tmp2 = answer;
        }
        answer
    }
}

time complexity : O(n)

space complexity : O(1)