题目大意：
两地调度
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。
示例：
输入：[[10,20],[30,200],[400,50],[30,20]] 输出：110 解释： 第一个人去 A 市，费用为 10。 第二个人去 A 市，费用为 30。 第三个人去 B 市，费用为 50。 第四个人去 B 市，费用为 20。 最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
提示：
- 1 <= costs.length <= 100
- costs.length 为偶数
- 1 <= costs[i][0], costs[i][1] <= 1000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1029
解题思路分析：
这道题的解法有很多，本文我们尝试使用动态规划DP的方式来解题。另外，对于DP类的题目，我更喜欢采用递归加记忆数组的方式来替代传统DP。
首先我们建立一个递归函数，函数中传入2个参数，分别是当前已分配到A地的人数，以及B地的人数。递归函数的返回值为将剩下未分配的人都分配完之后最小的花费。当前递归中，当前待分配人的下标应该是A加上B的和（已分配完总人数）。如果A人数或者B人数大于总人数二分之一时，代表当前这是一种不合理分配，返回一个int最大值。如果人数A加人数B等于总人数，代表所有人已分配完毕，返回0。除了上述特殊情况外，我们在当前递归中有两种选择：
- 将当前人分配到A地，此时，A人数加一，B人数不变，我们将该状态传入递归子函数。如果子递归返回值不是int最大值，代表该分配方案可行，因此再加上当前人分配到A地的费用即是一种选择方案。
- 将当前人分配到B地，此时，B人数加一，A人数不变，我们将该状态传入递归子函数。如果子递归返回值不是int最大值，代表该分配方案可行，因此再加上当前人分配到B地的费用即是另一种选择方案。
上面两种方案的最小值即是当前递归函数的返回值。
最后再看记忆数组（相当于动态规划使用的dp数组）。由于递归函数存在2个可变参数，因此我们建立一个二维数组即可。
实现代码：
int n; // 总人数
int[][] memo; // 记忆数组
public int twoCitySchedCost(int[][] costs) {
n=costs.length; // 计算总人数
memo=new int[n][n]; // 初始化记忆数组
return help(costs,0,0); // 递归求解
}
// costs：花费数组
// countA：A地人数
// countB：B地人数
// 分配所有尚未分配人所需要的最小花费
int help(int[][] costs, int countA, int countB){
// 如果A或者B地人数大于总人数一半，这是一个不合理分配，返回int最大值
if(countA>n/2||countB>n/2) return Integer.MAX_VALUE;
// 当前待分配人的下标，即已分配完毕总人数
int index=countA+countB;
// 如果当前下标是n，代表所有人已分配完毕
if(index==n) return 0;
// 如果记忆数组中存在当前解，直接返回
if(memo[countA][countB]>0)return memo[countA][countB];
// 将当前人分配到A地，A地人数加一
int costA=help(costs,countA+1,countB);
// 如果该分配返回值不是int最大值，代表这是一种合理分配方案
// costA加上当前人分配到A地的费用
if(costA!=Integer.MAX_VALUE) costA+=costs[index][0];
// 将当前人分配到B地，B地人数加一
int costB=help(costs,countA,countB+1);
// 如果该分配返回值不是int最大值，代表这是一种合理分配方案
// costB加上当前人分配到B地的费用
if(costB!=Integer.MAX_VALUE) costB+=costs[index][1];
// 两种方案的最小值为当前最优解。
int res=Math.min(costA,costB);
// 将最优解存入记忆数组
memo[countA][countB]=res;
return res;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 97.36% of Java online submissions for Two City Scheduling.
Memory Usage: 39 MB, less than 63.89% of Java online submissions for Two City Scheduling.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1029-two-city-scheduling-解题思路分析/