题目

给你两个长度分别为 n 和 m 的整数数组 skill 和 mana 。

在一个实验室里，有 n 个巫师，他们必须按顺序酿造 m 个药水。每个药水的法力值为 mana[j]，并且每个药水 必须 依次通过 所有 巫师处理，才能完成酿造。第 i 个巫师在第 j 个药水上处理需要的时间为 timeij = skill[i] * mana[j]。

由于酿造过程非常精细，药水在当前巫师完成工作后 必须 立即传递给下一个巫师并开始处理。这意味着时间必须保持 同步，确保每个巫师在药水到达时 马上 开始工作。

返回酿造所有药水所需的 最短 总时间。

示例 1：

输入： skill = [1,5,2,4], mana = [5,1,4,2]

输出： 110

解释：

举个例子，为什么巫师 0 不能在时间 t = 52 前开始处理第 1 个药水，假设巫师们在时间 t = 50 开始准备第 1 个药水。时间 t = 58 时，巫师 2 已经完成了第 1 个药水的处理，但巫师 3 直到时间 t = 60 仍在处理第 0 个药水，无法马上开始处理第 1个药水。

示例 2：

输入： skill = [1,1,1], mana = [1,1,1]

输出： 5

解释：

1. 第 0 个药水的准备从时间 t = 0 开始，并在时间 t = 3 完成。
2. 第 1 个药水的准备从时间 t = 1 开始，并在时间 t = 4 完成。
3. 第 2 个药水的准备从时间 t = 2 开始，并在时间 t = 5 完成。

示例 3：

输入： skill = [1,2,3,4], mana = [1,2]

输出： 21

提示：

• n == skill.length
• m == mana.length
• 1 <= n, m <= 5000
• 1 <= mana[i], skill[i] <= 5000

解题思路

核心思想：逐个优化生产线

我们可以把为 m 个药水排产的过程看作是启动 m 条独立的“流水线”。我们一条一条地规划，目标是在规划第 j 条流水线（即生产第 j 个药水）时，让它的最终完成时间尽可能早。

1. 第一条流水线 (第一个药水)
   • 这是最简单的情况。第一个药水没有任何前置约束。
   • 我们假设它在时间 t=0 时由第一个巫师开始处理。
   • 后续每个巫师的完成时间就是前一个巫师的完成时间，加上他自己的处理时间。这本质上是一个简单的累加过程。
   • 完成这一步后，我们就得到了一个完成时间数组 T_0，其中 T_0[i] 代表第 i 个巫师完成第一个药水的时间点。
2. 后续的流水线 (第 j 个药水, j > 0) 这是问题的关键。在开始处理第 j 个药水前，我们面临一个决策：应该让第一个巫师在什么时间点（我们称之为“开工时间” S_j）开始处理这个新药水？
   • 开工时间 S_j 的影响：
     • 如果 S_j 太早：第一个巫师可能很早就完成了，但药水传到下游的某个巫师 k 时，发现巫师 k 还在处理上一个药水 j-1。这时药水就要等待，产生了“管道气泡”（idle time），总时间并不会缩短。
     • 如果 S_j 太晚：整个流水线被无谓地延后了，导致最终完成时间变晚。
   • 寻找最优开工时间 S_j： 最优的 S_j 应该是最早的、且不会在任何巫师处产生“等待上一个药水”这种瓶颈的时间点。 我们可以对每一个巫师 k 进行分析，计算出一个能让他“无缝衔接”的 S_j 的下限：这个不等式必须对所有巫师 k 都成立。因此，我们必须选择满足所有巫师需求的那个最大的下限值作为我们的最优开工时间： S_j = max( T_{j-1}[k] - C_j[k-1] ) (对所有巫师 k 取最大值)
     • 巫师 k 完成上一个药水 j-1 的时间点是 T_{j-1}[k]。
     • 当前药水 j 如果在 S_j 时刻开工，它“裸奔”（不考虑等待）到达巫师 k 的开工时间是 S_j 加上从巫师 0 到 k-1 的累计处理时间 C_j[k-1]。
     • 要让巫师 k 不成为瓶颈，必须满足：S_j + C_j[k-1] >= T_{j-1}[k]。
     • 移项得到：S_j >= T_{j-1}[k] - C_j[k-1]。
   • 计算当前流水线的完成时间： 一旦确定了最优开工时间 S_j，我们就可以计算第 j 个药水在所有巫师手中的完成时间了。
     • 第一个巫师的完成时间： T_j[0] = S_j + (skill[0] * mana[j])
     • 后续巫师 k 的完成时间遵循标准的动态规划递推： T_j[k] = max(T_j[k-1], T_{j-1}[k]) + (skill[k] * mana[j])
3. 最终结果 重复步骤2，直到计算完最后一个药水。最后一个药水在最后一个巫师手中的完成时间 T_{m-1}[n-1] 就是最终答案。

该算法的流程是：

初始化 (药水0) -> 循环 (对于后续每个药水) -> { 寻找最优开工时间 -> 计算该药水在所有巫师处的完成时间 } -> 返回最终结果。

这种思路通过在每一步做出最优决策（选择最佳开工时间），最终得到了全局最优解。

具体代码

生成具体表格

这个代码能生成完整的分析流程，但是整体比较重。

