dlxogh376   1달 전

코드를 이와 같이 재귀로 했는데요..

dp가 메모이제이션을 통한 재귀 호출 반복을 막는거라는 건 알겠습니다.

여기서 예를 들면 recursive의 반복을 막아주기 위해 캐시 배열을 선언해서 저장해 놓는거라고 알고있는데요.. 문제는 그걸 어떻게 여기서 변형해야 할지를 모르겠습니다. ㅠㅠ

설명좀 해주실분 안계신가요?

zlzmsrhak   1달 전

메모이제이션은 함수가 호출될 때의 인자가 같은 경우 같은 값을 리턴하는 함수에 대해서,

계산한 값을 저장하여 같은 인자에 대해서는 두 번 이상 계산을 하지 않도록 하는 방법입니다.

이것을 위해서는 재귀함수를 그냥 바꿀 수는 없고, 함수 정의와 점화식을 신경써주어야 합니다.


먼저 함수의 정의를 

int recursive(int curNum,int wha) : curNum번째 계단에서 시작하고, 연속 상태가 wha일 때 얻을 수 있는 최대 이득

으로 수정하는 것으로 시작하는 것으로 시작해야 합니다.


재귀 코드를 참고하면, (틀릴 수도 있습니다)

wha = 0인 경우 recursive(curNum + 1, 1) + stair[curNum + 1], recursive(curNum + 2, 0) + stair[curNum + 2]중 큰 값,

wha =1인 경우 recursive(curNum + 2, 0) + stair[curNum + 2]

wha = 2인 경우 recursive(curNum + 1, 0) + stair[curNum + 1],

        recursive(curNum + 2, 0) + stair[curNum + 2] 중 큰 값으로 구할 수 있겠습니다.


메모이제이션 기본 틀인 캐시 배열도 추가해야 합니다.

dlxogh376   1달 전

감사합니다..
그래서 좀 고쳐봤는데 여기서 어떤 문제가 있는지 피드백좀 부탁드려도 될까요?

댓글을 작성하려면 로그인해야 합니다.