다음과 같이 함수를 정의 해 봅시다.
d0(i) : i번째 계단을 밟은 경우, i번째 계단까지 최대 값
d1(i): i번째 계단을 밟지 않은 경우, i번째 계단까지 최대 값
이렇게 정의하면, 다음과 같이 다시 쓸 수 있습니다.
d0[i] = d1[i-1]
d1[i] = max(d0[i-2]+w[i-1]+w[i], d1[i-2]+w[i]) = max(d0[i-2]+w[i-1], d1[i-2]) + w[i] = max(d1[i-3]+w[i-1], d1[i-2]) + w[i]
where, w[i] : i번째 계단의 점수
이런 과정으로 위의 점화식이 나온 것 입니다.
jwl2327 4년 전
풀려고 하는데 너무 막혀서 다른 분 코드를 가지고 고쳐서 올렸더니 정답 맞았어요. 그런데 왜 이게 정답이 되는지 이해가 안되네요.
20번 줄에서 Math.max(maxValue[i - 3] + stair[i - 1], maxValue[i - 2]) 하는데 이게 어떻게 계단을 한게 또는두게 를 3번 이상 안넘어가게 계산 하는지 이해가 안됩니다.