### 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?

Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).Auto comment: topic has been updated by hritikkumar (previous revision, new revision, compare).Errichto , I am looking for your reply. Please help me!

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

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

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.

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.

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.

Thanks SuperJ6 :)