dp가
1. rec.urrence 정의
2. dp table 정의
3. bottom-up으로 dp table 채움
4. dp table에 있는 거 그대로 쓰든지 아니면 뭐 추가 계산을 하던가 해서 솔루션 구함
이렇게 되잖음
그리고 저 dp table을 채우는건 보통 반복문으로 채우고
근데 top down으로 dp를 푼다는건
dp table을 재귀로 채운다는거임??
그게 가능함??
물론 가능은 하겠다만
그렇게 풀면 그냥 d&c로 푸는거랑 다를 게 없지않음??
재귀로 풀면 중복연산을 하게돼서 시간복잡도가 보통 크니까 dp를 쓰는건데
dp를 재귀써서 풀고 거기에 dp table 채우는 연산까지 하면 더 손해아님??
진짜 몰라서 물어봄 코테린이임
재귀가 단순 재귀로 푸는게 아니라 당연히 바텀업처럼 메모이제이션하면서 재귀함수 돌리는거임 이건 걍 탑다운 코드 확인해보는게 좋음
재귀인데 바텀업처럼 한다는게 이해가안가네 직접 코드 봐야겠네
https://hellojaehoon.tistory.com/20
여기에
탑다운 바텀업 코드 둘 다 잘 적혀 있네
해당 댓글은 삭제되었습니다.
위상정렬같은거 풀다보면 이해할텐데 사실 뭐가 더 중요한건없음 근본은 바텀업인데 우리뇌는 탑다운인듯 - dc App
보통은 둘중 뭐로풀어요?
일단 탑다운을 기본으로 두는게 훠월낫습니다ㅋㅋ - dc App
탑다운 먼저 시도해보고 안풀릴거같으면 바텀업??
코딩 문제에 따라 탑다운 바텀업이 보통 정해져 있어서 선택지가 없어요
각각을 써야만 하는 상황이 존재함.
dp[i] = dp[i/2] + dp[i/5] 면 당연히 탑다운으로 짜야지.
예를 들어, 아래 링크는 점화식이 dp[i] = min(dp[i/2] + 1, dp[i/3] + 1, dp[i-1]) 인 문제임
https://www.acmicpc.net/problem/1463
근데 이 문제는 바텀업으로 짜도 되긴 하네
바텀업으로 짜는 게 더 합리적인거아님?? 왜냐면 table에서 i가 0 1 2... 일 때를 먼저 채우고 나면 i를 주루룩 구할 수 있는거잖아 자동으로
글고 반대로 바텀업으로 짜야 코드가 훨 깔끔해 지는 경우도 있음. 플루이드 워셜도 dp[j][k] = min(dp[j][i] + dp[i][k], dp[j][k]) 잖아. 이 경우는 탑다운으로 짜면, 바텀업에서는 3중 반복문으로 원큐에 될걸, 굳이 굳이 재귀로 짜는 참사가 일어남
ㄴㄴ 맞음 문제 잘못 가져옴
다시보니 내가 쓴 점화식이 잘못되었네 dp[i] = min(dp[i/2] + 1, dp[i/3] + 1, dp[i-1] + 1) 이 점화식대로면 탑다운으로 짜는게 훨씬 효율적임. 예를들어 n이 8이면 7,6,5 는 계산 안하고 생략가능함.
8일따 765 오타야??
3도 포함해야되네