Knapsack-like | 0 ms | O(s*n^2) Worst Case
Step 1: Build DP Matrix\n\nBuild a knapsack-like matrix to find how many ways we can spend X time with our current tasks.\n\nEx. [1,2,3]    sessionTime = 3\n\n0
**Step 1: Build DP Matrix**\n\nBuild a knapsack-like matrix to find how many ways we can spend X time with our current tasks.\n\nEx. [1,2,3]    sessionTime = 3\n\n**0 1 2 3** \n1 0 0 0  |  *looking at 0 tasks*\n1 1 0 0  |  *including task 1*\n1 1 1 1  |  *including task 2*\n1 1 1 2  |  *including task 3*\n\n#Ways to spend s time with tasks 0->t =\n#Ways to spend s time with tasks 0->(t-1) +\n#Ways to spend s-(time of task t) time with tasks 0->(t-1).\n\n**Step 2: Extrapolate Tasks from Matrix**\n\nLook for the bottom-right-most, non-zero cell in our matrix (in this case [3,3]).\nFind the task that caused this cell to increase to its current value (task #3).\nAdd that task to the list of used tasks and decrease our column idx by that task\'s value.\n\n**Step 3: Remove Tasks, Increment Sessions, Repeat**\n\n[1,2,3] becomes [1,2]. Sessions = 1\nOur matrix becomes\n\n1 0 0 0   |  *looking at 0 tasks*\n1 1 0 0   |  *including task 1*\n1 1 1 1   |  *including task 2*\n\nWe can extrapolate tasks 2 & 1 from this.\n\n[1,2] becomes []. Sessions = 2\n\n**Time Complexity**\n\nEach iteration has a complexity of O(sn), where s is sessionTime and n is the number of tasks.\nWorst case scenario, each session only includes one task, giving worst case O(s*n^2)\n\n```\nclass Solution {\npublic:\n    int minSessions(vector<int>& tasks, int sessionTime) {\n        int sessions = 0;\n        \n        while (!tasks.empty()) {\n\t\t\t// Create dp matrix.\n            vector<vector<int>> dp (tasks.size()+1, vector<int> (sessionTime+1, 0));\n            \n            for (auto& row : dp)\n                row[0] = 1;\n            \n            for (int t=1; t<dp.size(); t++) {\n                for (int s=1; s<dp[0].size(); s++) {\n                    int curTask = tasks[t-1];\n                    \n\t\t\t\t\tdp[t][s] = dp[t-1][s];\n\t\t\t\t\t\n\t\t\t\t\tif (curTask <= s)\n                        dp[t][s] += dp[t-1][s-curTask];\n                }\n            }\n            \n\t\t\t// Build idx list from dp matrix.\n            int row = dp.size()-1;\n            int col = dp[0].size()-1;\n            vector<int> indices;\n            \n            while (col>0 && row>0) {\n                while (col > 0 && dp[row][col] == 0)\n                    col--;\n                \n                while (row > 0 && dp[row][col] == dp[row-1][col])\n                    row--;\n                \n                if (col==0 && row==0)\n                    continue;\n                \n                indices.push_back(row-1);\n                col -= tasks[row-1];\n                row--;\n            }\n\t\t\t\n\t\t\t// Remove used tasks.\n            for (auto idx : indices)\n                tasks.erase(tasks.begin() + idx);\n            \n            sessions++;\n        }\n        \n        return sessions;\n    }\n};\n```\n
['C', 'C++']