hritikkumar's blog

Can anyone help me with this problem?
By hritikkumar, history, 4 years ago, In English

Problem:

Calculating the number of distinct ways to fill an n × m grid using 1 × 2 and 2 × 1 size tiles. For example, one valid solution for the 4 × 7 grid is and the total number of solutions is 781.

I want to solve this problem through Dynamic Programming. Please help me?

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First thing that popped up: http://www.math.cmu.edu/~bwsulliv/domino-tilings.pdf

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you can't figure out how to look up standard problems on google, you'll never get anywhere, not just in cp, but in life.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    hey SuperJ6 I know the mathematical formula for this problem. But, I want to know that can we solve this problem through Dynamic Programming. You know all solutions are not on google :) that's why I asked.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It is a very well known problem, but to my surprise, it was actually a little hard to find resources on it, particularly if you don't know the name, so ig I was a bit harsh. It is known as broken profile dp, and there are many such problems where you hold the state as a whole row of a grid, and in the case of this problem it's a bitmask holding whether you are going to extend the domino or not. The best tutorial for it sadly seems to be down, but here it is on web archive link.

      → Reply