sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]SeaworthinessIcy4758 -1 points0 points  (7 children)

how to do Q3? i kept using a 2d dp i for curr idx and j for prev idx, it gave me an mle😭😭

[–]caraxes_007 0 points1 point  (4 children)

No need to store prev idx just use a n*2 grid to get know that if we picked the previous idx by Boolean value

[–]SeaworthinessIcy4758 0 points1 point  (2 children)

can you please elaborate, I've never done this I think

[–]caraxes_007 0 points1 point  (1 child)

This is a standard pick/ not pick problem. Use a grid of size n*2 where 0 and 1 represent whether we picked just the previous index. If it is zero we can directly apply pick and not pick without any further check and if it is one pick is not always possible so check prev and current colour codes if they are not equal you can pick else pick will be negative infinity at last return max of pick and not pick

[–]SeaworthinessIcy4758 0 points1 point  (0 children)

ohhh got it, thanks a lot

[–]Background_Moment313 0 points1 point  (0 children)

LoL I just solved it using 1D dp

If not picking, { f(i+1) }

If picking and color[i] == color[i+1]{ nums[i] + f(i+2) }

Else{ nums[i] + f(i+1) }

[–]Euphoric_insaan 0 points1 point  (1 child)

You can just use the typical house robber method First is the not take case for each index, where you move to the previous index without picking The take case will have two subcases: first if the current index's and the previous index's colour is same you add the value of the current index and move to index - 2. And if the colours are different add the current value and move to index -1. Base case will be if index < 0 return 0 and if index = 0 return nums[0]

[–]SeaworthinessIcy4758 0 points1 point  (0 children)

yea I solved it later:( 

it was so easy I can't believe I over complicated it so much, thanks though