划分型动态规划——书籍复制

分手后的思念是犯贱 2022-10-27 06:30 143阅读 0赞

#  #

给定 n 本书, 第 i 本书的页数为 pages\[i\]. 现在有 k 个人来复印这些书籍, 而每个人只能复印编号连续的一段的书, 比如一个人可以复印 pages\[0\], pages\[1\], pages\[2\], 但是不可以只复印 pages\[0\], pages\[2\], pages\[3\] 而不复印 pages\[1\].

所有人复印的速度是一样的, 复印一页需要花费一分钟, 并且所有人同时开始复印. 怎样分配这 k 个人的任务, 使得这 n 本书能够被尽快复印完?

返回完成复印任务最少需要的分钟数.

样例 1:

输入: pages = [3, 2, 4], k = 2
    输出: 5
    解释: 第一个人复印前两本书, 耗时 5 分钟. 第二个人复印第三本书, 耗时 4 分钟.
    样例 2:
    
    输入: pages = [3, 2, 4], k = 3
    输出: 4
    解释: 三个人各复印一本书.
    挑战
    时间复杂度 O(nk)
    
    注意事项
    书籍页数总和小于等于2147483647

### 1、题目分析 ###

如果一个抄写员抄写到第i本到第j本书，则需要时间A\[i\]+A\[i+1\] + … + A\[j\]。最后完成时间取决于耗时最长的那个抄写员。因此需要找到一种分段方式，分成不超过K段，使得所有段的数字之和的最大值最小。

### 2、确定状态 ###

最后一步：最优策略中最后一个抄写员抄写的部分。假设最后一个抄写员抄写第j本到第N-1本书。则需要时间A\[j\]+……+A\[n-1\]。需要知道前面K-1一个人最少需要多少时间抄写完前j本书(第0～j-1本书)

因此我们可以假设f\[k\]\[i\]为前K个抄写员最少需要多少时间抄完前i本书

### 3、转移方程 ###

f\[k\]\[i\]为前K个抄写员最少需要多少时间抄完前i本书

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 4、初始条件和边界情况 ###

初始条件：0个抄写员只能抄0本书，所以f\[0\]\[0\]=0，f\[0\]\[1\]=f\[0\]\[2\]=……

K个抄写员需要0时间抄0本书，f\[k\]\[0\]=0(k>0)

### 5、计算顺序 ###

逐行计算，时间复杂度O(N\*N\*K)，空间复杂度O(N\*K)，如果K>N，可以赋值N ->K

### 6、代码实现 ###

class Solution:
        """ @param pages: an array of integers @param k: An integer @return: an integer """
        def copyBooks(self, pages, k):
            # write your code here
            if len(pages) == 0:
                return 0
            dp = [[float('inf')] * (len(pages) + 1) for i in range(k + 1)]
            dp[0][0] = 0
            for i in range(1, k + 1):
                dp[i][0] = 0
                for j in range(1, len(pages) + 1):
                    sum = 0
                    for l in range(j, -1, -1):
                        dp[i][j] = min(dp[i][j], max(dp[i - 1][l], sum))
    
                        if l > 0:
                            sum += pages[l - 1]
            return dp[k][len(pages)]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/7f7fd375e4254c1fa297cca85f28d8f2.png