3. Dynamic Programming with Bitmasking #

Created Tuesday 28 July 2020

Q) We have n people and given n jobs. we are given a matrix in which the time for the nth person in doing n job is written. Now we have to do all the n jobs. Each person can be assigned to one job, and each job can be assigned to one person. We need to do this in the minimum time possible. We solve this using DP and bitmasking. A) Our mask consists of n bits, with the person and the depth of the tree being the job and the person being 1 if doing the job.

• We are having overlapping sub-problems. We can solve this by keeping a count of numbers and heights.