Java | Space O(2^n) | Bottom-Up 1D DP
Saw a lot of the posts on the front most-upvoted page with 2D dp with space complexity O(2^n * W). It\'s unnecssary. We can do it in O(2^n) space.\nBecause, for
Saw a lot of the posts on the front most-upvoted page with 2D dp with space complexity `O(2^n * W)`. It\'s unnecssary. We can do it in `O(2^n)` space.\nBecause, for a given subset of tasks, there is only 1 optimal way - the minimum number of bin required and then followed by the minimum weight.\nThere is no reason to try all the possible weights for the current bin subset. Try the best one will guarantee the optimal solution.\n\nFor example, bin `(0b101)` has a weight of `1`, and in another possibliity, bin `(0b101)`has a weight of 5. It is always more optimal to take the bin with weight of 1 and ignore the one with a weight of 5.\n\n#### Java\n```Java\n// Time Complexity O(2^n * n)\n// Space O(2^n)\nclass Solution {\n    public int minSessions(int[] tasks, int sessionTime) {\n        int n = tasks.length;\n        int[] dp = new int[1<<n]; \n        int[] w = new int[1<<n]; // best (min) weight for the current subset i\n        Arrays.fill(dp, 100);\n        Arrays.fill(w, 1000);\n        dp[0]=0;\n        for (int i = 1; i < 1<<n; i++){\n            for (int j = 0; j < n; j++){\n                if ((i & 1 << j) > 0){\n                    int extra = 0, wh = w[i^1<<j]+tasks[j];\n                    if (wh > sessionTime){ // need another bin\n                        extra = 1;\n                        wh=tasks[j];\n                    }\n                    dp[i] = Math.min(dp[i], dp[i^1<<j]+extra);\n                    if (dp[i^1<<j]+extra==dp[i]){ // update weight to min\n                        w[i]=Math.min(wh, w[i]);\n                    }\n                }\n            }\n        }\n        return dp[(1<<n)-1];\n    }\n}\n```
['Dynamic Programming', 'Bitmask', 'Java']