关于LeetCode两地调度问题DP递推关系的合理性问询

问题背景 #

LeetCode上的两地调度问题：公司计划面试2n名候选人，给定费用数组costs，其中costs[i] = [aCost, bCost]，代表第i名候选人前往城市A的费用为aCost，前往城市B的费用为bCost。要求返回让每个城市都恰好接收n名候选人的最低总费用。

提出的DP递推方案 #

我设计了如下动态规划递推关系：

OPT[i][w] = min{cost[i][0] + OPT[i+1][w-1], cost[i][1] + OPT[i+1][w]}

各参数定义：

• OPT[i][w]：处理到第i名候选人时，城市A剩余可容纳人数为w的情况下，分配当前及后续候选人的最小总成本
• 选择cost[i][0] + OPT[i+1][w-1]：将第i名候选人分配到城市A，此时A的剩余容量减少1
• 选择cost[i][1] + OPT[i+1][w]：将第i名候选人分配到城市B，此时A的剩余容量保持不变

最终期望通过计算OPT[0][n]得到最小总成本——即从第0名候选人开始分配，城市A初始剩余容量为n时的最优解。

疑问 #

我在这个DP状态中没有跟踪城市B的剩余容量，仅假设当城市A满员（剩余容量为0，共分配n人）时，城市B会自动满员n人。请问这个逻辑是否可行？

相关截图 #

• 递推逻辑示意图：
• 原题题目截图：

内容的提问来源于stack exchange，提问作者penguin365