Two City Scheduling: A Dynamic Programming Solution

We have 2N people. We need to split them evenly between cities A and B. Each person has different costs for going to each city. What’s the minimum total cost?

This is a DP and brute force search problem.

Each person can go to either A or B. Start with zero cost.

At each step, we can choose to assign the current person to A or B based on all previous cases.

The 2D DP model captures both decisions. Cases with lower costs survive during enumeration.

State transitions move right or down-right. Each horizontal move advances one column. Overlapping parts take the minimum value.

This works well for brute force memoized search with multiple limited choices.

Constraint: Exactly N people must choose A, and N people must choose B.

Solution: We can define moving down-right as assigning to B. Then we just need the result at [2N][N].

int twoCitySchedCost(vector<vector<int>>& costs) {
    memset(dp, 0x3F, sizeof dp);
    dp[0][0]=0;

    int n=costs.size();

    for(int i=0;i<n;++i) {
        for(int j=0;j<=i;++j) {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]+costs[i][0]);
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+costs[i][1]);
        }
    }
    return dp[n][n>>1];
}

int dp[102][102];

#typical #search #DP