hazxz   7년 전

for(int j=size; j>=c[i]; j--) {

}

로 점화식을 돌리면 AC를 받습니다.

for(int j=c[i]; j<=size; j++) {
}

하지만 두번째처럼 아래에서 올라가는 형식으로 점화식을 돌리면 틀렸다고 나오네요


암만봐도 어차피 max값을 취하는 거고 구간이 똑같은데 왜 결과가 다르게 나오는지 모르겠습니다..

제가 무엇을 놓친걸까요


ntopia   7년 전

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년 전

ntopia 님 감사합니다.

그런식으로 차이가 생길지는 몰랐네요..아직 점화식 이해가 부족한가봅니다 감사합니다.

댓글을 작성하려면 로그인해야 합니다.