13398번 - 연속합 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]을 제거한 상태에서의 최대 연속합인 경우를 세지 않는가?는 겁니다
궁금증이 해결되었네요 dp[n][1]의 첫번째 경우는 dp[n][0]의 값을 이용하기 때문에 숫자가 제거되지 않는 경우가 맞군요
댓글을 작성하려면 로그인해야 합니다.
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]을 제거한 상태에서의 최대 연속합인 경우를 세지 않는가?는 겁니다