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;}
}
