# 1986. Minimum Number of Work Sessions to Finish the Tasks
###### tags: `Leetcode` `Medium` `DFS+Memorization`
Link: https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/
## 思路
重点复习！
### dp+backtracking
如果直接用backtracking会TLE
参考[这里](https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/discuss/1436811/C%2B%2BJavaPython-From-Straightforward-to-Optimized-Bitmask-DP-O(2n-*-n)-Clean-and-Concise)
Let ```dp(mask, remainTime)``` is the minimum of work sessions needed to finish all the tasks represent by mask (where $i$-th bit = 1 means ```tasks[i]``` need to proceed) with the remainTime we have for the current session.
We use mask as ```111...1111```, represent we need to process all n tasks.
We pass ```remainTime = 0```, which means there is no remain time for the current session; ask them to create a new session.
可以理解成从11111...111,0建tree tree的root是没有任何task所以dp返回0
### dp
状态压缩
dp[state]表示当mask为i时最少需要几个session
state是一个最大值是```1<<n```的mask 表示当下有几个task已经做了
dp[state]如果对应着多个session，那么它必然可以“拆分”成两个任务集subset与state-subset，然后对各自所需的session数目进行相加。所以我们需要遍历state的所有subset，找到最优的一种拆分。即dp[state]=min{dp[subset]+dp[state-subset]}。注意，上述的枚举子集的框架，所需要的时间复杂度是$o(3^n)$而不是$o(2^n)$

初始值：对于一些特定的任务组合state，如果总时间小于sessionTime，那么他们的dp[state]就是1. 其余的dp[state]我们都设置为无穷大。这需要花费2^n的时间预处理遍历所有的组合。。

利用枚举子集的模板：

for (int state=1; state<(1<<n); state++){ 
    for (int subset=state; subset>0; subset=(subset-1)&state){
        dp[state] = DoSomething(dp[subset]);
    }
}

## Code
### dp+backtracking

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        Integer[][] dp = new Integer[1<<tasks.length][sessionTime];
        return backtracking(dp, tasks, sessionTime, (1<<tasks.length)-1, 0);
    }
    private int backtracking(Integer[][] dp, int[] tasks, int sessionTime, int mask, int remain){
        if(mask==0) return 0;
        if(dp[mask][remain]!=null) return dp[mask][remain];
        int ans = tasks.length;
        for(int i=0;i<tasks.length;i++){
            if(((mask>>i)&1)==1){
                int newMask = ~(1<<i)&mask;
                if(tasks[i]<=remain){
                    ans = Math.min(ans, backtracking(dp, tasks, sessionTime, newMask, remain-tasks[i]));
                }
                else{
                    ans = Math.min(ans, backtracking(dp, tasks, sessionTime, newMask, sessionTime-tasks[i])+1);
                }
            }
        }
        return dp[mask][remain]=ans;
    }
}

### dp

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        int[] dp = new int[1<<n];
        Arrays.fill(dp, Integer.MAX_VALUE/2);
        for(int state=1; state<(1<<n); state++){
            int sum=0;
            for(int i=0; i<n; i++){
                if(((state>>i)&1)==1){
                    sum += tasks[i];
                }
            }
            if(sum<=sessionTime) dp[state]=1;
        }
        dp[0]=0;
        for(int state=1; state<(1<<n); state++){
            for(int substate=state; substate>=1; substate=(substate-1)&state){
                dp[state] = Math.min(dp[state], dp[substate]+dp[state-substate]);
            }
        }
        return dp[(1<<n)-1];
    }
}