파일 합치기 1에서 썼던 식을 최적화 시킬 수 있다.

dp[l][r] = min(dp[l][r], dp[l][j]+dp[j+1][r]+ls[r]-ls[l-1]);

누적합(ls[r]-ls[l-1])을 이용한 부분을 C[i][j]로 가정하고 보면

C[i][j]는 단조성, 사각부등식을 만족하므로 Knuth Optimization으로 풀 수 있다. 코드는 갓 jhnah917님의 코드를 참고하였다.

#include <bits/stdc++.h>
#define MEM 5005
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000
using namespace std;
typedef long long lld;
const int INF = 1e9+7;
int t;
int n;
int ls[MEM], dp[MEM][MEM], k[MEM][MEM];
main(){
    sanic;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i=1; i<=n; i++){
            cin >> ls[i];
            ls[i] += ls[i-1];
        }
        for(int i=1; i<=n; i++) 
            dp[i-1][i] = 0, k[i-1][i] = i;
        for(int i=2; i<=n; i++){
            for(int l=0; l<=n-i; l++){
                int r = l+i;
                dp[l][r] = INF;
                for(int j=k[l][r-1]; j<=k[l+1][r]; j++){
                    int now = dp[l][j] + dp[j][r] + ls[r] - ls[l];
                    if(dp[l][r] > now){
                        dp[l][r] = now;
                        k[l][r] = j;
                    }
                }
            }
        }
        cout << dp[0][n] << '\n';
    }
}

---