Where it runs
1. The problem
A build farm (a group of servers that build code) has n machines and n jobs. Each machine runs each job at its own speed, so cost[i][t] is the estimated minutes for machine i to run job t. You want to hand out the jobs so every machine gets exactly one and the total minutes are as low as possible.
Trying every arrangement means n! options, and n! grows very fast: at n = 12 it is already 479,001,600. The greedy shortcut fails too: "each machine in turn takes the fastest free job". Take cost = [[1, 2], [1, 9]]. Machine 0 takes job 0 for 1 minute, machine 1 is left with job 1 for 9 minutes, total 10. If machine 0 takes job 1 instead (2 minutes), machine 1 takes job 0 (1 minute), total 3. The cheap early pick forced an expensive late one.
What saves you is that n is small here: machines in a rack, maybe a dozen. When there are few elements, you can store the answer to "which jobs are already taken" compactly.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- best/maximum/minimum ending at position i
- ways to reach, climb, or tile
- cannot pick two adjacent items
- minimum cost path through a grid
- overlapping subproblems, same state recomputed
Looks similar, isn't
- Recursion with memoization
Memoisation fills the same table from the top, on demand. This fills it upward in a fixed order.
- Greedy (exchange argument)
Greedy commits to one choice per step. DP keeps every option until the end.
- Recursion
The recursion tells you what the transition is. The table is what makes it fast.
- DP on subsequences (LIS / LCS / edit distance)
There the state is a pair of positions in two sequences. Here one index is enough.
n states with O(1) work each gives O(n). Memory drops to O(1) when only the last states matter.
On LeetCode
Assignment and visiting problems on up to about 15 items, where the state is which items are already used. dp[mask] stores the best answer for that set, and the number of 1 bits in mask says whose turn is next.
The lesson task with a maximum. Students are the workers, mentors are the tasks, and the score is the number of matching answers.
Each number of nums1 takes a different number of nums2 and the cost is their XOR, so this is the lesson task with n up to 14.
dp[mask] counts the arrangements of the numbers in mask. The next position is the bit count of mask plus 1, and it must divide the next number or be divided by it.
dp[mask] keeps how full the current bucket is after the numbers in mask, and a number fits only if it does not overflow the bucket.
The state is a node plus the mask of visited nodes, and a BFS over these pairs finds the shortest walk through all of them.