SUSHI 반복적 동적계획법이 아닌 재귀적 동적계획법 문의

  • 임정민
    임정민

    안녕하세요
    해당 문제를 예제 코드 9.27처럼
    재귀적동적계획법으로 해결해보고자 하는데
    stack overflow가 납니다.
    for 문은 n번이라 20번으로 해결이 될것같은데
    어떤 부분을 수정해야 답을 도출해낼수 있을까요?

    아래와 같이 미리 100으로 전부 나눈 상태로 시작하였습니다.

    #define MAX_BUDGET 10000000
int cache[MAX_BUDGET + 1];

int sushi(int budget) {
    int &ret = cache[budget];
    if (ret != -1) return ret;
    ret = 0;
    for (int dish = 0; dish < n; ++dish) {
        if (budget < price[dish]) continue;
        ret = max(ret, sushi(budget - price[dish]) + pref[dish]);
    }
    return ret;
}

    8년 전
1개의 댓글이 있습니다.
  • usefulhyun
    usefulhyun

    stack overflow 가 일어나기 때문에 반복적동적게획법으로 밖에 풀 수 없는 것 아닌가요?


    8년 전 link

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