书本分发

Description

You are given N number of books. Every ith book has Pi number of pages. You have to allocate books to M number of students. There can be many ways or permutations to do so. In each permutation one of the M students will be allocated the maximum number of pages. Out of all these permutations, the task is to find that particular permutation in which the maximum number of pages allocated to a student is minimum of those in all the other permutations, and print this minimum value. Each book will be allocated to exactly one student. Each student has to be allocated atleast one book.

思路

一个典型的动态规划，尝试分配1|2|3...|n-1个任务给当前的人，再递归剩下的任务和人数

1. 假设当前分配x个任务给第一个人，那么分配方式的结果是sum(task1, task2...task_x)和子问题f(n-x, people_nums-1)，两者中的最大值。

2. 对上述的不同x，找出对应分配方式的最小值返回

递推公式：

f(n, p) = min(max(sum[task_1~task_i], f(n-i, p-1)), 1 <= i <= n
递归结束条件是n == 0（没有任务）或者 p==1（只剩下一个人可以分配任务）

时间复杂度O(n^2)

python

from functools import lru_cache
def solve(p, tasks):
    @lru_cache(None)
    def dfs(rp, it):
        if rp == 1:
            return sum(tasks[it:])
        if it == len(tasks) - 1:
            return tasks[-1]
        rp -= 1

        ans, cursum = float('inf'), 0
        for j in range(it, len(tasks)):
            cursum += tasks[j]
            ans = min(ans, max(cursum, dfs(rp, j+1)))
        return ans

    return dfs(p, 0)