Leetcode題解 Python & C#：六月挑戰DAY3 Two City Scheduling

要把 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;
    }
}