jiwoo2211   2년 전

dp[i][0] : 1부터 i번까지 숫자를 제거하지않은 최대 연속합

dp[i][1] : 1부터 i번까지 숫자를 1개 제거한 최대 연속합

여기서 dp[i][1]의 점화식을

dp[i][1] = max(dp[i-1][0], dp[i-1][1]+A[i])로 작성했습니다

첫번째 경우는 A[i]를 제거한 경우고

두번째 경우는 1~i-1번까지에서 1개의 숫자가 제거되어 A[i]를 추가한 경우인데

궁금한 점은 dp를 작성해가면서 1개의 숫자만 제거해야 하는데 여러개의 숫자를 제거하는 경우를 세지 않나하는 의문이듭니다

만약에 dp[2][1]이 A[2]를 제거한 상태에서의 최대 연속합이고

dp[3][1]도 A[3]을 제거한 상태에서의 최대 연속합인 경우를 세지 않는가?는 겁니다

jiwoo2211   2년 전

궁금증이 해결되었네요 dp[n][1]의 첫번째 경우는 dp[n][0]의 값을 이용하기 때문에 숫자가 제거되지 않는 경우가 맞군요

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