lordly   2년 전

knuth's optimization을 이용해서 문제를 풀며 점화식을 이용한 풀이에서

c[i][j]란 dp[i][j]가 최소가 되게 하는 k(i < k < j)값을 저장하는 배열이라 정의할 때,

c[i][j-1]  <= c[i][j] <= c[i+1][j]이 성립하고 이를 코드로

for (int i = 1; i <= n; ++i) { c[i-1][i] = i; }

와 같이 나타내는 것을 알았는데 잘 이해가 되질 않습니다.

왜 위의 점화식을 기준으로 c[i-1][i] 에 i를 대입하는 것인가요?

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