本蒟蒻写的递推式不知道哪里有问题
查看原帖
本蒟蒻写的递推式不知道哪里有问题
932039
lzy20091001楼主2023/7/22 09:40

设f[i]表示面积为i的墙壁的覆盖方法(不是长为i而是面积为i)。


如果i为偶数,那么有f[i] = f[i - 2] + f[i - 4] + 2 * f[i - 3]。

以i = 8为例:

f[i - 2]表示竖着摆1块长2宽1的砖。

0001
0001

f[i - 4]表示横着摆2块长2宽1的砖。

0011
0022

f[i - 3]表示摆一块L形的转,因为有

0011  0001
0001  0011

两种摆法,所以要乘上2。


如果i为奇数,那么有f[i] = f[i - 2] + f[i - 3]。

以i = 7为例

f[i - 2]表示横着摆1块长2宽1的砖。

0011
000

f[i - 3]表示摆1块L形的砖。

0011
001

请问这个递推式哪里有问题?

2023/7/22 09:40
加载中...