Copy Books

Question

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. )

Challenge Could you do this in O(n*k) time ?

Thoughts

区间动态规划

state dp[i][k] - 前i本书交给k个人copy的最小花费

function

`dp[i][k] = max(dp[j][k-1], cost[j+1][i]) (j < i)

init

dp[i][1] = cost[1][i]

result

dp[n][k]

注意点

-建matrix时多建一个，将0-based index转换为1开始 -当k大于n时，所需的时间即为最大的那本书的长度

Solution

class Solution:
    # @param pages: a list of integers
    # @param k: an integer
    # @return: an integer
    def copyBooks(self, pages, k):
        # write your code here
        if not pages:
            return 0

        if len(pages) <= k:
            return max(pages)

        dp = [[sys.maxint for i in range(k+1)] for j in range(len(pages) + 1)]
        w = [[0 for i in range(len(pages)+1)] for j in range(len(pages) + 1)]

        for i in range(1, len(pages)+1):
            for j in range(i+1, len(pages)+1):
                for z in range(i, j + 1):
                    w[i][j] += pages[z-1]

        #just one man
        for i in range(len(pages) + 1):
            dp[i][1] = w[1][i]

        for i in range(1, len(pages) + 1):
            for j in range(2, k+1):
                for x in range(1, i):
                    if dp[i][j] == sys.maxint or dp[i][j] > max(dp[x][j-1], w[x+1][i]):
                        dp[i][j] = max(dp[x][j-1], w[x+1][i])

        return dp[len(pages)][k]

    def cost(self, pages, start, end):
        result = 0
        for i in range(start, end+1):
            result += pages[i-1]

        return result