| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 7 | SecondThread | 150 |
| 9 | pajenegod | 145 |
| 9 | orz | 145 |
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?
First thing that popped up: http://www.math.cmu.edu/~bwsulliv/domino-tilings.pdf
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.