범위를 정하고 돌아야 하는 DP

DP[i][j] = min(DP[i][j], DP[i][k], DP[k+1][j]+@) 라는 식을 감싸는 for문을 생각해보자

 

일단 이렇게 보면 굉장히 헷갈린다. 변수명을 바꿔보자

 

for(int range = 1; range <= N; range++){

    for(int startPos=1; startPos<=N; startPos++){

        int endPos = startPos+range;

        for(int k= startPos; k < endPos; k++){

            DP[startPos][endPos] = min(DP[startPos][endPos], DP[startPos][k] + DP[k+1][endPos] + @

        }

   }

}

 

DP[start][end] = min(DP[start][end], DP[startPos][k] + DP[k+1][endPos] + @)

 

이에 대한 코드는 다음과 같다

 

#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;
int prefix[505], file[505], DP[505][505];
int main() {
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    int T;
    scanf("%d", &T);
    while (T--) {
        int N; cin >> N;
        for (int i = 1; i <= N; i++) {
            scanf("%d", &file[i]);
            prefix[i] = prefix[i - 1] + file[i];
        }
        for (int range = 1; range <= N; range++) {
            // 검색 범위
            for (int startPos = 1; startPos <= N; startPos++) {
                int endPos = startPos + range;
                if (endPos <= N) {
                    DP[startPos][endPos] = INF;
                    for (int k = startPos; k < endPos; k++) {
                        // (startPos, endPos) 사이에 있는 어떤 K든 다 끌고와봄
                        int fellow = prefix[endPos] - prefix[startPos - 1];
                        DP[startPos][endPos] = min(
                            DP[startPos][endPos],
                            DP[startPos][k] + DP[k + 1][endPos] + fellow
                        );
                    }
                }
            }

        }
        printf("%d\n", DP[1][N]);
    }
    return 0;

}