class Solution {
public int minimumTimeRequired(int[] jobs, int k) {
int n = jobs.length;
int[][] dp = new int[k + 1][1 << n];
// dp[i][j], i persons, they do the job as the state
// of j, the minimum time
// initialization
// ask the person do all the jobs
for (int mask = 0; mask < (1 << n); mask++) {
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) == 0) continue;
int left = mask - (1 << j);
dp[1][mask] = dp[1][left] + jobs[j];
}
}
// when we have more than 1 person
for (int i = 2; i <= k; i++) {
// 1101
// 1000
for (int mask = 1; mask < (1 << n); mask++) {
int min = Integer.MAX_VALUE;
for (int subMask = mask; subMask != 0; subMask = (subMask - 1) & mask) {
min = Math.min(min, Math.max(dp[1][subMask], dp[i - 1][mask - subMask]));
}
dp[i][mask] = min;
}
}
return dp[k][(1 << n) - 1];
}
}