[dp] 백준 2579 계단오르기

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

마지막을 생각하면 편합니다.

마지막을 밟고, 그 전 칸을 밟은 경우 : dp[n] = dp[n-3] + arr[n] + arr[n-1]

마지막을 밟고, 그 전 전 칸을 밟은 경우: dp[n] = dp[n-2]+arr[n]

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int n,tmp;
    int dp[301] = {0};
    int arr[301];
    
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    
    dp[1] = arr[1];
    dp[2] = arr[1]+arr[2];
    dp[3] = max(arr[1]+arr[3], arr[2]+arr[3]);
    
    for(int i = 4; i <= n; i++)
        dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i]+arr[i-1]);
    
    cout << dp[n];
}