func minTime(skill []int, mana []int) int64 {

	n := len(mana)  // n 为药水数量
	m := len(skill) // m 为巫师数量

	// dp[i][j] 用于存储与第 i 个药水和第 j 个巫师相关的时间数据
	// 初始存储累计处理时间，后续更新为最终完成时间
	dp := make([][]int64, n)
	for i := range dp {
		dp[i] = make([]int64, m+1)
	}

	// 步骤1: 预计算每种药水不受干扰时的累计处理时间 (C_i[j-1])
	// dp[i][j] = skill[0]*mana[i] + ... + skill[j-1]*mana[i]
	for i := 0; i < n; i++ {
		for j := 1; j < m+1; j++ {
			dp[i][j] = dp[i][j-1] + int64(skill[j-1])*int64(mana[i])
		}
	}

	// 步骤2: 迭代计算每种药水的最终完成时间
	// helper 用于临时存储计算开工时间所需的数据
	helper := make([]int64, m)
	// 第0个药水的完成时间就是其累计处理时间，已在步骤1中算好，所以从第1个药水开始
	for i := 1; i < n; i++ {
		// --- 2a: 计算当前药水 i 的最优开工时间 S_i ---
		// S_i = max(T_{i-1}[k] - C_i[k-1])
		// T_{i-1}[k] 即 dp[i-1][k+1]
		// C_i[k-1]   即 dp[i][k] (预计算的值)
		for k := range helper {
			helper[k] = dp[i-1][k+1] - dp[i][k]
		}
		// 最优开工时间 S_i 存入 dp[i][0]
		dp[i][0] = Max(helper)

		// --- 2b: 更新当前药水 i 在每个巫师处的最终完成时间 T_i[j-1] ---
		// T_i[j-1] = S_i + C_i[j-1]
		for j := 1; j < m+1; j++ {
			// dp[i][0] 是 S_i
			// dp[i][j] 在右侧是预计算的 C_i[j-1]
			dp[i][j] = dp[i][0] + dp[i][j]
		}
	}

	// 返回最后一个药水在最后一个巫师处的完成时间
	return dp[n-1][m]
}

// Max 是一个寻找切片中最大值的辅助函数
func Max(vector []int64) int64 {
	var max_num int64 = 0
	for _, num := range vector {
		if num > max_num {
			max_num = num
		}
	}
	return max_num
}

时间优化版

用一个一维数组，更快一些

func minTime(skill []int, mana []int) int64 {
	n := len(skill) // 巫师数量
	m := len(mana)  // 药水数量
	if n == 0 || m == 0 {
		return 0
	}

	// `finishTimes[i]` 存储当前正在处理的药水，在巫师 i 手中完成的时间点。
	// 它是一个滚动数组，每一轮循环都会被新药水的数据覆盖。
	finishTimes := make([]int64, n)

	// --- 步骤 1: 初始化，计算第一个药水 (mana[0]) 的完成时间 ---
	// 第一个药水没有前置依赖，它的生产过程是一个简单的累加。
	var cumulativeTime int64 = 0
	for i, s := range skill {
		cumulativeTime += int64(s) * int64(mana[0])
		finishTimes[i] = cumulativeTime
	}

	// --- 步骤 2: 循环处理后续的每一个药水 ---
	for j := 1; j < m; j++ {
		currentMana := int64(mana[j])

		// --- 步骤 2a: 计算当前药水的“最优开工时间” (Optimal Start Time) ---
		// 这是整个算法的核心。我们寻找一个最早的时刻 S_j，让巫师0开始处理当前药水，
		// 且能保证这瓶药水在到达任何下游巫师 k 手中时，巫师 k 都已完成上一个药水的工作。
		// 这个“完美”的开工时间 S_j 可以通过以下公式计算：
		// S_j = max_{k=0..n-1} ( T_{j-1}[k] - C_j[k-1] )
		// 其中 T_{j-1}[k] 是上一轮的 finishTimes[k]，
		// C_j[k-1] 是当前药水到巫师 k-1 的累计无等待处理时间。
		var optimalStartTime int64 = 0
		var cumulativeProcessingTimeForCurrentPotion int64 = 0
		for k := 0; k < n; k++ {
			// finishTimes[k] 此刻存储的是上一个药水的完成时间 T_{j-1}[k]
			// cumulativeProcessingTimeForCurrentPotion 此刻是 C_j[k-1]
			if finishTimes[k]-cumulativeProcessingTimeForCurrentPotion > optimalStartTime {
				optimalStartTime = finishTimes[k] - cumulativeProcessingTimeForCurrentPotion
			}
			// 为下一次循环迭代更新累计时间，使其成为 C_j[k]
			cumulativeProcessingTimeForCurrentPotion += int64(skill[k]) * currentMana
		}

		// --- 步骤 2b: 基于最优开工时间，更新当前药水的完成时间 ---
		// 关键洞察：正是因为我们选择了上述“完美”的 optimalStartTime，
		// 复杂的标准递推公式 T_j[i] = max(T_j[i-1], T_{j-1}[i]) + P_j[i]
		// 得以简化。这个开工时间确保了 T_j[i-1] >= T_{j-1}[i] 总是成立。
		// 因此，递推关系简化为 T_j[i] = T_j[i-1] + P_j[i]，
		// 也就是一个基于 optimalStartTime 的简单累加。
		cumulativeProcessingTimeForCurrentPotion = 0
		for i, s := range skill {
			cumulativeProcessingTimeForCurrentPotion += int64(s) * currentMana
			finishTimes[i] = optimalStartTime + cumulativeProcessingTimeForCurrentPotion
		}
	}

	return finishTimes[n-1]
}