반복적 DP로 풀수 있는 모든 문제는 재귀적 DP로도 해결할 수 있나요?

  • nosqeil24
    nosqeil24

    안녕하세요,

    저는 DP를 종만북으로 처음 접하였습니다.

    종만북에서 소개하는 DP방식이 재귀적 DP였기 때문에

    저는 재귀적DP로 대부분의 DP문제를 해결해왔습니다.

    그런데 슬라이딩 윈도우 등 반복적 DP에서만 가능한 테크닉이 있기에

    그런 테크닉을 쓰기위해서재귀적 DP로 푼 문제라도 다시 반복적 DP로도 풀어보려고 하고 있는데요,

    지금까지 공부를 해오면서 반복적DP로 코드까지 짜서 정답 판정을 받은 코드 중에서

    재귀적DP코드로 도저히 어떻게 짜야할지 감이 안오는 문제가 딱 2개가 있습니다.

    첫번째 문제는 https://www.acmicpc.net/problem/2293 입 니다.
    대부분의 정답코드는 1차원 다이나믹으로 반복적으로 해결했는데, 재귀적 DP로 어떻게 해야할지 모르겠습니다...

    두번째 문제는https://www.acmicpc.net/problem/10982 입니다.
    이 두 문제를 재귀적 dp로 어떻게 해결할 수 있나요?

    타 사이트 문제라서 죄송합니다 종만북에서 배운 방식이라 여기에 질문을 올려야 될것같아서 질문드립니다. . 대부분 반복적DP를 쓰셔서
    종만북에서 배운 재귀적 DP로도 풀 수 있는지 궁금합니다!

    감사합니다


    4년 전
1개의 댓글이 있습니다.
  • fleo0917
    fleo0917

    첫 번째 문제는 똑같은 문제가 알고스팟에도 있네요.
    COINS
    참고가 될런진 모르겠지만 제 답안 한 번 봐보세요.

    https://algospot.com/judge/submission/detail/311316
    일반적인 dp입니다. 느린 건 탐색공간이 2차원이라서 그렇구요. 저는 반대로 여기서 상태공간을 1차원으로 줄일 방법을 몰라 한참 헤멨던 기억이 나네요. 똑같은 코드가 파이썬으로는 시간초과가 났거든요.


    4년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.