X

LEETCODE 1029. Two City Scheduling 解题思路分析

题目大意:

两地调度

公司计划面试 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。除了上述特殊情况外,我们在当前递归中有两种选择:

  1. 将当前人分配到A地,此时,A人数加一,B人数不变,我们将该状态传入递归子函数。如果子递归返回值不是int最大值,代表该分配方案可行,因此再加上当前人分配到A地的费用即是一种选择方案。
  2. 将当前人分配到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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1029-two-city-scheduling-解题思路分析/
Categories: leetcode
kwantong: