Leetcode 1986. Minimum Number of Work Sessions to Finish the Tasks

[Woodyiiiiiii]

Bitmask + up-bottom dfs

讲解：

• [C++/Java/Python] From Straightforward to Optimized Bitmask DP - O(2^n * n) - Clean & Concise

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        Integer[][] dp = new Integer[1 << n][sessionTime];
        return dfs(tasks, n, dp, (1 << n) - 1, 0, sessionTime);
    }

    private int dfs(int[] tasks, int n, Integer[][] dp, int mask, int remainTime, final int sessionTime) {
        if (mask == 0) {
            return 0;
        }
        if (dp[mask][remainTime] != null) {
            return dp[mask][remainTime];
        }
        int ans = n;
        for (int i = 0; i < n; ++i) {
            if ((mask & (1 << i)) == 0) {
                continue;
            }
            int newMask = mask ^ (1 << i);
            if (tasks[i] <= remainTime) {
                ans = Math.min(ans, dfs(tasks, n, dp, newMask, remainTime - tasks[i], sessionTime));
            } else {
                ans = Math.min(ans, 1 + dfs(tasks, n, dp, newMask, sessionTime - tasks[i], sessionTime));
            }
        }
        return dp[mask][remainTime] = ans;
    }

}

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        Pair[] dp = new Pair[1 << n];
        return dfs(tasks, n, dp, (1 << n) - 1, sessionTime).getKey();
    }

    private Pair dfs(int[] tasks, int n, Pair[] dp, int mask, final int sessionTime) {
        if (mask == 0) {
            return new Pair(0, 0);
        }
        if (dp[mask] != null) {
            return dp[mask];
        }
        int ans = n, remain = 0;
        for (int i = 0; i < n; ++i) {
            if ((mask & (1 << i)) == 0) {
                continue;
            }
            int newMask = mask ^ (1 << i);
            Pair p = dfs(tasks, n, dp, newMask, sessionTime);
            int sessionCnt = p.getKey(), remainTime = p.getValue();
            if (tasks[i] > remainTime) {
                sessionCnt++;
                remainTime = sessionTime - tasks[i];
            } else {
                remainTime -= tasks[i];
            }
            if (sessionCnt < ans || (sessionCnt == ans && remainTime > remain)) {
                ans = sessionCnt;
                remain = remainTime;
            }
        }
        return dp[mask]= new Pair(ans, remain);
    }

    static class Pair {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        int getKey() {
            return x;
        }
        int getValue() {
            return y;
        }
    }

}

---

• 1986. Minimum Number of Work Sessions to Finish the Tasks