php小编新一将为大家解答一个有趣而烧脑的问题：如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x N 地板？这个问题涉及到组合数学和动态规划的知识，通过分析和推导，我们可以得出一个简洁而有效的计算方法。接下来，让我们一起来探索这个问题的答案吧！
问题内容
我刚刚做了一个技术测试，并对这个任务感到困惑。我的目标是了解如何解决这个“覆盖地板”问题。老实说，我不知道从哪里开始。
任务是：
- 有一层 2 x n 层。
- 我们有 1x1、1x2、2x1 的瓷砖来填充地板。
问题是：
-
solution(1)预期输出为 2，实际输出为 2。 - 但是，
solution(2)预期输出为 7，实际输出为 3。
当前的解决方案是：
- 1x1 总是可以填满 2 x n 层，因此可能的方式从 1 开始。
- 如果剩余楼层 mod 2 为 0，则可能的方式增加 1。
当前解决方案的问题是它不区分 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。
基本案例：
- x_0 = 1，y_0 = 1，z_0 = 2
- x_1 = 2，y_1 = 3，z_1 = 5
归纳步骤，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，我们有：
- x_n = x_(n-1) + x_(n-2) + y_(n-1) + y_(n-2)
- y_n = x_n + y_(n-1)
现在，只需迭代计算每个值：
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))
}
您可以不使用切片来完成此操作，但这更容易理解。 游乐场演示
