# 1029. Two City Scheduling

{% embed url="<https://leetcode.com/problems/two-city-scheduling/>" %}

一点都不easy啊...竟然是这样`greedy`出来的，让我想起比较优势理论 Comparative advantage。

12/27/2020 Update:&#x20;

也可以用DP做，但这题没法记忆，会TLE。**Try to assign a person to both cities if its possible** (a typical DP technique) and **return the minimum of it**.

{% tabs %}
{% tab title="Greedy" %}

```python
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        res = 0
        costs.sort(key=lambda x: x[0]-x[1])
        for i in range(len(costs)//2):
            res += costs[i][0] + costs[-i-1][1]
        return res
```

{% endtab %}

{% tab title="DP" %}

```python
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs)//2
        
        def dp(idx, countA):
            if countA > n:
                return float('inf')
            if idx == len(costs):
                if countA == n:
                    return 0
                else:
                    return float('inf')
            return min(costs[idx][0]+dp(idx+1, countA+1),
                      costs[idx][1]+dp(idx+1, countA))
        
        return dp(0, 0)
```

{% endtab %}
{% endtabs %}
