풀이
- 마지막 계단을 밟은 경우
- 마지막 계단을 밟지 않은 경우
둘 중 좀 더 큰 것으로 선택해 배열 dp를 채우면 됨!
코드
python
# 1번 : dp[n] = dp[n-3] + arr[n-1] + arr[n]
# 2번 : dp[n] = dp[n-2] + arr[n]
dp[n] = max(dp[n-3] + arr[n-1] + arr[n], dp[n-2] + arr[n])