2022-04-02：你只有1*1、1*2、1*3、1*4，四种规格的砖块。 你想铺满n行m列的区域

2022-04-02：你只有11、12、13、14，四种规格的砖块。 你想铺满n行m列的区域，规则如下： 1）不管那种规格的砖，都只能横着摆， 比如1*3这种规格的砖，3长度是水平方向，1长度是竖直方向； 2）会有很多方法铺满整个区域，整块区域哪怕有一点点不一样，就算不同的方法； 3）区域内部(不算区域整体的4条边界)，不能有任何砖块的边界线（从上一直贯穿到下）。 返回符合三条规则下，铺满n行m列的区域，有多少种不同的摆放方法。 来自hulu。

答案2022-04-02：

这道题很难想。动态规划。

代码用golang编写。代码如下：

package main

import (
	"fmt"
)

func main() {
	ret := ways(4, 3)
	fmt.Println(ret)
}

var r = []int{0, 1, 2, 4, 8}

func ways(n, m int) int {
	if n <= 0 || m <= 1 {
		return 1
	}
	// len[i] = 一共有1行的情况下，列的长度为i的时候有几种摆法(所有，不分合法和非法)
	len0 := make([]int, m+1)
	for i := 1; i <= getMin(m, 4); i++ {
		len0[i] = r[i]
	}
	for i := 5; i <= m; i++ {
		len0[i] = len0[i-1] + len0[i-2] + len0[i-3] + len0[i-4]
	}
	// any[i] = 一共有n行的情况下，列的长度为i的时候有几种摆法(所有，不分合法和非法)
	any := make([]int, m+1)
	for i := 1; i <= m; i++ {
		// n * i的区域：总共的摆法！不区分合法、不合法
		any[i] = power(len0[i], n)
	}
	// solid[i] = 一共有n行的情况下，列的长度为i的时候有几种合法的摆法
	solid := make([]int, m+1)
	solid[1] = 1
	for i := 2; i <= m; i++ {
		invalid := 0
		// N * i
		// 1) （N * 1 合法） * （N * (i-1) 总共）
		// 2) （N * 2 合法） * （N * (i-2) 总共）
		// 3) （N * 3 合法） * （N * (i-3) 总共）
		//
		// j) （N * j 合法） * （N * (i-j) 总共）
		for j := 1; j < i; j++ {
			invalid += solid[j] * any[i-j]
		}
		solid[i] = any[i] - invalid
	}
	return solid[m]
}

func power(base, power int) int {
	ans := 1
	for power != 0 {
		if (power & 1) != 0 {
			ans *= base
		}
		base *= base
		power >>= 1
	}
	return ans
}

func getMin(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

执行结果如下：

左神java代码