j가 증가하는 순으로 루프를 돌리면 m[i] 가 여러번 더해지겠죠
예를들어 c[i]를 1이라고 하면
DP[2]를 계산할 때 DP[1]에서 값을 가져오면서 m[i]를 한 번 더하고
DP[3]을 계산할 때 DP[2]에서 값을 가져오면서 m[i]를 한 번 더하고
...
이런 식으로 m[i]가 반복적으로 더해지게 됩니다
j를 내림차순으로 돌리면 이런 문제가 없죠
그래서 보통 저런 식의 dp는 루프를 반대로 돌리거나
헷갈리면 그냥 2차원 배열 잡아서 순서대로 돌리기도 합니다
hazxz 7년 전 3
for(int j=size; j>=c[i]; j--) {
}
로 점화식을 돌리면 AC를 받습니다.
for(int j=c[i]; j<=size; j++) {
}
하지만 두번째처럼 아래에서 올라가는 형식으로 점화식을 돌리면 틀렸다고 나오네요
암만봐도 어차피 max값을 취하는 거고 구간이 똑같은데 왜 결과가 다르게 나오는지 모르겠습니다..
제가 무엇을 놓친걸까요