[Python3] Bitmask DP - Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n- We have to try all possible cases to find minimum number of work session -> DP signal
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- We have to try all possible cases to find minimum number of work session -> DP signal.\n- `1 <= n <= 14` the number of tasks is small enough to save all states using a bit number.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Initialization:**\n- n = len(tasks): Calculates the number of tasks.\n\n**2. Dynamic Programming (Top-Down Approach):**\n- `@cache`: This decorator is used to memoize the `dp` function, avoiding redundant calculations.\n- `def dp(task_mask: int, remain_time: int) -> int:` Defines the recursive `dp` function.\n    - if `task_mask == (1 << n) - 1: return 1`: If all tasks have been completed (the bitmask task_mask is full), return 1 as only one more session is needed to complete the remaining tasks.\n    - `res = float("inf")`: Initializes the minimum number of sessions to infinity.\n    - `for i in range(n):`: Iterates through all tasks.\n        - `if task_mask & (1 << i) or tasks[i] > remain_time: continue`: Checks if the task is already completed or if it exceeds the remaining session time. If so, skip it.\n        - `res = min(res, dp(task_mask | (1 << i), remain_time - tasks[i]), dp(task_mask | (1 << i), sessionTime) + 1)`: Recursively calculates the minimum number of sessions by considering two options:\n            - Assigning the current task to the current session: `dp(task_mask | (1 << i)`, remain_time - tasks[i]).\n            - Starting a new session for the current task: `dp(task_mask | (1 << i), sessionTime) + 1`.\n    - `return res`: Returns the minimum number of sessions required to reach the current state.\n\n**3. Main Call:**\n\n- `return dp(0, sessionTime)`: Calls the dp function with initial values of 0 for the current state (no tasks completed) and the initial session time.\n\n**4. Explanation:**\n\n- The `dp` function uses a top-down dynamic programming approach to efficiently calculate the minimum number of sessions.\n- The state of the task completion is represented by the bitmask `task_mask`, and the remaining session time is represented by `remain_time`.\n- The `dp` function recursively explores different combinations of task assignments within sessions, considering the available time and the remaining tasks.\n- The memoization decorator ensures that the `dp` function avoids recalculating results for the same state, improving efficiency.\n- The final result is the minimum number of sessions required to complete all tasks.\n\n# Complexity\n- Time complexity: $$O(2 ^ N * S * N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(2 ^ N * S)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n        n = len(tasks)\n        @cache\n        def dp(task_mask: int, remain_time: int) -> int:\n            if task_mask == (1 << n) - 1: return 1\n            res = float("inf")\n            for i in range(n):\n                if task_mask & (1 << i) or tasks[i] > remain_time: continue\n                res = min(res, \n                          dp(task_mask | (1 << i), remain_time - tasks[i]), \n                          dp(task_mask | (1 << i), sessionTime) + 1)\n            return res\n        return dp(0, sessionTime))\n```
['Array', 'Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'Python3']