18232번 - 텔레포트 정거장
이런 문제를 풀 때마다 헷갈리는게 BFS로 풀리는 건 알겠는데
탑 다운DP로는 왜 풀 수 없는 건가요??
해결됐습니다
-> dp는 그래프의 형태가 DAG가 아니면 일반적으로는 쓸 수 없습니다. 사이클에 대한 대처를 하지 못하기 때문입니다.
100 6
1 33
1 50
50 70
70 80
80 90
90 34
3 34
답:4
출력:6
이거 보시면 왜 안되시는지 아실거에요.
좋은 예제네요 감사합니다.
재귀의 순서로인해 ret에 이미 최적의 값이 아닌 값이 할당되게되고
ret에 값이 할당되어 있으면 return해버리니 더 최적의 값을 ret에 할당할 수 없게 돼 최적화가 안되는 거네요 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
dlftls38 4년 전 1
이런 문제를 풀 때마다 헷갈리는게 BFS로 풀리는 건 알겠는데
탑 다운DP로는 왜 풀 수 없는 건가요??
해결됐습니다
-> dp는 그래프의 형태가 DAG가 아니면 일반적으로는 쓸 수 없습니다. 사이클에 대한 대처를 하지 못하기 때문입니다.