这次分享一道 Stripe 的 Coding 面试真题。题目以供应链为背景：原材料、组装、包装分别有一组候选工厂，每个工厂的制造成本不同，还可能产生铁路运输费用。

整道题分成三个 Part，条件逐步增加，重点在于如何把最初的简单选择扩展成通用解法。

Given multiple groups of factories, each factory has a manufacturing cost and a position along a railroad.

Select exactly one factory from each group, in order, to minimize the total cost.

1. Part 1: There are 3 factory groups (materials, assembly, packaging). All positions are 0, so shipping is free. Find the minimum manufacturing cost.
2. Part 2: Factories have different positions. Shipping between consecutive factories costs the absolute difference between their positions. Minimize manufacturing + shipping costs.
3. Part 3: Generalize the solution to support any number of factory groups (at least 3), while minimizing total manufacturing and shipping costs.

每个生产环节都有多个工厂可选，必须按照环节顺序，从每组恰好选出一家。目标是让所有被选工厂的制造成本，加上相邻生产环节之间的运输费用，达到最低。

Part 1 只有原材料、组装、包装三组工厂，所有工厂都位于铁路坐标 0，运输费用为零。这个版本直接在每组挑制造成本最低的工厂，再把三个最小值相加即可。例如三组的最低成本分别是 4、3、5，答案就是 12。

Part 2 加上了工厂位置。相邻两家被选中工厂的运输费用，等于它们铁路坐标之差的绝对值。此时单独挑每组最便宜的工厂，就可能让运费过高。

举个例子，原材料组有两家工厂，成本和位置分别是 (1, 0)、(3, 10)；组装组也有 (1, 0)、(3, 10)；包装组只有 (1, 10)。

如果每组都选制造成本最低的工厂，总费用是 1 + 1 + 1 + 0 + 10 = 13。选择三家都位于坐标 10 的工厂，总费用只有 3 + 3 + 1 = 7。

这里适合使用动态规划（Dynamic Programming）。

对于当前组的每一家工厂，记录“选中这家工厂时，从第一组走到这里的最低总成本”。转移时，枚举上一组的工厂，把上一组的最优费用、两家工厂之间的运费、当前工厂的制造成本相加，取其中最小值。这样前面已经发生的生产和运输成本都能被正确保留下来。

可以用一行表达核心逻辑：

dp[i][j] = cost[i][j] + min(dp[i-1][k] + abs(pos[i][j] - pos[i-1][k]))

其中 k 遍历上一组的全部工厂。

Part 3 要求扩展到任意数量的工厂组。其实沿用同一套 DP 即可：先用第一组各工厂的制造成本初始化，再按组依次计算，最终取最后一组的最小值。每次只需要保存上一组的结果，不必保留整张 DP 表。

如果相邻两组分别有 m 和 n 家工厂，这两组之间的转移耗时 O(mn)；整体时间复杂度是所有相邻组工厂数量乘积之和，额外空间复杂度为 O(最大单组工厂数)。

还有一个容易忽略的细节：工序顺序是固定的，铁路位置不要求递增，运输费用也只计算相邻两个被选中的生产环节。

这道题的三个 Part 衔接得很自然。第一部分可以直接取最小值，第二部分需要把路径成本放进状态，第三部分考察能否把三组的写法扩展到更多组。

把状态含义、转移过程和边界条件说清楚，思路就比较完整了。

关于 CSOAHelp

CSOAHelp 持续整理 Stripe 等北美科技公司的 Coding 面试题，也提供 Mock Interview 和实时 VO 辅助。

遇到这种连续增加条件的题目，我们可以协助梳理算法框架、检查边界与复杂度、组织清晰的英文解释，让面试过程更从容。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~