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.

DP O(k*n^2)时间复杂度 solution

空间复杂度O(n*k) dp[ki][ni]保存的是抄ni+1本书，ki+1个人需要的最小时间

class Solution {
public:
    /**
     * @param pages: a vector of integers
     * @param k: an integer
     * @return: an integer
     */
    int copyBooks(vector<int> &pages, int k) {
        // write your code here
        if(k<1)return 0;

        if(pages.size()<=k)
        {
            int maxVal=pages[0];
            for(int i=1;i<pages.size();i++)
            maxVal=max(maxVal,pages[i]);

            return maxVal;
        }

        int n=pages.size();


        vector<vector<int>> dp(k,vector<int>(n,INT_MAX>>1));


        for(int i=0;i<n;i++)
        dp[0][i]=((i==0)?0:dp[0][i-1])+pages[i];

        for(int ki=1;ki<k;ki++)
        {
            for(int ni=ki;ni<n;ni++)
            {
                for(int nj=ki-1;nj<ni;nj++)
                {
                    int sum=dp[0][ni]-dp[0][nj];
                    dp[ki][ni]=min(dp[ki][ni],max(dp[ki-1][nj],sum));
                }
            }
        }

        return dp.back().back();
    }
};

O(n*k)时间复杂度

合理利用了抄ni-1本书ki-1个人时候情况

详细

class Solution {
public:
    /**
     * @param pages: a vector of integers
     * @param k: an integer
     * @return: an integer
     */
    int copyBooks(vector<int> &pages, int k) {
        // write your code here

        if(pages.size()<=k)
        {
            int maxVal=0;
            for(int i=0;i<pages.size();i++)
            maxVal=max(maxVal,pages[i]);

            return maxVal;
        }

        int n=pages.size();
        vector<int> sum(n);

        vector<vector<int>> dp(n,vector<int>(k,INT_MAX>>1));

        for(int i=0;i<pages.size();i++)
        {
            sum[i]+=((i==0)?0:sum[i-1])+pages[i];
            dp[i][0]=sum[i];
        }

        for(int ki=1;ki<k;ki++)
        {
            //不要在这种地方自作聪明加上ni=1，以为可以优化！！！！
            //会导致dp[0][ki]是初始值很大样子
            int ni=0;
            int left=0;

            while(ni<n)
            {
                dp[ni][ki]=min(dp[ni][ki],max(dp[left][ki-1],sum[ni]-sum[left]));
                if(dp[left][ki-1]<=sum[ni]-sum[left])
                {
                    left++;
                }
                else
                {
                    ni++;
                    if(left>0)left--;
                }
            }
        }
        return dp.back().back();
    }
};