1986. Minimum Number of Work Sessions to Finish the Tasks

Description

Solution

State Compress + DP

firstly compute cost[mask].
dp[mask] = min(dp[subset] + cost[mask ^ subset] <= TimeSession ? 1 : 0)

Code

class Solution {
public:
    int minSessions(vector<int>& tasks, int sessionTime) {
        int n = tasks.size();
        vector<int> dp(1 << n, 15);
        vector<int> cost(1 << n);
        for(int i = 0; i < n; i++){
            for(int mask = 0; mask < (1<<i); mask++){
                cost[mask|(1<<i)] = cost[mask] + tasks[i]; 
            }
        }
        dp[0] = 0;
        //dp[mask] = min(dp[mask ^ i] + dp[i])
        for(int mask = 0; mask < (1 << n); mask++){
            for(int i = mask; i > 0; i = (i-1) & mask){
                if(cost[i] <= sessionTime)
                    dp[mask] = min(dp[mask^i] + 1, dp[mask]);
            }
        }
        return dp[(1<<n)-1];
    }
};