백준 11066:파일 합치기

https://www.acmicpc.net/problem/11066

dp제는 너무 어려운거 같아요. 바텀업보다 탑다운이 코드짜기 편하고해서 점화식만 잘세우고, 탈출조건만 잘짜면 된다하는데 아직 많이 어렵네요.. 밑에 코드에서는 start~end 까지 보는데 for문을 돌면서 start ~ i의 최소합 i+1 ~ end까지의 최소합을 구해서 리턴하면 되네요. sum배열은 누적합을 저장해놓은 배열이예요.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int K;
vector<unsigned> file;
vector<unsigned> sum;
vector<vector<unsigned>> dp;
 
unsigned minSum(int start, int end) {//start~end 까지 최소합
    if (start >= end) return 0;
    else if (start + 1 == end) return file[start] + file[end];//인접할 경우
    if (dp[start][end] != -1) return dp[start][end];
 
    unsigned& result = dp[start][end] = numeric_limits<int>::max();
    for (size_t i = start; i <= end; i++) {
        result = min(result, minSum(start, i) + minSum(i + 1, end) + sum[end + 1] - sum[start]);
        //result에 (start ~ i의 최소합과 i+1 ~ end 까지의 최소합 + 누적합)의 최솟값을 넣어요
    }
    return result;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    size_t T; cin >> T;
    for (size_t tc = 0; tc < T; tc++) {
        cin >> K;
        dp.resize(K);
        for (size_t i = 0; i < K; i++) {
            dp[i].resize(K, -1);
            int size; cin >> size;
            file.push_back(size);
        }
        sum.push_back(0);
        for (size_t i = 0; i < K; i++) {
            sum.push_back(sum[i] + file[i]);
        }
        cout << minSum(0, K - 1) << endl;
        file.clear(); dp.clear(); sum.clear();
    }
    return 0;
}