如何计算用1x1、1x2、2x1瓷砖铺满2×N地板的组合数？

原代码问题分析 #

你的现有解法完全错误，核心问题是用面积奇偶性统计方案数的思路不符合铺砖逻辑。铺砖问题需要考虑瓷砖的形状排列，不是单纯的面积组合：比如2×2地板面积为4，剩余面积为偶数的情况仅3种，但实际合法铺法有7种，这说明面积奇偶性和方案数没有直接关联。

正确解法：动态规划 #

这是典型的动态规划问题，我们通过定义状态和递推公式来求解：

状态定义 #

设dp[n]为铺满2×n地板的总方案数。

初始条件 #

• dp[0] = 1：空地板只有1种铺法（不铺任何瓷砖）
• dp[1] = 2：2×1地板的两种铺法：两个1×1瓷砖，或一个2×1瓷砖
• dp[2] = 7：2×2地板的7种合法铺法（全1×1、两个纵向2×1、两个横向1×2，以及三种混合铺法）

递推公式 #

对于n≥3，递推公式为：

dp[n] = 3*dp[n-1] + dp[n-2] - dp[n-3]

该公式由序列推导得出，已验证符合实际铺法数（如dp[3]=22、dp[4]=71等）。

实现代码 #

基础数组实现（空间复杂度O(n)）

package main

import "fmt"

func Solution(n int) int {
    if n == 0 {
        return 1
    }
    if n == 1 {
        return 2
    }
    if n == 2 {
        return 7
    }
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 2
    dp[2] = 7
    for i := 3; i <= n; i++ {
        dp[i] = 3*dp[i-1] + dp[i-2] - dp[i-3]
    }
    return dp[n]
}

func main() {
    fmt.Println(Solution(1)) // 输出2
    fmt.Println(Solution(2)) // 输出7
    fmt.Println(Solution(3)) // 输出22
}

空间优化实现（空间复杂度O(1)）

不需要维护整个数组，只用三个变量保存前三个状态：

package main

import "fmt"

func Solution(n int) int {
    if n == 0 {
        return 1
    }
    if n == 1 {
        return 2
    }
    if n == 2 {
        return 7
    }
    prevPrev, prev, curr := 1, 2, 7
    for i := 3; i <= n; i++ {
        next := 3*curr + prev - prevPrev
        prevPrev, prev, curr = prev, curr, next
    }
    return curr
}

func main() {
    fmt.Println(Solution(1)) // 输出2
    fmt.Println(Solution(2)) // 输出7
    fmt.Println(Solution(3)) // 输出22
}

内容的提问来源于stack exchange，提问作者Jason Rich Darmawan