Python Top-Down DP and Thinking Process
Inspired by this top voted post:\nhttps://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/discuss/1432155/Easier-than-top-voted-ones-o
Inspired by this top voted post:\nhttps://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/discuss/1432155/Easier-than-top-voted-ones-or-LegitClickbait-or-c%2B%2B\nWhich has a great explanation of how does bit masks works for this problem.\n\nThe brutal recursive solution is finding all possible combinations. We take every un-taken task and pass it to the next level recursive call for any given list. There are two possibilities when we made the recursive call:\n1) Keep in the current working session\n2) Start a new working session\n\nAnd if all tasks are done, we return 1\n\n```\ndef recur_f(c_session_time, c_tasks):\n            \n            if(c_session_time > sessionTime):\n                return math.inf\n            \n            if(sum(c_tasks) == len(c_tasks)*-1):\n                return 1\n            \n            result = math.inf\n            for i in range(0, len(c_tasks)):\n                if(c_tasks[i] != -1):\n\t\t\t\t\t#avoid calling by reference so we made an copy of the current task list\n                    n_tasks = c_tasks.copy()\n                    n_tasks[i] = -1\n                    result = min(result, \n\t\t\t\t\tmin(\n\t\t\t\t\t\t#keep the current working session\n\t\t\t\t\t\trecur_f(c_session_time + tasks[i], n_tasks),\n\t\t\t\t\t\t#start a new working session\n\t\t\t\t\t\t1+recur_f(tasks[i], n_tasks)))  \n\t\t\t\t\t\n            return result\n        \n        return recur_f(0, tasks)\n```\n\nBut this will get TLE. So we need to optimize it by \n1) Using the bit string to represent the task status instead of using a list\n2) Using memorization (Top-Down DP)\n\nPlease check https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/discuss/1432155/Easier-than-top-voted-ones-or-LegitClickbait-or-c%2B%2B for explanation for bit mask. \n\nBasically we use a binary representation of a integer, which is a bit string to represent the tasks status. E.g. 11111 means all five tasks are processed.\n\nAnd tasks | (1<<i) means set ith task as one, tasks & (1<<i) means check whether ith task is 1.\n\nSo we modified our brutal force recursive solution, and used an array with **current tasks bit string and current session time** as the variables. \n\nQuestions: Is anyone came up with a bottom-up version DP for this problem? \n\n```\nclass Solution:\n    result = math.inf\n    n_tasks = 0\n    all_ones = 0\n    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n\n        num_possible_schedule = (1 << 15)\n        self.n_tasks = len(tasks)\n        self.all_ones = (1<<self.n_tasks)-1\n       \n        def recur_f(c_session_time, c_tasks, dp_array):\n\n            if(c_session_time > sessionTime):\n                return math.inf\n            \n            if(c_tasks == self.all_ones):\n                dp_array[c_tasks][c_session_time] = 1\n                return 1\n            \n            if(dp_array[c_tasks][c_session_time] != -1):\n                return dp_array[c_tasks][c_session_time]\n            \n            result = math.inf\n            for i in range(0, self.n_tasks):\n                if(c_tasks & (1<<i) == 0):\n                    \n                    n_tasks = c_tasks | (1<<i)\n                    \n                    result = min(result, \n                                 min(recur_f(c_session_time + tasks[i], n_tasks, dp_array),1+recur_f(tasks[i], n_tasks, dp_array)))                                \n                                \n            dp_array[c_tasks][c_session_time] = result\n            return result\n\n        dp_array = [[-1 for i in range(0, 16)] for j in range(0, num_possible_schedule)]\n\n        return recur_f(0, 0, dp_array)\n```
[]