Link to home
Start Free TrialLog in
Avatar of crimsonfrog

asked on

Dynamic Programming - Tiling

Here's the problem I'm having trouble understanding (I couldn't find a way to format it in plain text):

User generated image

I'm hoping someone can walk me through this and explain it to me like I'm 5, because I'm really having a lot of trouble in this class.

Thanks in advance
Avatar of ozo
Flag of United States of America image

Are you asking for an explanation of the meaning of the problem means, or of the solution of the problem?
Avatar of crimsonfrog


An explanation of the solution of the problem
For a dynamic programming solution, I'd suggest building a table to record whether a solution exists for the first x bits of t, using the first y tiles in s.
I'm sorry, I still don't understand. Can you perhaps give me an example?
Do you know what Dynamic Programming is?
Basically breaking down a problem into simpler problems, correct? And I understand that the solution to the simpler problems is commonly stored, or memoized so it can be looked-up later on
So one way to break down this problem into simpler problems could be  to solve it for a shorter t and a shorter list of tiles.
Okay, that makes sense. But what do I do from there?

Also, does the notation {0,1} mean t can only be 0 or 1, or that it's between 0 and 1?
Avatar of arober11
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial