### Leetcode June Challenge - Day 3

**Problem:** LeetCode June Challenge - Day 3

**Ideas:**

Again a very simple problem, you need to pick n people for each city, so for every person we have:

- Send him to city A, so you need to pick one less person for city A and add the cost.
- Send him to city B, so you need to pick one less person for city B and add the cost.

This is a standard DP problem, solved using recursion.

**Solution**:

```
#define MAXN 51
#define INF (int)1e8
int dp[MAXN*2][MAXN][MAXN];
class Solution {
int solve(int person, int a, int b, vector<vector<int>>& c){
if(person < -1 || a < 0 || b < 0) return INF;
if(person == -1) return 0;
if(dp[person][a][b] != -1) return dp[person][a][b];
return (dp[person][a][b] = min(solve(person-1,a-1,b,c) + c[person][0],
solve(person-1,a,b-1,c) + c[person][1]));
}
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
int n = costs.size()/2;
memset(dp, -1, sizeof(dp));
return solve(2*n-1, n, n, costs);
}
};
```