我刚刚做了一个技术测试,并对这个任务感到困惑。我的目标是了解如何解决这个“覆盖地板”问题。老实说,我不知道从哪里开始。
任务是:
问题是:
Solution(1)
预期输出为 2,实际输出为 2。Solution(2)
预期产出是7,实际产出是3。目前的解决方案是:
当前解决方案的问题是它不区分 1x2 和 2x1 的图块。因此,对于
Solution(2)
,实际输出是 3 而不是 7。
代码
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$。