[일반] 보통 문제가 dp인지 아닌지 어캐 구별함?

[익명(106.101)]

작은 문제로 쪼개질수 있는가로 난 보는데 이걸로는 잘 안보여서 ㅠㅠㅠㅠ

[익명(skuld88)]

상태 안 되돌아가면서 부분문제로 쪼개야 하는데 이게 재활용 되면 dp

[익명(106.101)]

상태 안돌아가야 한다는데 무슨 얘기임??

[익명(180.70)]

상태가 사이클을 이루고 있으면 안 돼 특정 칸의 최적값을 구할 때 보통 점화식 쓰잖아 dp[X] = dp[X - 1] + dp[X - 2] 대략 이런식으로 이렇게 해서 한 번 구해진 dp[X] 는 다시 갱신되어서는 안 됨, 한 번 점화식 넣어서 최적값 구했으면 그걸로 끝

[익명(1.250)]

냅색문제 일차원 배열로 푸는건 값 갱신하던데

[익명(1.250)]

https://chanhuiseok.github.io/posts/improve-6/
이거 일차원 배열로 푸는건 엄밀히 따지면 dp가 아닌거임?

[익명(223.62)]

저거는 dp식은 2차원인데 계산 과정에서 배열을 1차원으로 줄일 수 있는거임. d[i][j]=max(d[i-1][j], d[i-1][j-w[i]]+v[i]) 식은 그대로인데 j를 큰 쪽부터 보면 한번의 i루프에서 d[i][j]를 갱신했으면 그 j값은 d[i][0]~d[i][j-1]을 계산하는 도중에 쓰일 일이 없잖아? 그래서 그냥 i를 없애고 덮어씌워도

[익명(223.62)]

잘 동작하는 거임

[익명(106.101)]

아 ㅇㅇㅇ 고마워 ㅎㅎㅎ

[익명(1.250)]

오 역시 개고수의 통찰력은 다르군 하나 배워간다

[익명(175.223)]

나도 그거 못해서 그리디로 접근하고 개같이 폭사함ㅋㅋ