dlftls38   4년 전

이런 문제를 풀 때마다 헷갈리는게 BFS로 풀리는 건 알겠는데

탑 다운DP로는 왜 풀 수 없는 건가요??

해결됐습니다

-> dp는 그래프의 형태가 DAG가 아니면 일반적으로는 쓸 수 없습니다. 사이클에 대한 대처를 하지 못하기 때문입니다.

snrnsidy   4년 전

100 6

1 33

1 50

50 70

70 80

80 90

90 34

3 34

답:4

출력:6

이거 보시면 왜 안되시는지 아실거에요.

dlftls38   4년 전

좋은 예제네요 감사합니다.

재귀의 순서로인해 ret에 이미 최적의 값이 아닌 값이 할당되게되고 

ret에 값이 할당되어 있으면 return해버리니 더 최적의 값을 ret에 할당할 수 없게 돼 최적화가 안되는 거네요 감사합니다.

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