题解 | #牛奶供应问题#

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param taskDurations int整型一维数组 
# @param capacity int整型 
# @return int整型
#
class Solution:
    def animalTaskScheduler(self , taskDurations: List[int], capacity: int) -> int:
        # write code here
        # 几个一组，不能改变顺序，每次选择1-c个任务执行
        # n < 10**3
        # 动态规划 dp[i] 表示完成i任务最短的时间 
        # dp[i] = min(dp[i-c] + max(nums[i-c+1:i+1]), dp[i-c+1] + max()...)
        nums = taskDurations
        k = capacity
        n = len(nums)
        dp = [10**9]*n
        # initialise
        for w in range(1, k+1): # 可以每次包含1-k个任务
            temp = max(nums[0:0+w]) # w个任务同时执行
            dp[0+w-1] = min(temp, dp[0+w-1]) 
            
        # print(dp[:10])
        for i in range(1, n): 
            for w in range(1, k+1): # 做几个任务
                # transition
                if i-w >= 0:
                    dp[i] = min(dp[i], dp[i-w] + max(nums[i-w+1: i+1]))
        
        # print(dp)
        return dp[-1]

第一眼感觉是动态规划，dp[i]记录到当前i任务最短需要多长时间，每次只能执行1-k个任务，那我们就知道当前状态可以从k个前置状态转移而来：当前步做1、2、3。。。k个任务，取最小值即可。所以transition function：

for w in range(1, k+1):

dp[i] = dp[i-w] + max(nums[i-w+1:i+1))