要把 2n 個人，平分給 cityA 和 cityB，costs[i] 代表第 i 個人，costs[i][0] 代表第 i 個人到 cityA 的花費，而 costs[i][1] 則是到 cittyB。要回傳最小總花費。※去 cityA 和 去 cityB 都應該有 n 個人。
一看到題目，馬上用DP解，因為我解的上一題是也是分配的問題。不過一看到用時，就知道這不是好的寫法。
對總體來說，如果每個人都以「相對代價」較低的為目的地，就可以找到最佳分配的情形。
相對代價 costs[i][0] – costs[i][1]，我們讓前 n 個相對代價較小的到 cityA ，後面的到 cityB，就是最佳方案。
(若有 3 個以上的選擇，就不能用這算法。)
Python(DP)
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
n = len(costs)//2
@lru_cache(None)
def dfs(n1, n2):
if n1 + n2 == n*2:
return 0
i = n1 + n2
path = set()
if n1 < n:
path.add(costs[i][0] + dfs(n1+1, n2))
if n2 < n:
path.add(costs[i][1] + dfs(n1, n2+1))
return min(path)
return dfs(0,0)
Python
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
costs.sort(key = lambda x: x[0] - x[1])
n = len(costs)//2
result = 0
for i in range(n):
result += costs[i][0] + costs[i+n][1]
return result
C#
public class Solution {
public int TwoCitySchedCost(int[][] costs) {
int n = costs.Length / 2;
int result = 0;
int[][] sorted_costs = costs.OrderBy(x => (x[0]-x[1])).ToArray();
for(int i = 0; i < n; i++)
result += sorted_costs[i][0] + sorted_costs[i+n][1];
return result;
}
}