Tushar’s Birthday Party

• Time : $O(max(A_i) * |B| + |A|)$
• Space : $O(max(A_i))$

c++

int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
    vector<long long> dp(1010, INT_MAX);
    dp[0] = 0;
    for(int i = 0; i < B.size(); i++) {
        int cap = B[i], cost = C[i];
        for(int j = cap; j < dp.size(); j++) {
            dp[j] = min(dp[j], dp[j-cap] + cost);
        }
    }
    int res = 0;
    for(int i = 0; i < A.size(); i++) res += dp[A[i]];
    return res;
}