이번 문제의 점화식은 다음과 같이 세웠습니다.

문제에 나와있는 Test Case는 잘 구해지는데 어느 부분이 틀렸는지 잘 모르겠습니다. 반례 혹은 점화식이 잘못된 것을 지적해주시면 감사하겠습니다.

n=1,2 일때까지는 구해줍니다.

n>3 부터는 아래 그림과 같은 점화식으로 문제를 해결하려고 합니다.

간단히 그림을 설명드리자면, n번째 dp[i][j]는 dp[0][j], dp[1][j]로 나누어 구합니다.(파란색, 빨간색)

1) dp[0][j] -> j번째 열의 0행 스티커를 떼어낼 때, 가장 높은 점수로 떼어내는 방법

2) dp[1][j]-> j번째 열의 1행 스티커를 떼어낼 때, 가장 높은 점수로 떼어내는 방법입니다.

최종 결과는 1과 2의 최댓값으로 구합니다.

좀 더 세부적으로 설명드리면,

1)은 아래 그림의 1,2번 케이스로 나누어지므로 두 경우의 max값

2)는 아래 그림의 3,4번 케이스로 나누어지므로 두 경우의 max값으로 구합니다.

그 다음 최종 결과는 1과 2의 최댓값으로 구합니다.

반례 혹은 점화식의 잘못된 부분을 알려주시면 감사하겠습니다.