Dynamic Programming(동적 계획법)의 개발절차
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기
1) n-2번째 계단 -> n번째 계단
2) n-1번째 계단 -> n번째 계단
단, 이 경우에는 연속된 3개의 계단을 밟을 수 없다는 조건에 의해 무조건 'n-3 -> n-1 -> n' 의 순서를 가지게 된다.
재귀 관계식
stairs[n] = n번째 계단의 점수
S[n] : n번째 계단까지 오를 때 얻을 수 있는 점수의 최댓값
S[n] = maximum(S[n-2] + stairs[n], S[n-3] + stairs[n-1] + stairs[n]) (n >= 3)
int calMax() {
for (int i = 3;i <= n;i++) {
S[i] = maximum(S[i - 2] + stairs[i], S[i - 3] + stairs[i - 1] + stairs[i]);
}
return S[n];
}
S[0] = 0;
S[1] = stairs[1];
S[2] = stairs[1] + stairs[2];
int res = calMax();