[#2579] 계단 오르기

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    vector<int> vec(300, 0);
    vector<int> cache(300, 0);
 
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    
    cache[0] = vec[0];
    cache[1] = vec[0] + vec[1];
    cache[2] = max(vec[0] + vec[2], vec[1] + vec[2]);
    
    for (int i = 3; i < n; i++) {
        //전계단 밟는 경우 전전계단은 밟으면 안됨. 전전전계단 밟아야함
        //전계단 안밟는 경우
        //이 중 최대값
        cache[i] = max(cache[i - 3] + vec[i - 1] + vec[i], cache[i - 2] + vec[i]);
    }
 
    cout << cache[n - 1];
 
    return 0;
}

 

n>=4 이상일때 cache[n] = max(cache[n-3] + vec[n-1] + vec[n], cache[n-2] + vec[n])

계단이 1개일 때, 2개일 때, 3개일 때 ... 손으로 해보면서 점화식을 찾기