This recently came up in a Microsoft loop. You're on a game show where there are a set of boxes laid out in front of you. Each box has a score associated with it. If you select a box, a trap door opens up and the boxes on either side fall through. Your goal is to determine the maximum score you can obtain by selecting from the boxes laid out. Which LC question is this referring? #engineering #software #swe #microsoft #leetcode
sounds like graph colouring , maximize sum
That's just a variation on the house robber problem https://leetcode.com/problems/house-robber/
Not even a variant, really. The condition here is the same: "can't use two values in a row"
2D or 1D arrangement?
Lets say there are 10 boxes. If I select box 5 then 4 and 6 fall through. Now what happens if I select box 7? Would only box 8 fall through(since 6 was already no longer available) or would boxes 5 and 8 fall through? If its the first case then its similar to house robber(medium) or else its similar to burst balloons(hard).
House robber
Dynamic Programming
It’s dynamic programming max sum without adjacent or something similar Edit: house robber is what I was thinking
Yup house robber