항해99, 5주차 계단 오르기

Today I learned
2022/02/09

회고록

2/09

항해 99, 알고리즘 4주차(항해 5주차)

교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)

다이나믹 프로그래밍

1. 이론

이론 정리 포스팅 글(내 벨로그)

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-5%EC%A3%BC%EC%B0%A8-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

2. 문제

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

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

3. MySol

• DP btm-up memoization

n = 4

d = [0]*(n+1)

d[0]=1
d[1]=1

for i in range(2,n+1):
    d[i] = d[i-2] + d[i-1]

print(f'{d[n]}')

4. 배운 점

• DP
• 바텀업 방식으로 메모이제이션 구현

5. 총평

DP 알고리즘 익히기