You have to paint N boards of lenght {A0, A1, A2 ... AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continues sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

We define M[n, k] as the optimum cost of a partition arrangement with n total blocks from the first block and k patitions, so

                 n              n-1
M[n, k] = min { max { M[j, k-1], ∑ Ai } }                j=1             i=j

The base cases are:

M[1, k] = A0         n-1M[n, 1] = Σ Ai
         i=0

Therefore, the brute force solution is:

int sum(int A[], int from, int to){    int total = 0;    for (int i = from; i <= to; i++)        total += A[i];    return total;}int partition(int A[], int n, int k){    if (n <= 0 || k <= 0)        return -1;    if (n == 1)        return A[0];    if (k == 1)        return sum(A, 0, n-1);    int best = INT_MAX;    for (int j = 1; j <= n; j++)        best = min(best, max(partition(A, j, k-1), sum(A, j, n-1)));    return best;}

The Painter's Partition Problem Part I