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 <= costs.length <= 100
- It is guaranteed that
costs.length
is even. 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 ] ; } };
No comments:
Post a Comment