다이나믹 프로그래밍 문제 (마지막을 선택해야 하고 연속해서 뽑지 못하는 수열에서 최댓값 찾기)

마지막을 선택해야 하고 연속해서 뽑지 못하는 수열에서 최댓값 찾기

무조건 마지막 계단 n을 밟았다고 쳤을 때 나올 수 있는 방식은

마지막 계단 전에 밟은 계단이  n-1 일 때, n-2 일 때 둘로 나뉜다

  

dp[i] : i번째 계단을 밟았을때 까지의 최댓값

 

dp[i-2] + score[i]                  : i번째 계단을 밟기 전에 i-2계단을 밟았을 때

dp[i-3] + score[i] + score[i-1] : i번째 계단을 밟기 전에 i-1계단을 밟았을 때

 

3계단을 연속으로 밟을 수 없으므로 i-2번째 계단을 밟았을 땐 i번째 점수 score[i]에 dp[i-2]를 더해 주고,

i-1번째 계단을 밟았을 때는 score[i], score[i-1]에 dp[i-1-2]인 dp[i-3]을 더해 준다.