有多少种方法可以用2x1多米诺骨牌拼贴3xn矩形？

Question

每天我都在努力解决算法问题并尝试在这里问我无法回答的问题.对不起,如果我引起任何头痛.无论如何,

这里的问题从滑铁卢ACM大学程序设计竞赛.

有多少种方法可以用2x1多米诺骨牌拼贴3xn矩形？

Nirvana:闻起来像递归精神

Answer 1

只是对taskinoor答案中隐含给出的方程式的显式解决方案:

要么

f[n]=((1 + (-1)^n)*((2 - Sqrt[3])^(n/2)*(-1 + Sqrt[3]) + 
     (1 + Sqrt[3])* (2 + Sqrt[3])^(n/2)))/(4*Sqrt[3]) 

如果有人关心.

让我们显示10个值(奇数n没有解){n,f [n]}:

{6, 41.},   
{12, 2131.},   
{18, 110771.},   
{24, 5.75796*10^6},   
{30, 2.99303*10^8},   
{36, 1.5558*10^10}, 
{42, 8.08717*10^11},  
{48, 4.20377*10^13}, 
{54, 2.18515*10^15}, 
{60, 1.13586*10^17}

Answer 2

您可以使用动态编程解决此问题.检查这个可能的解决方案.