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代码