Copy Books

Given an array A of integer with size of n( means n books and number of pages of each book) and k people to copy the book. You must distribute the continuous id books to one people to copy. (You can give book A[1],A[2] to one people, but you cannot give book A[1], A[3] to one people, because book A[1] and A[3] is not continuous.) Each person have can copy one page per minute. Return the number of smallest minutes need to copy all the books

Example

Given array A = [3,2,4], k = 2.

Return 5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

Solution:

1. DP - Check backpack DP?
2. State: f[i][j], i represents total i books and j means total j persons, so f[i][j] is the minimum minutes when i books are assigned to j people.
3. Function: f[i][j] = min(max(f[p][j-1], sum[p+1][i])), find the minimum value. Loop p from 0 to i. sum[p][q] represents the sum from index p to index q (included)
4. Initial: f[i][1] = sum[1][i]; pre-dispose the sum array
5. Answer: f[n][k]

    public int copyBooks(int[] pages, int k) {
        if (pages == null || pages.length == 0) {
            return 0;
        }

        int n = pages.length;
        if (n <= k) {
            int max = 0;
            for (int i = 0; i < n; ++i) {
                max = Math.max(max, pages[i]);
            }
            return max;
        }

        int[][] sum = new int[n+1][n+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = i; j <= n; ++j) {
                sum[i][j] = sum[i][j-1] + pages[j-1];
            }
        }

        int[][] f = new int[n+1][k+1];
        for (int i = 1; i <= n; ++i) {
            f[i][1] = sum[1][i];
        }

        for (int ik = 2; ik <= k; ++ik) {
            for (int i = ik; i <= n; ++i) {
                f[i][ik] = Integer.MAX_VALUE;
                for (int j = 0; j < i; j++) {
                    if (f[i][ik] == Integer.MAX_VALUE || f[i][ik] > Math.max(f[j][ik-1], sum[j+1][i])) {
                        f[i][ik] = Math.max(f[j][ik-1], sum[j+1][i]);
                    }
                }
            }    
        }

        return f[n][k];
    }