How to calculate how many possible combinations of 1x1, 1x2, 2x1 tiles can fill a 2 x N floor?

php Editor Shinichi will answer an interesting and brain-burning question for everyone: How to calculate how many possible combinations of 1x1, 1x2, and 2x1 tiles can fill a 2 x N floor? This problem involves the knowledge of combinatorial mathematics and dynamic programming. Through analysis and derivation, we can come up with a simple and effective calculation method. Next, let’s explore the answer to this question together!

Question content

I just did a technical test and am confused about the task. My goal is to understand how to solve this "covered floor" problem. I honestly don't know where to start.

The task is:

1. There are 2 x n layers.
2. We have 1x1, 1x2, 2x1 tiles to fill the floor.

The issue is:

1. solution(1) Expected output is 2, actual output is 2.
2. However, solution(2) expected output is 7, actual output is 3.

The current solution is:

1. 1x1 can always fill 2 x n layers, so the possible ways start at 1.
2. If the remaining floors mod 2 is 0, the possible ways are increased by 1.

The problem with the current solution is that it doesn't differentiate between 1x2 and 2x1 blocks. So for solution(2) the actual output is 3 instead of 7.

Code

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
    possibleWays := 1

    floorArea := 2 * n
    // Your code starts here.

    for i := floorArea - 1; i >= 0; i-- {
        residualFloorArea := floorArea - i
        fmt.Println(i, residualFloorArea)
        if residualFloorArea%2 == 0 {
            fmt.Println("punch")
            possibleWays += 1
        }
    }

    return possibleWays
}

func main() {
    fmt.Println(Solution(1))
    fmt.Println("next")
    fmt.Println(Solution(2))
}

Solution

A more descriptive and thorough attempt:

The number of methods called to cover the 2xn grid is x_n, the number of methods covering the 2xn 1 grid is y_n, and the number of methods covering the 2xn 2 grid is z_n.

Basic case:

• x_0 = 1, y_0 = 1, z_0 = 2
• x_1 = 2, y_1 = 3, z_1 = 5

Induction steps, n >=2:

-- --
      |  |  |
 -- -- -- --  ...
|xx|  |  |  |
 -- -- -- --

Consider the leftmost cell of a 2xn 2 grid, if it is covered by a 1x1 tile, then the rest is a 2xn 1 grid, otherwise, it is covered by a 1x2 tile, and the rest is a 2xn grid. therefore,

z_n = x_n y_n

-- --
   |  |  |
 -- -- --  ...
|xx|  |  |
 -- -- --

Consider the leftmost cell of a 2xn 1 grid, if it is covered by a 1x1 tile, the remainder will be 2xn grid, otherwise, it is covered by a 1x2 tile, the remainder will be 2x(n- 1) 1 grid. therefore,

y_n = x_n y_(n-1)

-- --
|xx|  |
 -- --  ...
|  |  |
 -- --

Consider the upper left corner of a 2xn grid, if it is covered by a 1x1 tile, the remainder will be 2x(n-1) 1 grid, if it is covered by a 1x2 tile, the remainder will be A 2x(n-2) 2 grid, otherwise, it is covered by 2x1 tiles and the remainder will be a 2x(n-1) grid. therefore:

x_n = y_(n-1) z_(n-2) x_(n-1)

Replacing z_n with x_n y_n, we have:

• x_n = x_(n-1) x_(n-2) y_(n-1) y_(n-2)
• y_n = x_n y_(n-1)

Now, just iterate over each value:

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
    if n == 0 {
        return 1
    } else if n == 1 {
        return 2
    }

    x := make([]int, n + 1)
    y := make([]int, n + 1)
    x[0] = 1
    y[0] = 1
    x[1] = 2
    y[1] = 3

    for i := 2; i <= n; i++ {
        x[i] = x[i - 1] + x[i - 2] + y[i - 1] + y[i - 2]
        y[i] = x[i] + y[i - 1]
    }

    return x[n]
}

func main() {
    fmt.Println(Solution(1))
    fmt.Println("next")
    fmt.Println(Solution(2))
}

You can do this without using slices, but it's easier to understand. Playground Demonstration

The above is the detailed content of How to calculate how many possible combinations of 1x1, 1x2, 2x1 tiles can fill a 2 x N floor?. For more information, please follow other related articles on the PHP Chinese website!