Leetcode June Challenge - Day 3

Problem: LeetCode June Challenge - Day 3

Ideas:

  1. 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);
    }
};