Question

from lintcode
Given n books( the page number of each book is the same) and an array of integer with size k means k people to copy the book and the i th integer is the time i th person to copy one 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.) Return the number of smallest minutes need to copy all the books.
Example
Given n = 4, array A = [3,2,4], .

Return 4( First person spends 3 minutes to copy book 1, Second person spends 4 minutes to copy book 2 and 3, Third person spends 4 minutes to copy book 4. )

Idea

As explained in the code comments.

package ladders.copyBooksII.dynamicProgramming;

public class Solution {
    /**
     * @param allBooks: an integer
     * @param times: an array of integers
     * @return: an integer
     */
    public int copyBooksII(int allBooks, int[] times) {

        // number of people
        int numOfPeople = times.length;

        // f[2 states][0 to n books]
        // why 2 states? current person and previous person
        // we move from first person, some books, next person, some books...
        // until N books, we know that
        // from the first person to the previous person, N - x books have been processed
        // where x is the one who minimizes the path time bound
        // term explain: "path time bound" means the total time consumed for processing all books,
        // which is determined by just one person who consumes most time, namely "time bound".
        // "path" means there is a path from the first person to this person.
        // e.g. for 5 books with people [4, 2, 3]
        // {1 * 4 + 2 * 2 + 3 * 2} is one path for previous 5 books
        // {1 * 4 + 2 * 2 } is one path for previous 3 books
        int[][] minPathBound = new int[2][allBooks+1];

        // f: minimum "path time bound"
        // initialization:
        // the path is unique for the first person given a number of books
        for (int prevNBooks = 0 ; prevNBooks <= allBooks; prevNBooks++) {
            minPathBound[0][prevNBooks] = prevNBooks * times[0];
        }

        // from 1st-indexed person to kth-indexed person (second person to last person)
        for (int personI = 1; personI < numOfPeople; personI++) {

            // from 1 book to n books
            for (int assignedBooks = 1; assignedBooks <= allBooks; assignedBooks++) {

                // current person position
                int currentPerson = personI % 2;
                // previous person position
                int prevPerson = (personI - 1) % 2;

                // from first person to previous person, totally processed N - x books,
                // to this person, will process n books
                // iterate each possibility of x, pick the minimum path bound
                minPathBound[currentPerson][assignedBooks] = Integer.MAX_VALUE;
                for (int xBookNum = 0; xBookNum <= assignedBooks; xBookNum++) {
                    // previous person already handle j-l books
                    // and consume a greater time than current person
                    int finishedBooks = assignedBooks - xBookNum;

                    int pathBound =
                            Math.max(minPathBound[prevPerson][finishedBooks], times[personI] * xBookNum);

                    // update the minimum in the iteration
                    minPathBound[currentPerson][assignedBooks] =
                            Math.min(minPathBound[currentPerson][assignedBooks], pathBound);

                    // we want minimum only
                    // now that times[personI] * bookNum already exceeds original path bound
                    // more books for this person only leads to more time consumption
                    // so, we can just break
                    if (minPathBound[prevPerson][finishedBooks] <= times[personI] * xBookNum) {
                        break;
                    }
                }
            }
        }
        // f[last person][all books]
        return minPathBound[(numOfPeople-1)%2][allBooks];
    }
}