描述

给定 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
解释: 三个人各复印一本书.

思路：

令表示前k个人复印n本书籍最少用的时间。同样从终止条件开始考虑，可知如果最后一个人抄写范围从第本书到第本书，则，并且是一个范围，必须考虑所有情况的最小值，即。具体实现如下。

class Solution {
public:
    /**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */
    int copyBooks(vector<int> &pages, int k) {
        // write your code here
        int n=pages.size();
        if(!n)
        {
            return 0;
        }
        if(k>n)
        {
            k=n;
        }
        vector<vector<int>> dp(k+1,vector<int>(n+1,INT_MAX));
        for(int i=0;i<=k;i++)
        {
            dp[i][0]=0;
        }
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int sum=0;
                for(int m=j;m>=0;m--)
                {
                    dp[i][j]=min(dp[i][j],max(dp[i-1][m],sum));
                    if(m>0)
                    {
                       sum+=pages[m-1]; 
                    }
                }
            }
        }
        return dp[k][n];
    }
};