[C++/Java/Python] From Straightforward to Optimized Bitmask DP - O(2^n * n) - Clean & Concise
\u2714\uFE0F Solution 1: Straightforward Bitmask DP\n- Let dp(mask, remainTime) is the minimum of work sessions needed to finish all the tasks represent by mask
**\u2714\uFE0F Solution 1: Straightforward Bitmask DP**\n- 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.\n- Then `dp((1 << n) - 1, 0)` is our result\n\t- We use `mask` as `111...1111`, represent we need to process all `n` tasks.\n\t- We pass `remainTime = 0`, which means there is no remain time for the current session; ask them to create a new session.\n\n<iframe src="https://leetcode.com/playground/CQvMZRS9/shared" frameBorder="0" width="100%" height="530"></iframe>\n\nComplexity:\n- Time: `O(2^n * sessionTime * n)`, where `n <= 14` is length of tasks, `sessionTime <= 15`.\n   Explain: There is total `2^n * sessionTime` dp states, they are `dp[0][0], dp[1][0]..., dp[2^n-1][remainTime]`. Each dp state needs an inner loop `O(n)` to calculate the result. \n- Space: `O(2^n * sessionTime)`\n\n---\n\n**\u2714\uFE0F Solution 2: Bitmask DP - Optimized (Independence with SessionTime)**\n- Let `dp(mask)` return `(the minimum of work sessions needed, remainTime)` to finish all the tasks represent by `mask` (where `i`th bit = 1 means tasks[i] need to proceed).\n- Then `dp((1 << n) - 1)[0]` is our result\n\t- We use `mask` as `111...1111`, represent we need to process all `n` tasks.\n\n<iframe src="https://leetcode.com/playground/MkXWVVw2/shared" frameBorder="0" width="100%" height="640"></iframe>\n\nComplexity:\n- Time: `O(2^n * n)`, where `n <= 14` is length of tasks.\n   Explain: There is total `2^n` dp states, they are `dp[0], dp[1]..., dp[2^n-1]`. Each dp state needs an inner loop `O(n)` to calculate the result.\n- Space: `O(2^n)`\n\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]