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

You can give arbitrary books to current person, and give the remained ones to next person... Try all possibilities by DFS search. Remember to cache some calculated results.

Note: This solution can only pass 65% of the test cases. I will update a better one later.

``java
/**

• f(i, remain)

• f represents the minimum time required to finish the remained books when starting from i-indexed person
  /
  public class Solution {
  /*

  • @param n: An integer

  • @param times: an array of integers

  • @return: an integer
    */
    public int copyBooksII(int numOfBooks, int[] times) {

    if (times.length == 0) return Integer.MAX_VALUE;
    if (numOfBooks == 0) return 0;

    this.times = times;
    this.computed = new int[times.length + 1][numOfBooks + 1];
    for (int i = 0; i < computed.length; i++)
    for (int j = 0; j < computed[0].length; j++)
    computed[i][j] = -1;
    return compute(0, numOfBooks);
    }

  private int[] times;

  private int[][] computed;

  private int compute(int i, int remainBooks) {
  if (i == times.length)
  return Integer.MAX_VALUE;
  if (this.computed[i][remainBooks] > 0)
  return this.computed[i][remainBooks];

  int minTime = Integer.MAX_VALUE;
  /**
   *  try each possible paths
   */
  for(int books = 0; books <= remainBooks; books++) {
      int consume = books * this.times[i];
      int minConsumeOfPath;
      if (books == remainBooks) {
          minConsumeOfPath = consume;
      } else {
          /**
           *  why Math.max?
           *  The shortest time was bounded by the person who consumes the most time
           */
          minConsumeOfPath = Math.max(consume, compute(i + 1, remainBooks - books));
      }
      minTime = Math.min(minTime, minConsumeOfPath);
  }
  
  this.computed[i][remainBooks] = minTime;
  return minTime;
  

  }
  }