Leetcode 1029. Two City Scheduling

题目

解法

解法1:贪心

利用a-b的差值从小到大排序，前n个人去a，剩下的去b，利用的贪心思想。但是这个解法细想并没有非常令人信服的解释，起码我不能完全说服自己为什么这么做是对的

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

解法2:背包动态规划

这道题标准的解法应该是背包。一个人去a还是b类似背包问题取不取。难点在于这边有限制：a和b去的人数必须一半一半。做法是，固定dp的形状为n*n，这样就可以保证最右下角的元素就是符合条件的答案

class Solution:def twoCitySchedCost(self, costs: List[List[int]]) -> int:n = int(len(costs)/2)# define dp matrix, dp[i][j] means the min cost of i person go to city a and j person go to city bdp = [[0] * (n+1) for _ in range(n+1)]# initialize the condition where all person go to city a or bfor i in range(1,n+1):dp[i][0] = dp[i-1][0] + costs[i-1][0]for i in range(1,n+1):dp[0][i] = dp[0][i-1] + costs[i-1][1]# for every person, take the min of current person going to city a or bfor i in range(1,n+1):for j in range(1,n+1):dp[i][j] = min(dp[i-1][j] + costs[i+j-1][0], dp[i][j-1] + costs[i+j-1][1])return dp[-1][-1]

背包问题详解可以看这边