CODEWITHSUNDEEP
algorithmoptimizationdynamic-programmingcombinatorics
dark_energy
dark_energy

Reputation: 37

How to implement dp?

I recently have encountered a question where I have been given two types of person: Left-handed and Right-handed (writing style). They all are to be seated in a class row and to avoid any disturbance their hands must not collide i.e. pattern may be like LR or LL or RR.
I tried using recursion (taking two branches of L and R for every seat) but number of computations would be very high even for a row size of 100. Somehow I need to implement DP to reduce the computations. Please suggest.

EDIT:
Actually there is a matrix (like a classroom) in which three types (L R B) of people can be seated with no collisions of hand. I have to generate the maximum number of people that can be seated. Suppose I have a 2x2 matrix and to fill it with Left, Right and Both handed type of persons L=0, R=1 ,B =3 are given. So one valid arrangement would be Row0: B R and row1: B - where - means blank seat.

Upvotes: 1

Views: 223

Answers (1)

Saeid
Saeid

Reputation: 4265

Actually the fact that you have a matrix doesn't make a difference in the solution you can transform it to an array without losing generality because each state depends on its left or right not its up and down. A bottom-up approach: In each state you have three things L, B and R , index of the seat you want to fill and its left person. Now we can fill the table from right to left. The answer is dp[inedx=0][L][B][R][left_person=' '].

recursive [index][L][B][R][left_person] :
  if left_person = ' ' or 'L':
    LVal = recursive[index+1][L-1][B][R]['L']
  if left_person = ' ' or 'L' or 'R'
    RVal = recursive[index+1][L][B][R-1]['R']
  if left_person = ' ' or 'L':
    BVal = recursive[index+1][L][B-1][R]['B']
  NVal = recursive[index+1][L][B][R][' ']
  max(LVal, RVal, BVal, NVal) -> dp[index][L][B][R][left_person]

Of course this is not complete and I'm just giving you the genereal idea. You should add some details like the base case and checking if there is anymore person of that kind before assigning it and some other details.

Upvotes: 1

Related Questions