2403. Minimum Time to Kill All Monsters

You are given an integer array power where power[i] is the power of the ith monster.

You start with 0 mana points, and each day you increase your mana points by gain where gain initially is equal to 1.

Each day, after gaining gain mana, you can defeat a monster if your mana points are greater than or equal to the power of that monster. When you defeat a monster:

• your mana points will be reset to 0, and
• the value of gain increases by 1.

Return the minimum number of days needed to defeat all the monsters.

class Solution {
    long long dp[1<<18];
    long long helper(vector<vector<int>>& cost, int day, int mask) {
        if(day == cost.size()) return 0;
        if(dp[mask] != -1) return dp[mask];
        long long& res = dp[mask] = LLONG_MAX;
        for(int i = 0; i < cost.size(); i++) {
            if(mask & (1<<i)) continue;
            res = min(res, cost[day][i] + helper(cost,day + 1, mask | (1<<i)));
        }
        return res;
    }
public:
    long long minimumTime(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> cost(n, vector<int>(n));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cost[i][j] = (A[j] + i) / (i + 1);
            }
        }
        memset(dp, -1, sizeof dp);
        return helper(cost, 0, 0);
    }
};