我刚刚做了一个技术测试，并对这个任务感到困惑。我的目标是了解如何解决这个“覆盖地板”问题。老实说，我不知道从哪里开始。
任务是：
问题是：
Solution(1)Solution(2)目前的解决方案是：
当前解决方案的问题是它不区分 1x2 和 2x1 的图块。因此，对于
Solution(2)代码
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))
}
更具描述性且详尽的尝试：
称覆盖2xN网格的方式数量为x_n，覆盖2xN+1网格的方式数量为y_n，覆盖2xN+2网格的方式数量为z_n。
基本案例：
归纳步骤，N >= 2：
-- --
| | |
-- -- -- -- ...
|xx| | | |
-- -- -- --
考虑 2xN + 2 网格的最左边的单元格，如果它被 1x1 瓦片覆盖，那么剩下的就是 2xN + 1 网格，否则，它被 1x2 瓦片覆盖，剩下的就是 2xN 网格。因此，
z_n = x_n + y_n
-- --
| | |
-- -- -- ...
|xx| | |
-- -- --
考虑 2xN + 1 网格的最左边的单元格，如果它被 1x1 瓦片覆盖，剩余的将是 2xN 网格，否则，它被 1x2 瓦片覆盖，剩余的将是 2x(N-1) + 1 个网格。因此，
y_n = x_n + y_(n-1)
-- --
|xx| |
-- -- ...
| | |
-- --
考虑 2xN 网格的左上角，如果它被 1x1 块覆盖，则剩余将是 2x(N-1) + 1 网格，如果它被 1x2 块覆盖，剩余将是 2x( N-2) + 2 个网格，否则，它被 2x1 的图块覆盖，剩余的将是 2x(N-1) 的网格。因此：
x_n = y_(n-1) + z_(n-2) + x_(n-1)
将 z_n 替换为 x_n + y_n，我们有：
现在，只需迭代计算每个值：
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))
}
你可以不做切片，但这更容易理解。 游乐场示范
这主要是一个简单的组合难题，而不是编程练习。诀窍是计算平铺 2xN 网格的方式数量，以及前两个方格之一已填充的 2xN 网格。这给出了递归关系，可以通过计算来解决。
设 F(N) 为平铺 2xN 网格的方式数，G(N) 为平铺前两个方格之一已填充的网格的方式数。
我们可以枚举从左侧开始填充网格的方法（注意不要计算两次）：
A...
A...
A...
BB..
AA..
B...
A...
B...
AA..
BB..
因此，F(N) = 2F(N-1) + 2G(N-1) + F(N-2)
G 也一样（这里# 是已经填满的那一块）：
#...
A...
#...
AA..
所以 G(N) = F(N-1) + G(N-1)
我们还有基本情况：F(0) = 1、G(0)=0、F(1) = 2、G(1) = 1。
根据这些递推关系，我们可以在 O(N) 算术运算中迭代地解决问题：
package main
import "fmt"
func F(N int) int {
f0, f1 := 1, 2
g1 := 1
for i := 0; i < N; i++ {
f1, g1, f0 = 2*f1+2*g1+f0, f1+g1, f1
}
return f0
}
func main() {
for i := 0; i < 10; i++ {
fmt.Println(i, F(i))
}
}
另一种方法是使用第一个 2x1 图块上的案例来计算排列（或者如果它从未出现过）。
首先，用 1x1 和 1x2 块来平铺 $1 imes k$ 网格的方法数量为 $F_{k+1}$。我将把它作为练习来证明斐波那契递归成立[提示：考虑最后一个图块是 1x1 还是 1x2]。
现在用 $S_k$ 表示 $2 imes k$ 地板的平铺。请注意，任一行（或列）中必须有偶数个 $1 imes 1$，以便我们可以在第一个垂直 1x2 上使用案例。如果它出现在位置 $k$，则问题相当于 $(F_k)^2S_{n-k}$，因为我们需要独立平铺两行 $1 imes (k-1)$。如果它根本没有出现，我们出于同样的原因添加 $(F_{n+1})^2$ 。求和产生类似于加泰罗尼亚数的递归。给定初始条件 $S_0 = 1, S_1 = 2$，我们有 $S_n = \sum_{k=1}^n (F_k)^2S_{n-k} + (F_{n+1})^2$ 所以第一个几个术语是： [1, 2, 7, 22, 71, 228, 733, 2356, 7573, \点。] （请注意，序列以 $S_0$ 开头，而不是 $S_1$。