Leetcode Problem 1349. Maximum Students Taking Exam

1349. Maximum Students Taking Exam

Leetcode Solutions

Dynamic Programming with Bitmasking

  1. Initialize a DP array dp with dimensions (m+1) x (1<<n) filled with -1, where m is the number of rows and n is the number of columns in the seats matrix.
  2. Set dp[0][0] to 0 as the base case.
  3. Iterate over each row i from 1 to m.
  4. For each row, iterate over all possible mask states (from 0 to (1<<n) - 1).
  5. If the mask is a subset of the valid seats in the current row and there are no adjacent students, proceed to the next step. Otherwise, continue to the next mask.
  6. For each valid mask, iterate over all possible previous row states prev_mask.
  7. If prev_mask is valid and there are no students in the upper left or upper right positions that can lead to cheating, update dp[i][mask].
  8. The result is the maximum value in the last row of the dp array.
UML Thumbnail

Backtracking with Pruning

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...