Copy Books

Question

Given n books and the ith book has A[i] pages. You are given k people to copy the n books.

n books list in a row and each person can claim a continous range of the n books. For example one copier can copy the books from ith to jth continously, but he can not copy the 1st book, 2nd book and 4th book (without 3rd book).

They start copying books at the same time and they all cost 1 minute to copy 1 page of a book. What's the best strategy to assign books so that the slowest copier can finish at earliest time?

Solution

這題實在不是很好想，屬於區間型的動態規劃。區間型動態規畫的定義是把一個數組劃分成幾個區塊，然後要求怎麼切比較好。這題滿直觀的就是把 array 切成 k 個區塊，然後給 k 個人負責這樣

狀態表達式：dp[n][k] 表示 n 本書給 k 個人去抄寫，所得到的最少抄寫時間

遇到這種劃分型的動態規劃，在想轉移方程時，一定要想著『上一步』狀態。那上一步狀態無非是 dp[x][k - 1]，也就是 k - 1 個人分 x 本書。因此，轉移方程就會變成：

dp[n][k] = Math.max(dp[x][k - 1], 從 x + 1 到 n 本書的所有時間)

這邊的 x 代表可能是 n - 2 本書給 k - 1 個人分；又或者是 n - 5 本書給 k - 1 個人分。那該怎麼求得這個 dp[x][k - 1] 呢？也就是 for 循環去求出所有可能性，並且取最小值。

    if (pages == null || pages.length == 0) {
            return 0;
        }

        int n = pages.length;
        int[][] dp = new int[n + 1][k + 1]; //dp[n][k] 表示 n 本書用 k 個人所花的時間

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

        for (int j = 2; j <= k; j++) {
            for (int i = 1; i <= n; i++) {
                dp[i][j] = Integer.MAX_VALUE;
                int pivot = i - 1;
                while (pivot >= 0) {
                    int one = dp[i][1] - dp[pivot][1];
                    int others = dp[pivot][j - 1];
                    int minute = Math.max(one, others);
                    dp[i][j] = Math.min(dp[i][j], minute);
                    pivot--;
                }
            }
        }
        return dp[n][k];