hritikkumar's blog

By hritikkumar, history, 12 months 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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).

»
12 months ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

Errichto , I am looking for your reply. Please help me!

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks wet_water, I already checked that resource. I want to know that is there any DP solution for this problem.

»
12 months 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.

  • »
    »
    12 months 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.

    • »
      »
      »
      12 months 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.