1029. Two City Scheduling -------------E !!!!!!!!!

Q:

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

 

Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

 

Note:

1. 1 <= costs.length <= 100
2. It is guaranteed that costs.length is even.
3. 1 <= costs[i][0], costs[i][1] <= 1000

A:

------------------下面这个会LTE --------（一开始这么写，是因为costs.length < 100 ------

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int N = costs.size()/2;
        return helper(costs, 0, N, N);
    }
private:
    int helper(vector<vector<int>>& costs, int index, int left, int right){
        int a = INT_MAX, b = INT_MAX;
        if(left == 0 && right ==0)
            return 0;
        if(left>=1){
            a = costs[index][0] + helper(costs, index+1, left-1, right);
        }
        if(right>=1){
            b = costs[index][1] + helper(costs, index+1, left, right-1);
        }        
        return min(a,b);
    }
};

----------------  DFS+Cache -----------------

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int N = costs.size()/2;
        vector<vector<int>> V(N+1, vector<int>(N+1,-1));
        V[0][0] = 0;
        return helper(costs, N, N, V);
    }
private:
    int helper(vector<vector<int>>& costs, int left, int right, vector<vector<int>> & V ){
        int N2 = costs.size();
        int a = INT_MAX, b = INT_MAX;
        if(V[left][right] >=0)
            return V[left][right];
        
        if(left>=1)
            a = costs[N2-left-right][0] + helper(costs, left-1, right, V);
        
        if(right>=1)
            b = costs[N2-left-right][1] + helper(costs, left, right-1, V);
        
        V[left][right ] = min(a,b);
        return V[left][right ] ;
    }
};