안녕하세요.

계단오르기 문제 질문하려고 합니다.

알고리즘은 i번째 계단을 밟았을 때의 최대값 안밟았을 때의 최대값 2개를 저장해서 풀었습니다.

  dp[i][0] = i번째 계단을 밟지 않았을 때의 최대값

  dp[i][1] = i번째 계단을 밟았을 때의 최대값

계단을 밟지 않았을 때는 i-1 번째의 값중 최대값을 저장하고 계단을 밟을 경우에는 연속된 3개의 계단을 밟지 않도록 조건을 걸었습니다. i-2 번째 계단을 밟았으면 i - 1 계단을 밟지 않고 i -1 번째 계단을 밟으면 i - 2 계단을 밟지 않도록 하였습니다. 점화식은 다음과 같습니다.

  dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
  dp[i][1] = Math.max(dp[i-2][0] + stair[i-1], dp[i-2][1]) + stair[i];

첫번 째 계단과 두번 째 계단은 따로 초기화를 하였습니다.

이와 같은 풀이로 포도주시식 (2156문제) 믄제를 해결해서 이상없이 풀 수 있을 것이라 생각했는데

틀렸다고 결과가 나오네요.

기존에 있던 질문글을 검색해서 반례 테스트를 해봤는데 아직 틀린 것을 못찾았습니다.

혹시 풀이에 문제가 있거나 반례를 알고 계시면 조언 해주시길 부탁드리겠습니다.

감사합니다.