리트코드-70. Climbing Stairs
문제
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?
풀이
주어진 조건에서 n 계단을 올리가기 위한 모든 방법을 계산하는 문제이다. 전형적인 DP 알고리즘 적용 문제로 인덱스 0, 1, 2을 제외하고서는 dp[n] =dp[n-1] + dp[n-2] 식을 적용하면 쉽게 풀린다.
- 인덱스 0, 1, 2를 제외하는 이유는 1계단, 2계단씩 오를 수 있기 때문에 위의 식에서 +1씩 방법이 늘어나기 때문이다.
- DP는 상향식과 하향식이 있는데 해당 문제는 하향식으로 푸는 것이 더 빠른 결과를 가져온다.
- 하지만 상향식이 더 간단하기 때문에, 상향식을 사용해 풀었다.
코드
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0, 1, 2]
for i in range(3,n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
Author And Source
이 문제에 관하여(리트코드-70. Climbing Stairs), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ddaynew365/리트코드-70.-Climbing-Stairs저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)