2022-07-23 @이영훈
전형적인 점화식을 찾는 Dynamic Programming 문제입니다.
이 문제에서 점화식을 찾을 때 3번 규칙 (마지막 도착 계단은 반드시 밟아야 한다) 따라야하기 때문에 점화식을 계단을 올라가는 앞에서 생각하는 방식보다는 도착지부터 생각하는 방식의 접근이 더 쉽습니다.
dp[n]은 n번째 계단에 올랐을 때 얻을 수 있는 점수의 최댓값입니다.
n 번째 계단에 올라오기 위해서는 두 가지 경우가 있습니다. n-1번째 계단으로 오는 경우와 n-2번째 계단으로 오는 경우입니다.
n-1번째 계단으로 오는 경우에는
dp[n] = dp[n-3] + stairs[n-1] + stairs[n] 입니다
n-2번째 계단으로 오는 경우에는
dp[n] = dp[n-2] + stairs[n] 입니다
이 중에서 더 큰 수가 dp[n]이 됩니다.
점화식에서 보면 첫번째 식에서 dp[n-3]이 있기 때문에 1, 2, 3층의 dp는 초기화해주어야 합니다.
생각의 방식은 다임하게님이 그림으로 잘 설명해주셨습니다. (글씨도 예쁘십니다)