백준 2228 구간나누기

문제

풀이

1. 부분 문제 정하기

   cache[i][j] 를 1~i까지 구간이 j개일 때 최댓값으로 정하자. 그러면 
   cache[i][j] 는 arr[i]를 포함하는 경우와 arr[i]를 포함하지 않는 경우로 나눌수 있다. 
   cache[i][j] = max(cache[i][j], cache[i-1][j], max{0..k}(cache[k-2][j-1] + psum[i]-psum[k-1]))

2. 최적부분구조임을 보이기

   ?? 어케보여?