LeetCode 1029. Two City Scheduling

[Woodyiiiiiii]

重新做了一遍。

首先一步步推理，要找到最小的分成两半的花费。那么其实每步到一个人的时候可以选择选择让他去A或者去B，那么每步其实类似最后一个2^n的递归选择，那就可以继续优化成DP。

接下来考虑如何设置缓存，考虑到这是类似一个背包问题。设置二维数组dp[n][n]，dp[i][j]表示i个人去A和j个人去B的最小花费，答案就是dp[n][n]。那么每一步就是从后往前求解最小花费。

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        for (int[] cost : costs) {
            for (int i = n; i >= 0; --i) {
                for (int j = n; j >= 0; --j) {
                    if (i - 1 >= 0 && dp[i - 1][j] != Integer.MAX_VALUE) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + cost[0]);
                    }
                    if (j - 1 >= 0 && dp[i][j - 1] != Integer.MAX_VALUE) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + cost[1]);
                    }
                }
            }
        }
        return dp[n][n];
    }
}

这道题才是周赛第二题，难度不高。可以从贪心方面考虑，假如全部送去A，需要total花费(这是恒定的)，那么怎么选择一半送去B使得最后的total最小呢？那就选择一半的人中去B花费最小的。这样total会整体最小。

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        Arrays.sort(costs, Comparator.comparingInt(o -> (o[1] - o[0])));
        int ans = 0;
        for (int[] cost : costs) {
            ans += cost[0];
        }
        for (int i = 0; i < n; ++i) {
            ans += costs[i][1] - costs[i][0];
        }
        return ans;
    }
}

---

• 1029. Two City Scheduling