[Dynamic Programming] 계단 오르기

https://www.acmicpc.net/problem/2579

Description

계단의 수와 각 계단의 점수가 주어지며, 밟는 계단의 점수를 얻는다.

1.  한 번에 한 계단 또는 두 계단만 이동 가능
2. 연속된 세 계단을 모두 밟아서는 안 됨. 시작점은 포함하지 않음.
3. 마지막 계단은 꼭 밟아야

얻을 수 있는 점수의 최댓값?

Idea

n번째 계단으로 오를 수 있는 경우는 n-1번째 계단에서 한 계단 오르거나, n-2번째 계단에서 두 계단 오르는 경우 뿐이다. n번째 계단으로 한 계단 올라와서 얻는 최고 점수들을 dp1에. n번째 계단으로 두 계단 올라와서 얻는 최고 점수들을 dp2에. 구하는 답은 max(dp1[n], dp2[n]). Base case를 생각해 보면, dp1[0] = dp2[0] = 0 dp1[1] = scores[1], dp2[1] = 0 (첫 번째 계단으로 두 계단 올라올 수 없음) dp1[2] = scores[1] + scores[2], dp2[2] = scores[2]  

Code

def maxScoreFinalOneStep(n, dp1, dp2, scores):
    ''' computes max score when the one gets to nth step with final one-up-step '''
    #
    #base cases
    #

    #0th step : score 0
    if n == 0 and dp1[n] == -1:
        dp1[n] = 0
        return dp1[n]
    #1st step : score[1]
    elif n == 1 and dp1[n] == -1:
        dp1[n] = scores[n]
        return dp1[n]
    #2nd step : score[1] + score[2]
    elif n == 2 and dp1[n] == -1:
        dp1[n] = scores[n-1] + scores[n]
        return dp1[n]
    
    #dp2[n-1] not set, compute it
    if dp2[n-1] == -1:
        dp2[n-1] = maxScoreFinalTwoStep(n-1, dp1, dp2, scores)
    
    #finally fill in dp1[n] and return it
    dp1[n] = dp2[n-1] + scores[n]
    return dp1[n]

def maxScoreFinalTwoStep(n, dp1, dp2, scores):
    ''' computes max score when the one gets to nth step with final two-up-step '''
    #
    #base cases
    #

    #0th step : score 0
    if n == 0 and dp2[n] == -1:
        dp2[n] = 0
        return dp2[n]
    #1st step : score 0. we cannot reach 1st step with final two-up-step
    elif n == 1 and dp2[n] == -1:
        dp2[n] = 0
        return dp2[n]
    #2nd step : scores[2]
    elif n == 2 and dp2[n] == -1:
        dp2[n] = scores[n]
        return dp2[n]

    #if dp1[n-2] or dp2[n-2] not set, fill them in
    if dp1[n-2] == -1:
        maxScoreFinalOneStep(n-2, dp1, dp2, scores)
    if dp2[n-2] == -1:
        maxScoreFinalTwoStep(n-2, dp1, dp2, scores)

    #finally fill in dp2[n] and return it
    dp2[n] = max(dp1[n-2], dp2[n-2]) + scores[n]
    return dp2[n]

if __name__ == '__main__':
    #total number of steps
    N = int(input())
    #scores of each steps. 0th step has 0 score!
    scores = [0] + [int(input()) for _ in range(N)]

    #dp1[n] : max score when reaches nth step with final one-up-step
    dp1 = [-1] * (N+1)
    #dp2[n] : max score when reaches nth step with final two-up-step
    dp2 = [-1] * (N+1)

    #answer
    print(max(maxScoreFinalOneStep(N, dp1, dp2, scores), maxScoreFinalTwoStep(N, dp1, dp2, scores)))