Leetcode Challenge: Two City Scheduling (6/3)

今天的题目原出处是 №1029 (https://leetcode.com/problems/two-city-scheduling/)，算是较新的题目。简单来说就是有 2N 个人要把他们丢到 A 跟 B 两个城市，每个人要被丢到 A 或 B 都有各自的 Cost，最后关键的是两个城市最后都要有 N 个人啰！

一开始可能会想说，那我就先 “贪婪地” (greedy) 把丢到 A 的 Cost 先排序，把前 N 低的，丢到 A，剩下的人再丢到 B，但很明显这是有问题的，假设以 Example 1 来说，我们先用丢到 A 的 Cost 进行排序得到 [10, 20], [30, 20], [30, 200], [400, 50] ，结果反而让丢到 B 的 Cost 大爆炸 (200+50)。反过来根据 B 的 Cost 排序当然也有问题 (你怎么知道要用 A 还是 B 的 Cost 来排序？！)

所以这题基本上还是可以用 Greedy 的方式，但是要排序 (升序) 的是 “丢到 Cost A 和 Cost B 的差”！我们先以这个思想把 Example 1 排出来会得到 [30, 200], [10, 20], [30, 20], [400, 50] (因为 “差” 的排序是 -170, -10, 10, 350 )，因为这里只有四个人，所以我们就把前两个就会丢到 A (30 and 10)，后两个则是丢到 B (20 and 50)。这样排序的理由是，以 [30, 200] 来说，要是我不选 A (30)，而选了 B (200)，那么成本会比选 A 大大地多了 170 ，为了不让这个情况发生，我这时候更一定要选 A 了，这样你有感觉了吗？让我们再看最后一个 [400, 50] ，要是此时我不选 B，而是选 A，那么选 A 的成本就会比选 B 的成本大大增加了 350 ！相信聪明的人看到这应该已经懂了！那么最后就让我们来看 Code 。

Code 的部分就跟上述一模一样啦！Line 3 作排序，而排序是根据 “丢到 Cost A 和 Cost B 的差” (x[0]-x[1]) ，再来就是把前 N 个的 Cost of A 放到 totalCost，以及把后 N 个的 Cost of B 放到 totalCost 。就酱！

class Solution:    def twoCitySchedCost(self, costs: List[List[int]]) -> int:        sortedCosts = sorted(costs, key=lambda x: x[0] - x[1])        totalCost  = 0        for i in range(len(costs)//2):            totalCost += sortedCosts[i][0]        for i in range(len(costs)//2, len(costs)):            totalCost += sortedCosts[i][1]        return totalCost

彩蛋！如果你想要用 DP 的话该怎么做呢？记得 DP 两部曲吗？状态的定义，以及状态转移方程式 (忘记的看 这里 )。这里原先的问题是，如果有 2N 个人，其中某 N 个人在 A (代表其他 2N-N=N 的人在 B) 的 Cost，那么子问题就是如果有 i 个人，其中 j 个人在 A (代表其他 i-j 的人在 B) 的 Cost 是多少。因此 dp[i][j] 就是如果有 i 个人，其中 j 个人在 A 的 Cost 啦！状态转移方程式则是 dp[i][j] = min(dp[i-1][j] + costs[i-1][1], dp[i-1][j-1] + costs[i-1][0]) ，就是看 1. 把 i是丢到 A 2. 把i 丢到 B 哪一个成本比较小。(这里要注意的是 costs[i-1] 的 i-1 是因为这里 i 是指第 i 个人，但是 costs 是从 0 开始。) 不过 DP 要花的时间跟空间自然比较高啰！(O(N²))

class Solution:    def twoCitySchedCost(self, costs: List[List[int]]) -> int:        dp = [[float('inf') for j in range(len(costs)//2 + 1)] for i in range(len(costs) + 1)]        dp[0][0] = 0        for i in range(1, (len(costs) // 2) + 1):            dp[i][0] = dp[i-1][0] + costs[i-1][1]                 for i in range(1, len(costs) + 1):            for j in range(1, len(costs) // 2 + 1):                dp[i][j] = min(dp[i-1][j] + costs[i-1][1], dp[i-1][j-1] + costs[i-1][0])                return dp[len(costs)][len(costs) // 2]

See YA!

欢迎追蹤我的 Medium 啰！
https://medium.com/@ryanyang1221