题目描述
公司计划面试 2N
人。第 i
人飞往 A
市的费用为 costs[i][0]
,飞往 B
市的费用为 costs[i][1]
。
返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N
人抵达。
样例
输入:[[10,20],[30,200],[400,50],[30,20]]
输出:110
解释:
第一个人去 A 市,费用为 10。
第二个人去 A 市,费用为 30。
第三个人去 B 市,费用为 50。
第四个人去 B 市,费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110,每个城市都有一半的人在面试。
说明
1 <= costs.length <= 100
costs.length
为偶数1 <= costs[i][0], costs[i][1] <= 1000
算法1
(动态规划) $O(n^2)$
- 设 $f(i, j)$ 表示考虑了前 $i$ 个人,其中有 $j$ 个人去了
A
市的最低费用。人的有效下标从 0 开始。 - 初始时,$f(0, 1) = costs[i][0]$,$f(0, 0) = costs[i][1]$,其余为正无穷。
- 转移时,$f(i, j) = \min(f(i - 1, j - 1) + costs[i][0], f(i - 1, j) + costs[i][1])$,分别表示派遣这个人去
A
市或者去B
市。 - 最终答案为 $f(n - 1, n / 2)$。
时间复杂度
- 状态数为 $O(n^2)$,转移时间为常数,故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要额外 $O(n^2)$ 的空间存储状态。
C++ 代码
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
const int INF = 1000000000;
int n = costs.size();
vector<vector<int>> f(n, vector<int>(n / 2 + 1, INF));
f[0][1] = costs[0][0];
f[0][0] = costs[0][1];
for (int i = 1; i < n; i++)
for (int j = 0; j <= n / 2; j++) {
if (j > 0)
f[i][j] = min(f[i][j], f[i - 1][j - 1] + costs[i][0]);
f[i][j] = min(f[i][j], f[i - 1][j] + costs[i][1]);
}
return f[n - 1][n / 2];
}
};
算法2
(贪心) $O(n \log n)$
- 将所有人按照(去
A
市的花费减去去B
市的花费)从小到大排序。 - 按照这个顺序,前一半的人去
A
市,后一半的人去B
市。 - 如果某个最优答案没有按照这个顺序,则交换到这个顺序后不会比当前最优答案更差。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$,排序后仅需要遍历一次数组。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
sort(costs.begin(), costs.end(),
[](const vector<int> &x, const vector<int> &y) {
return x[0] - x[1] < y[0] - y[1];
});
int n = costs.size();
int ans = 0;
for (int i = 0; i < n / 2; i++)
ans += costs[i][0];
for (int i = n / 2; i < n; i++)
ans += costs[i][1];
return ans;
}
};