| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3885 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3580 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3506 |
| 7 | ecnerwala | 3505 |
| 8 | Radewoosh | 3457 |
| 9 | Kevin114514 | 3377 |
| 10 | gamegame | 3374 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 170 |
| 2 | Um_nik | 162 |
| 3 | atcoder_official | 161 |
| 4 | maomao90 | 159 |
| 5 | -is-this-fft- | 158 |
| 6 | djm03178 | 157 |
| 7 | Dominater069 | 156 |
| 8 | adamant | 154 |
| 9 | luogu_official | 153 |
| 10 | awoo | 152 |
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.