Leetcode 알고리즘 시리즈: 계단 오르기

여보세요! 다른 알고리즘 문제로 돌아왔습니다. 오늘의 문제는 Leetcode의 상위 인터뷰 질문 - 동적 프로그래밍 장 에서 쉽습니다 .

에서 계단을 등반 :

당신은 계단을 오르고 있습니다. n정상에 도달하려면 단계가 필요 합니다.

매번 오르 1거나 걸을 수 있습니다 2. 얼마나 많은 독특한 방법으로 정상에 오를 수 있습니까?

예:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
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

내가 취하기로 결정한 첫 번째 단계는 작업할 더 많은 예제를 가질 수 있도록 몇 가지 테스트 케이스를 더 만드는 것이었습니다. Leetcode에서는 다양한 사례를 테스트할 수 있고 예상 답변을 제공할 수 있기 때문에 쉽습니다. 이 옵션이 없으면 더 많은 사례를 작성해 보겠습니다.

input: 4
Distinct Ways:
1. 1 + 1 + 1 + 1
2. 1 + 1 + 2
3. 1 + 2 + 1
4. 2 + 1 + 1
5. 2 + 2
output --> 5
input: 5
Distinct Ways:
1. 1 + 1 + 1 + 1 + 1
2. 1 + 1 + 1 + 2
3. 1 + 1 + 2 + 1
4. 1 + 2 + 1 + 1
5. 2 + 1 + 1 + 1
6. 1 + 2 + 2
7. 2 + 1 + 2
8. 2 + 1 + 1

…

피보나치 수열이라고 하면 맞습니다!! 더 많은 사례를 가지고 놀면서 이 패턴을 인식했고 이전에 피보나치 수열을 수행했기 때문에 이 문제를 훨씬 쉽게 해결하는 데 도움이 되었습니다. 피보나치 수에 익숙하지 않다면 여기 에서 읽어보십시오 . 기본적으로 시퀀스에서 앞의 2개의 숫자의 합인 숫자입니다. 그래서 내가 한 일은 while 루프 내부에 피보나치 수열을 설정 하고 while 루프가 입력으로 제공된 횟수만큼 실행되도록 한 것입니다.

var climbStairs = function(n) {
    let total = 0
    let first = 0
    let second = 1
    let i = 0
    
    while (i < n) {
        total = first + second
        first = second
        second = total
        i++
    }
    
    return total
};

이 문제에 접근하는 다른 방법이 있거나 이 알고리즘을 해결하는 방법이 있다면 내 코드를 어떻게 개선할 수 있는지 확실히 듣고 싶습니다. 어려움을 겪고 있다면 이것이 해결하는 데 도움이되기를 바랍니다!

앞으로 더 많은 LeetCode 솔루션을 기대하십시오!

LeetCode 시리즈:

1. 중복 포함
2. 정렬된 배열 병합
3. 높이 검사기
4. 유효한 회문
5. 해피 넘버
6. 가장 긴 공통 접두사
7. 계단 오르기
8. 유효한 괄호
9. 파스칼의 삼각형
10. 최대 하위 배열

plainenglish.io 에서 더 많은 콘텐츠