0

## Leetcode Challenge: Two City Scheduling (6/3)

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
``````

``````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!

https://medium.com/@ryanyang1221