[일반] 님들 dp 풀 때 optimal solution 다 정의하고품??

[익명(118.235)]

이 문제의 optimal solution은 뭐고

rec.urrence는 어떻게 짜여지고

solution table은 어떤 구조여야 할 것이며

이런 거 개념적으로 한번 정리하고 품?? a4에 하든 머릿속으로 하든

아님 걍 무대뽀로 일단 코드부터 침?

[백갤러 1(220.65)]

표본몇개던져보고 점화식세우고풀지

[익명(118.235)]

걍 점화식만 세워보고 바로 코드짜나

[익명(175.119)]

점화식만 세우면 댐. 애초에 코테에서는 DP 파악하기부터 어려워서 DP인게 검증되면 점화식만 세워도 다 통과함

[익명(175.119)]

이 문제가 DP인걸 파악했다 > 이미 해결책을 DP로 찾음 점화식을 세운다 > DP 테이블은 이미 감을 잡은 상태 점화식을 구현한다 > 점화식 탑다운으로 그대로 구현하면 재귀가 어떻게 짜여져야하는지 생각할 필요 자체가 없음

[익명(118.235)]

ㅇㅎㅇㅎ

[익명(59.6)]

보통 바텀업만 생각했는데 탑다운이 처음 풀때는 훨씬 할만함??

[익명(175.119)]

유형마다 다르긴한데, 대다수의 문제는 탑다운으로 푸는게 훨씬 쉬움. 바텀업으로 하면 어려운 문제가 많아서 내가 플래5 dp까지 문제 많이 풀어뒀는데, n x m 격자 관련 문제 아니면 거의 탑다운으로 풀었음

[백갤러 2(121.130)]

dp는 무조건 손으로 한번 하고 좀 어려운 dp같으면 최적화 한번 굴려야함 풀렸어도 히든 테케 걸리는거 개많음 dp가