leetcode2305. Fair distribution of biscuits (medium, weekly, shaped pressure DP)

Train of thought ： violence dfs, The time complexity is O(n^n), The time complexity is a little high .

Train of thought two ： subset division + The number of subsets is limited -> Pressure dp Time complexity O(n * 3^n) Is constant
Pressure dp Related knowledge ：

//  Traverse u All nonempty subsets of 
for (int s = u; s; s = (s - 1) & u) {
    
  //s Express u A subset of  u^s Means to remove s A subset of the latter 
}

Specific ideas ：
dp[i][j] Indicates that the number of sets consumed is i, The selected cookies are j The minimum value of the maximum total number of cookies obtained .
i The values for 1->k j The values for 1->(1<<n)
dp[i][j]=min(max(dp[i-1][j^s], sum[s]));

class Solution {
    
public:
    int distributeCookies(vector<int>& cookies, int k) {
    
 
        int n = cookies.size();
        vector<int> sum(1 << n);
        for (int i = 1; i < (1 << n); ++i) {
    
            for (int j = 0; j < n; ++j) {
    
                if (i & (1 << j)) sum[i] += cookies[j];
            }
        }
        vector<vector<int>> dp(k, vector<int>(1 << n));
        //dp[0] It means consumption 1 Group , The value obtained 
        dp[0] = sum;
        for (int i = 1; i < k; ++i) {
    
            for (int j = 1; j < (1 << n); ++j) {
    
                dp[i][j] = INT_MAX;
                for (int s = j; s; s = (s - 1) & j) {
    
                    dp[i][j] = min(dp[i][j], max(dp[i - 1][j ^ s], sum[s]));
                }
            }
        }
        return dp[k - 1][(1 << n) - 1];
    }
};