3376. Minimum Time to Break Locks I

Bob is stuck in a dungeon and must break n locks, each requiring some amount of energy to break. The required energy for each lock is stored in an array called strength where strength[i] indicates the energy needed to break the ith lock.

To break a lock, Bob uses a sword with the following characteristics:

• The initial energy of the sword is 0.
• The initial factor X by which the energy of the sword increases is 1.
• Every minute, the energy of the sword increases by the current factor X.
• To break the ith lock, the energy of the sword must reach at least strength[i].
• After breaking a lock, the energy of the sword resets to 0, and the factor X increases by a given value K.

Your task is to determine the minimum time in minutes required for Bob to break all n locks and escape the dungeon.

Return the minimum time required for Bob to break all n locks.

class Solution {
    int dp[1<<8];
    bool bit(int bit, int x) {
        return (bit>>x) & 1;
    }
    int helper(vector<int>& A, int mask, int cost, int k) {
        if(dp[mask] != -1) return dp[mask];
        int& res = dp[mask] = INT_MAX;
        for(int i = 0; i < A.size(); i++) {
            if(bit(mask,i)) continue;
            res = min(res, helper(A,mask | 1<<i, cost + k, k) + (A[i] + cost - 1) / cost);
        }
        return res;
    }
public:
    int findMinimumTime(vector<int>& strength, int K) {
        memset(dp, -1, sizeof dp);
        dp[(1<<strength.size()) - 1] = 0;
        return helper(strength, 0, 1, K);
    }
};