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.

Have you met this question in a real interview?

Yes

Example

Given n =4, array A =[3,2,4], .

Return4( 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. )

等同于

把问题转化为，把N本书分成K段抄，

枚举K的过程中，每一个方案最长的一段为该方案的答案，

选所有方案中最短的方案

f[i][j] 为前i个人抄前j本书的最短时间

f[i][j] = min {max{f[i - 1][k], A[i - 1] * (j - k)}, k -> {0, j}}

f[0][j] = max value j > 0

f[i][0] = 0

（优化： 可以比 f[i-1][j - k] 和 A[i - 1] * k, 如果一旦 f[i - 1][j - k] < A[i - 1] * k 那么随着k的增加，f[i - 1][j - k]会越来越小因为书越来越多， 而A[i - 1] * k 会越来越大，所以不会再改变最终的答案，可以直接break

public int copyBooksII(int n, int[] times) {
        // write your code here
        if (n == 0 || times.length == 0) {
            return 0;
        }

        if (times.length == 1) {
            return n * times[0];
        }

        int[][] f = new int[2][n + 1];


        for (int i = 1; i <= n; i++) {
            f[0][i] = Integer.MAX_VALUE;
        }

        int now = 0;
        int old = 0;
        for (int i = 1; i <= times.length; i++) {
            old = now;
            now = 1 - now;
            for (int j = 1; j <= n; j++) {
                f[now][j] = Integer.MAX_VALUE;
                for (int k = 0; k <= j; k++) {
                    if (f[old][j - k] > times[i - 1] * k) {
                        f[now][j] = Math.min(f[now][j], f[old][j - k]);
                    } else {
                        f[now][j] = Math.min(f[now][j], times[i - 1] * k);
                        break;
                    }
                }
            }
        }

        return f[now][n];
    }