good ref
https://daimhada.tistory.com/181
SOLUtion from https://velog.io/@highcho/Algorithm-baekjoon-2579
Initial
I first thought of reversing the list because the question said the last stair must be taken. Not sure why my idea does not work.
I reversed the list and initialised the dp so that the first step MUST be taken.
n=int(input())
lst=[]
for _ in range(n):
lst.append(int(input()))
lst.reverse()
dp=[0 for _ in range(n+1)]
dp[0]=lst[0]
dp[1]= lst[0]+lst[1]
dp[2]= max(dp[1],lst[0]+lst[2])
for i in range(3, n):
dp[i]= max(dp[i-2]+lst[i],dp[i-3]+lst[i-1]+lst[i],dp[i-1])
print(dp[n-1])Not sure why it is wrong but is it because this oox case is not allowed? Because the first and last step MUST be taken so at position n, oox is not allowed? TBC
solution
import sys
h = int(sys.stdin.readline())
stair = [0] + [int(sys.stdin.readline()) for i in range(1, h + 1)]
if h < 2: # 주어진 계단의 수가 2보다 작을 경우 위와 같이 stair 배열을 할당할 경우 예외처리를 해주지 않으면 index error가 발생한다
print(stair[h])
else:
dp = [0] * (h + 1)
dp[1] = stair[1]
dp[2] = dp[1] + stair[2]
for i in range(3, h + 1):
dp[i] = max(dp[i - 2], dp[i - 3] + stair[i - 1]) + stair[i]
print(dp[h])complexity
probably o(n) time and space
