Copy Books--Partition DP

一定有 连续

Description

Given _n _books and the _i_th book hasA[i]pages. You are given _k _people to copy the _n _books.

_n _books list in a row and each person can claim a continous range of the_n_books. For example one copier can copy the books from_i_th to _j_th continously, but he can not copy the 1st book, 2nd book and 4th book (without 3rd book).

They start copying books at the same time and they all cost 1 minute to copy 1 page of a book. What's the best strategy to assign books so that the slowest copier can finish at earliest time?

Example

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

Return5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

为什么是划分型DP？

因为可以把抄写员抄书的过程变成分段的问题