tiling算法題求解

Given N(integer), try to tile a 4 x N rectangle with 3 x 1 tiles.  In how many ways can it be done?


RT。周末准备参加学校里的一个编程小比赛，这是去年的一题。目前依旧没思路～

状态压缩动态规划吧。  铺瓷砖是经典应用了， 可以搜一下很多类似的

北美农民 发表于 2014-3-3 11:02
状态压缩动态规划吧。  铺瓷砖是经典应用了， 可以搜一下很多类似的

是的，2*N和3*N的不难，但4*N就让我蒙了～，求北美哥分析出递推式。。。

gnijuohz 发表于 2014-3-3 13:08
是的，2*N和3*N的不难，但4*N就让我蒙了～，求北美哥分析出递推式。。。

别喊我北美哥， 难听死了= =。 这题都一样的。 论坛回复不好解释啊， 要画图。 别说4*n了， m*n都行。

简单来说就是每一列看做一个二进制， D(i，j)表示第i列状态为j（转化为十进制后）能有多少方案， D[i,j] = 累加D[i - 1, k]， 其中j和k必须兼容， 你得用dfs做好预处理。

北美农民 发表于 2014-3-3 11:22
别喊我北美哥， 难听死了= =。 这题都一样的。 论坛回复不好解释啊， 要画图。 别说4*n了， m*n都行。

...

Alright, so the idea is swapping N with 4 and using DP? I'll try.

Do you have a blog or something? I think I could learn a lot :)

gnijuohz 发表于 2014-3-4 12:37
Alright, so the idea is swapping N with 4 and using DP? I'll try.

Do you have a blog or somethi ...

我也是新人， 没有blog这些。

这题因为基本unit是1*3或者3*1， 你要仔细想好怎么横着放怎么显示， 竖着放怎么显示， 状态转移怎么来。
但是anyway, 方法是general的