有多少種不同的方式來創建磚牆？

-3

有多少種不同的方式可以創建長度爲n，高度爲2的磚牆？我們的磚塊尺寸爲2x1和1x1。磚是二維的。有多少種不同的方式來創建磚牆？

For example; 
if n=1, we need one 2x1 or we need two 1x1 bricks  
     so result is 2 different way 

if n=2, we need two 2x1 (vertical and horizontal) 
     or we need four 1x1 bricks      
     so result is 7 different way 

if n=3, result is 20 (Unfortunately I'm not sure :/)

...等

我需要一個算法，根據這個結果，但我並沒有關聯，這導致對方。你能幫我嗎？

來源

2014-12-13 pupil

對於n = 2，有7種不同的方式。兩個2x2垂直，但左側或右側磚可以被兩個1x1替換。兩個2x2水平，但頂部或底部磚可以被兩個1x1替換。和四個1x1。 – 2014-12-13 18:42:53

你是對的。而且我猜如果n = 3，結果是20，但是我仍然不能在它們之間做任何關係o.O – pupil 2014-12-13 18:55:21

這是歐拉項目嗎？ – 2014-12-13 19:08:34

說一面牆有兩層N「槽」。

P [L1] [L2] =砌磚的可能性，以便第一層的第一個L1槽和第二層的第一個L2槽填充磚料。

(1st level =>) 1122 
(2nd level =>) 344

情況1：L1 = L2

.... 
....

例如，該配置是在P [3] [4]（11，22，如圖3所示，44磚具有數字）捕獲

你把一個2×1垂直磚在端>您添加P [L1-1] [L2-1]至P [L1] [L2]

...1 
...1

你把一個1x1的磚上1級在en d =>您添加P [L1-1] [L2]到P [L1] [L2]

.... 
...1

您在端放一個1x1的磚上2級=>您添加P [L1] [L2 -1]到P [L1] [L2]

...1 
....

你們兩個2×1磚水平放置，一個在上2級1級，一個>您添加P [L1-2] [L2-2]至P [L1] [L2]

..22 
..11

現在我們完成垂直線上的情況。由此我們觀察到你的問題的解決方案在P [N] [N]中。但是，我們留下的情況是磚塊在兩個層面上的加起來不相同。

情況2：L1-1 = L2，像

... 
....

你把一個1x1的磚上水平1 =>添加P [L1-1] [L2]到P [L1] [L2]

... 
...1

您上水平放置一個2×1水平地磚1 =>添加P [L1-2] [L2]到P [L1] [L2]

... 
..11

情況3：L1 + 1 = L2，簡單對稱。

這裏的想法是案例不應該重疊，即一個磚塊配置不應該被多次計數。現在我們已經完成了一般情況。你剩下的只是處理最初的情況。

案件什麼都不是：P [0] [0] = 1（你只能有一個零長度的牆）。

Nothing 
Nothing

案例沒什麼-1：P 0 = 1（你只能加2級1x1的磚）。

. 
Nothing

案例1全無：P 1 [0] = 1（可以僅在1級添加一個1x1磚）。

Nothing 
.

在紙上做這件事，並確保所有的索引是正確的。

也坐下來理解這個TopCoder tutorial on dynamic programming。它會讓你遠離一天。

來源

2014-12-13 21:52:21

有多少種不同的方式來創建磚牆？

回答

相關問題