안녕하세요.

우선 재귀로 dp를 구현하기위해서는 메모이제이션이 필수인데,

작성자님의 코드에서는 메모이제이션이 적용되지않고 있습니다. 메모이제이션에 대해 간략히 설명해드리자면, 피보나치 함수 f(4)를 예로들때,

f(4)은 f(3)와 f(2)를 호출하고, 호출된 f(3)는 f(2)와 f(1)을 호출하고, f(2)는 f(1)과 f(0)를 호출하고. 2의 값을 가지게됩니다. 그렇다면 f(3)은 2+1,즉 3의 값을가지게 됩니다.

그런데 f(4)에서 호출한 f(3)과 f(2)에서, f(3)은 계산을 완료했으니, f(2)를 계산할 차롄데, f(2)는 f(1)과 f(0)을 호출하지 않아도 그 값을 알수있습니다.

바로 위에서 f(3)을 계산할때, f(2)의값을 알았기때문이죠. 이처럼, 메모이제이션은 함수f(n)의 값을 알고있으면,f(n)에서 재귀를 또 돌리지 않는다는 의미입니다.

이처럼 dp를 재귀로 푸는것은 cache배열을 -1로 초기화하여 참조자를 사용해 푸는방법이 가장 정형화되어 있습니다.

이 내용을 다 설명하기엔, 너무 내용이 방대하기도 하고, 제가 설명이 부족할 수 있습니다.

그러니 dp재귀 구글링하시면 잘 정리가되어있는 글이 많으니 참고하시길 바랍니다.

@newdeal 

아 저가 뭘 잘못했는지 이해가 갔습니다.

감사합니다.