algoshipda   1년 전

저런식의 반복적 동적계획법을 재귀적 동적계획법으로 구현할 수 있나요?

단순하게 생각해서 두번째 코드처럼 구현했더니 동전 순서가 관계 있게 되면서 중복되는 경우가 같이 계산되는 것 같습니다.

(첫번째 코드에서 for문의 순서를 바꾼것과 같은)

재귀적 구현은 아무리 생각해도 dp배열을 2차원으로 잡고 dp[n][k] = n번째 종류 까지만 사용하고 k원을 만들어내는 경우의 수 , 로 구하는 방법 말고는 떠오르지 않습니다. 혹시나 가능한가요?

amugeona   1년 전

중복을 제거하는 방법은, 반복문의 방향을 바꾸면 해결되지요. :)

algoshipda   1년 전

반복문의 방향을 바꾸면 재귀적으로 구현이 가능하단 말인가요? 잘 이해가 안되는데..

amugeona   1년 전

@s201124481

제가 질문을 잘못 이해했네요. 대충 보고 중복을 어떻게 뺄지를 여쭈어본줄 알았습니다.

재귀적으로 dp를 꼭 써야하는 상황인가요? 중복되는 원소를 뺄 수 있는 원리는 "갱신전 상태"와 "갱신후 상태"를 분리할 수 있을 때 가능합니다. 재귀적인 구조에서도 이 구조를 유지할 수 있으면 가능합니다.

algoshipda   1년 전

죄송한데.. 갱신전 상태와 갱신후 상태를 분리하는 예를 들어주실 수 있나요?

amugeona   1년 전

1차원 DP 확장법이 대표적이지요. i를 갱신할 때 i보다 작은 인덱스들은 갱신전이고, i보다 큰 인덱스들은 갱신후로 표시가 되지요.

그렇기 때문에 뒤에서 앞으로 탐색하면 갱신전 인덱스를 참조해서 갱신 후를 만들 수 있기 때문에 1차원이 가능한 것이지요.

algoshipda   1년 전

죄송한데 잘 모르겠습니다. ㅜㅜ 동전의 경우 예로 들어주실 수 있으신가요

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